Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, February 13, 2017

Humboldt-Universität zu Berlin
Johann von Neumann-Haus
Institut für Informatik
Rudower Chaussee 25 (Ecke Magnusstr.)
12489 Berlin

Lecture - 14:15

Friedhelm Meyer auf der Heide - Paderborn University, Heinz Nixdorf Institute & Computer Science Department

Online Resource Leasing

Decisions regarding which resources to acquire in order to provide services comprise the core of many optimization problems. Classical problems which fall into this category of problems are for example Facility Location, Steiner Tree, and Set Cover, as well as several scheduling problems. Such problems have been widely studied in both offline and online settings. Traditionally, the decisions are considered to be final: we buy the resources. Once a resource is bought, it can be used any time in the future without inducing further costs.

Inspired by the Cloud Computing market, we consider the leasing variants of the above problems: Resources are not bought, but leased for a given time interval; the cost for a lease typically grows with the length of the interval, but the cost per time unit decreases with this length.

Such a model for leasing was introduced by Meyerson as the parking permit problem. In the talk, I will present online algorithms for several resource leasing problems. Technically, our algorithmic approach is mostly based on an online variant of primal-dual approximation algorithms.

The talk presents joint work with Christine Markarian

Colloquium - 16:00

Christoph Berkholz - Humboldt-Universität zu Berlin

Answering Conjunctive Queries under Updates

In this talk I present a recent joint work with Jens Keppeler and Nicole Schweikardt on the algorithmic task of answering conjunctive queries on dynamic databases. Our main result is a dichotomy theorem that precisely characterises those conjunctive queries that can be evaluated efficiently.

This work will appear at PODS 2017 and the more detailed abstract of the paper can be found below.

We consider the task of enumerating and counting answers to k-ary conjunctive queries against relational databases that may be updated by inserting or deleting tuples.
We exhibit a new notion of q-hierarchical conjunctive queries and show that these can be maintained efficiently in the following sense. During a linear time preprocessing phase, we can build a data structure that enables constant delay enumeration of the query results; and when the database is updated, we can update the data structure and restart the enumeration phase within constant time. For the special case of self-join free conjunctive queries we obtain a dichotomy: if a query is not q-hierarchical, then query enumeration with sublinear delay and sublinear update time (and arbitrary preprocessing time) is impossible.
For Boolean conjunctive queries and the more general problem of counting the number of solutions of a k-ary query we obtain complete dichotomies: if the query's homomorphic core is q-hierarchical, then size of the the query result can be computed in linear time and maintained with constant update time. Otherwise, the size of the query result cannot be maintained with sublinear update time.
All our lower bounds rely on the OMv-conjecture, a conjecture on the hardness of online matrix-vector multiplication that has recently emerged in the field of fine-grained complexity to characterise the hardness of dynamic problems. The lower bound for the counting problem additionally relies on the orthogonal vectors conjecture, which in turn is implied by the strong exponential time hypothesis.

Letzte Aktualisierung: 07.02.2017