Monday, February 13, 2017
Humboldt-Universität zu Berlin
Johann von Neumann-Haus
Institut für Informatik
Rudower Chaussee 25 (Ecke Magnusstr.)
12489 Berlin
Humboldt-Kabinett
Lecture - 14:15
Abstract:
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
Abstract:
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.