Source author record

Christian Coester

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms math.MG Discrete Mathematics

Catalog footprint

Research overview

5works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Competitive Algorithms for Block-Aware Caching

We study the block-aware caching problem, a generalization of classic caching in which fetching (or evicting) pages from the same block incurs the same cost as fetching (or evicting) just one page from the block. Given a cache of size $k$ , and a sequence of requests from $n$ pages partitioned into given blocks of size $β\leq k$ , the goal is to minimize the total cost of fetching to (or evicting from) cache. We show the following results: $\bullet$ For the eviction cost model, we show an $O(\log k)$ -approximate offline algorithm, a $k$ -competitive deterministic online algorithm, and an $O(\log^2 k)$ -competitive randomized online algorithm. $\bullet$ For the fetching cost model, we show an integrality gap of $Ω(β)$ for the natural LP relaxation of the problem, and an $Ω(β+ \log k)$ lower bound for randomized online algorithms. The strategy of ignoring the block-structure and running a classical paging algorithm trivially achieves an $O(β)$ approximation and an $O(β\log k)$ competitive ratio respectively for the offline and online-randomized setting. $\bullet$ For both fetching and eviction models, we show improved bounds for the $(h,k)$ -bicriteria version of the problem. In particular, when $k=2h$ , we match the performance of classical caching algorithms up to constant factors. Our results establish a separation between the tractability of the fetching and eviction cost models, which is interesting since fetching/evictions costs are the same up to an additive term for classic caching. Previous work only studied online deterministic algorithms for the fetching cost model when $k > h$ . Our insight is to relax the block-aware caching problem to a submodular covering LP. The main technical challenge is to maintain a competitive fractional solution, and to round it with bounded loss, as the constraints of this LP are revealed online.

preprint2021arXiv

Towards the k-server conjecture: A unifying potential, pushing the frontier to the circle

The $k$ -server conjecture, first posed by Manasse, McGeoch and Sleator in 1988, states that a $k$ -competitive deterministic algorithm for the $k$ -server problem exists. It is conjectured that the work function algorithm (WFA) achieves this guarantee, a multi-purpose algorithm with applications to various online problems. This has been shown for several special cases: $k=2$ , $(k+1)$ -point metrics, $(k+2)$ -point metrics, the line metric, weighted star metrics, and $k=3$ in the Manhattan plane. The known proofs of these results are based on potential functions tied to each particular special case, thus requiring six different potential functions for the six cases. We present a single potential function proving $k$ -competitiveness of WFA for all these cases. We also use this potential to show $k$ -competitiveness of WFA on multiray spaces and for $k=3$ on trees. While the DoubleCoverage algorithm was known to be $k$ -competitive for these latter cases, it has been open for WFA. Our potential captures a type of lazy adversary and thus shows that in all settled cases, the worst-case adversary is lazy. Chrobak and Larmore conjectured in 1992 that a potential capturing the lazy adversary would resolve the $k$ -server conjecture. To our major surprise, this is not the case, as we show (using connections to the $k$ -taxi problem) that our potential fails for three servers on the circle. Thus, our potential highlights laziness of the adversary as a fundamental property that is shared by all settled cases but violated in general. On the one hand, this weakens our confidence in the validity of the $k$ -server conjecture. On the other hand, if the $k$ -server conjecture holds, then we believe it can be proved by a variant of our potential.

preprint2020arXiv

Metrical Service Systems with Transformations

We consider a generalization of the fundamental online metrical service systems (MSS) problem where the feasible region can be transformed between requests. In this problem, which we call T-MSS, an algorithm maintains a point in a metric space and has to serve a sequence of requests. Each request is a map (transformation) $f_t\colon A_t\to B_t$ between subsets $A_t$ and $B_t$ of the metric space. To serve it, the algorithm has to go to a point $a_t\in A_t$ , paying the distance from its previous position. Then, the transformation is applied, modifying the algorithm's state to $f_t(a_t)$ . Such transformations can model, e.g., changes to the environment that are outside of an algorithm's control, and we therefore do not charge any additional cost to the algorithm when the transformation is applied. The transformations also allow to model requests occurring in the $k$ -taxi problem. We show that for $α$ -Lipschitz transformations, the competitive ratio is $Θ(α)^{n-2}$ on $n$ -point metrics. Here, the upper bound is achieved by a deterministic algorithm and the lower bound holds even for randomized algorithms. For the $k$ -taxi problem, we prove a competitive ratio of $\tilde O((n\log k)^2)$ . For chasing convex bodies, we show that even with contracting transformations no competitive algorithm exists. The problem T-MSS has a striking connection to the following deep mathematical question: Given a finite metric space $M$ , what is the required cardinality of an extension $\hat M\supseteq M$ where each partial isometry on $M$ extends to an automorphism? We give partial answers for special cases.

preprint2020arXiv

Pure entropic regularization for metrical task systems

We show that on every $n$ -point HST metric, there is a randomized online algorithm for metrical task systems (MTS) that is $1$ -competitive for service costs and $O(\log n)$ -competitive for movement costs. In general, these refined guarantees are optimal up to the implicit constant. While an $O(\log n)$ -competitive algorithm for MTS on HST metrics was developed by Bubeck et al. (SODA 2019), that approach could only establish an $O((\log n)^2)$ -competitive ratio when the service costs are required to be $O(1)$ -competitive. Our algorithm can be viewed as an instantiation of online mirror descent with the regularizer derived from a multiscale conditional entropy. In fact, our algorithm satisfies a set of even more refined guarantees; we are able to exploit this property to combine it with known random embedding theorems and obtain, for any $n$ -point metric space, a randomized algorithm that is $1$ -competitive for service costs and $O((\log n)^2)$ -competitive for movement costs.

preprint2020arXiv

Unbounded lower bound for k-server against weak adversaries

We study the resource augmented version of the $k$ -server problem, also known as the $k$ -server problem against weak adversaries or the $(h,k)$ -server problem. In this setting, an online algorithm using $k$ servers is compared to an offline algorithm using $h$ servers, where $h\le k$ . For uniform metrics, it has been known since the seminal work of Sleator and Tarjan (1985) that for any $ε>0$ , the competitive ratio drops to a constant if $k=(1+ε) \cdot h$ . This result was later generalized to weighted stars (Young 1994) and trees of bounded depth (Bansal et al. 2017). The main open problem for this setting is whether a similar phenomenon occurs on general metrics. We resolve this question negatively. With a simple recursive construction, we show that the competitive ratio is at least $Ω(\log \log h)$ , even as $k\to\infty$ . Our lower bound holds for both deterministic and randomized algorithms. It also disproves the existence of a competitive algorithm for the infinite server problem on general metrics.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Christian Coester

Research overview

Is this your work?

5 publications

Competitive Algorithms for Block-Aware Caching

Towards the k-server conjecture: A unifying potential, pushing the frontier to the circle

Metrical Service Systems with Transformations

Pure entropic regularization for metrical task systems

Unbounded lower bound for k-server against weak adversaries

See the researcher in context

Building this map preview