Search

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: A_t → 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 ∈ 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 Õ((nlog k)²). 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 M̂ ⊇ M where each partial isometry on M extends to an automorphism? We give partial answers for special cases., LIPIcs, Vol. 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), pages 21:1-21:20

A major technique in learning-augmented online algorithms is combining multiple algorithms or predictors. Since the performance of each predictor may vary over time, it is desirable to use not the single best predictor as a benchmark, but rather a dynamic combination which follows different predictors at different times. We design algorithms that combine predictions and are competitive against such dynamic combinations for a wide class of online problems, namely, metrical task systems. Against the best (in hindsight) unconstrained combination of $\ell$ predictors, we obtain a competitive ratio of $O(\ell^2)$, and show that this is best possible. However, for a benchmark with slightly constrained number of switches between different predictors, we can get a $(1+\epsilon)$-competitive algorithm. Moreover, our algorithms can be adapted to access predictors in a bandit-like fashion, querying only one predictor at a time. An unexpected implication of one of our lower bounds is a new structural insight about covering formulations for the $k$-server problem.

In a 1989 paper titled "shortest paths without a map", Papadimitriou and Yannakakis introduced an online model of searching in a weighted layered graph for a target node, while attempting to minimize the total length of the path traversed by the searcher. This problem, later called layered graph traversal, is parametrized by the maximum cardinality $k$ of a layer of the input graph. It is an online setting for dynamic programming, and it is known to be a rather general and fundamental model of online computing, which includes as special cases other acclaimed models. The deterministic competitive ratio for this problem was soon discovered to be exponential in $k$, and it is now nearly resolved: it lies between $\Omega(2^k)$ and $O(k2^k)$. Regarding the randomized competitive ratio, in 1993 Ramesh proved, surprisingly, that this ratio has to be at least $\Omega(k^2 / \log^{1+\epsilon} k)$ (for any constant $\epsilon > 0$). In the same paper, Ramesh also gave an $O(k^{13})$-competitive randomized online algorithm. Since 1993, no progress has been reported on the randomized competitive ratio of layered graph traversal. In this work we show how to apply the mirror descent framework on a carefully selected evolving metric space, and obtain an $O(k^2)$-competitive randomized online algorithm, nearly matching the known lower bound on the randomized competitive ratio.

We prove a few new lower bounds on the randomized competitive ratio for the $k$-server problem and other related problems, resolving some long-standing conjectures. In particular, for metrical task systems (MTS) we asympotically settle the competitive ratio and obtain the first improvement to an existential lower bound since the introduction of the model 35 years ago (in 1987). More concretely, we show: 1. There exist $(k+1)$-point metric spaces in which the randomized competitive ratio for the $k$-server problem is $\Omega(\log^2 k)$. This refutes the folklore conjecture (which is known to hold in some families of metrics) that in all metric spaces with at least $k+1$ points, the competitive ratio is $\Theta(\log k)$. 2. Consequently, there exist $n$-point metric spaces in which the randomized competitive ratio for MTS is $\Omega(\log^2 n)$. This matches the upper bound that holds for all metrics. The previously best existential lower bound was $\Omega(\log n)$ (which was known to be tight for some families of metrics). 3. For all $k

Motivated by the design of real system storage hierarchies, 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 ß = k, the goal is to minimize the total cost of fetching to (or evicting from) cache. This problem captures generalized caching as a special case, which is already NP-hard offline. We show the following suite of results: • For the eviction cost model, we show an O(log k)-approximate offline algorithm, a k-competitive deterministic online algorithm, and an O(log2k)-competitive randomized online algorithm. • For the fetching cost model, we show an integrality gap of O(ß) for the natural LP relaxation of the problem, and an O(ß +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. • 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 strong separation between the tractability of the fetching and eviction cost models, which is interesting since fetching/eviction costs are the same up to an additive term for the classic caching problem. Previous work of Beckmann et al. (SPAA 21) 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 linear program. The main technical challenge is to maintain a competitive fractional solution to this LP, and to round it with bounded loss, as the constraints of this LP are revealed online. We hope that this framework is useful going forward for other problems that can be captured as submodular cover.

We introduce a general online allocation problem that connects several of the most fundamental problems in online optimization. Let M be an n-point metric space. Consider a resource that can be allocated in arbitrary fractions to the points of M. At each time t, a convex monotone cost function c_t: [0,1] → ℝ_+ appears at some point r_t ∈ M. In response, an algorithm may change the allocation of the resource, paying movement cost as determined by the metric and service cost c_t(x_{r_t}), where x_{r_t} is the fraction of the resource at r_t at the end of time t. For example, when the cost functions are c_t(x) = α x, this is equivalent to randomized MTS, and when the cost functions are c_t(x) = ∞⋅1_{x < 1/k}, this is equivalent to fractional k-server. Because of an inherent scale-freeness property of the problem, existing techniques for MTS and k-server fail to achieve similar guarantees for metric allocation. To handle this, we consider a generalization of the online multiplicative update method where we decouple the rate at which a variable is updated from its value, resulting in interesting new dynamics. We use this to give an O(log n)-competitive algorithm for weighted star metrics. We then show how this corresponds to an extension of the online mirror descent framework to a setting where the regularizer is time-varying. Using this perspective, we further refine the guarantees of our algorithm. We also consider the case of non-convex cost functions. Using a simple 𝓁₂²-regularizer, we give tight bounds of Θ(n) on tree metrics, which imply deterministic and randomized competitive ratios of O(n²) and O(nlog n) respectively on arbitrary metrics., LIPIcs, Vol. 244, 30th Annual European Symposium on Algorithms (ESA 2022), pages 13:1-13:13

We study the online problem of minimizing power consumption in systems with multiple power-saving states. During idle periods of unknown lengths, an algorithm has to choose between power-saving states of different energy consumption and wake-up costs. We develop a learning-augmented online algorithm that makes decisions based on (potentially inaccurate) predicted lengths of the idle periods. The algorithm's performance is near-optimal when predictions are accurate and degrades gracefully with increasing prediction error, with a worst-case guarantee almost identical to the optimal classical online algorithm for the problem. A key ingredient in our approach is a new algorithm for the online ski rental problem in the learning augmented setting with tight dependence on the prediction error. We support our theoretical findings with experiments.

In the online k-server problem, an algorithm controls k mobile servers in a metric space. One by one, requests arrive at points of the space, and the algorithm must serve each request by selecting a server to visit it. The goal is to minimize the total distance traveled by all servers. In the framework of competitive analysis, we study two variants of the k-server problem, the infinite server problem and the k-taxi problem, and the more general metrical task systems problem. The infinite server problem is the variant of the k-server problem where the number of servers is infinite, initially all starting at the same point. We obtain a surprisingly tight connection between the infinite server problem and the resource augmentation version of the k-server problem. Using this connection, we also improve the known lower bounds for the resource augmented k-server problem. The k-taxi problem generalizes the k-server problem in that a request consists not of one point, but two points s and t, representing the start and destination of a taxi request. To serve such a request, a server (taxi) must move first to s and then to t. This problem becomes particularly difficult when the cost is defined as the distance of empty runs only. Indeed, we show an exponential gap between the competitive ratio of the k-taxi problem and that of the k-server problem. A main positive result is an O(2k log n)-competitive algorithm for arbitrary n-point metrics. Metrical task systems are a general framework subsuming many other online problems, including the k-server problem. Here, the algorithm suffers two kinds of costs, movement and service costs. For HST metrics, using an entropy regularization approach, we obtain tight bounds on the refined guarantees, i.e., movement and service costs are simultaneously optimally competitive against the optimal total cost. This also improves the refined guarantees for general metrics.

We consider a natural semi-online model for weighted paging, where at any time the algorithm is given predictions, possibly with errors, about the next arrival of each page. The model is inspired by Belady's classic optimal offline algorithm for unweighted paging, and extends the recently studied model for learning-augmented paging (Lykouris and Vassilvitskii, 2018) to the weighted setting. For the case of perfect predictions, we provide an $\ell$-competitive deterministic and an $O(\log \ell)$-competitive randomized algorithm, where $\ell$ is the number of distinct weight classes. Both these bounds are tight, and imply an $O(\log W)$- and $O(\log \log W)$-competitive ratio, respectively, when the page weights lie between $1$ and $W$. Previously, it was not known how to use these predictions in the weighted setting and only bounds of $k$ and $O(\log k)$ were known, where $k$ is the cache size. Our results also generalize to the interleaved paging setting and to the case of imperfect predictions, with the competitive ratios degrading smoothly from $O(\ell)$ and $O(\log \ell)$ to $O(k)$ and $O(\log k)$, respectively, as the prediction error increases. Our results are based on several insights on structural properties of Belady's algorithm and the sequence of page arrival predictions, and novel potential functions that incorporate these predictions. For the case of unweighted paging, the results imply a very simple potential function based proof of the optimality of Belady's algorithm, which may be of independent interest.

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., COLT 2019

We study online competitive algorithms for the line chasing problem in Euclidean spaces Rd, where the input consists of an initial point P0 and a sequence of lines X1,X2,...,Xm, revealed one at a time. At each step t, when the line Xt is revealed, the algorithm must determine a point Pt ∈ Xt. An online algorithm is called c-competitive if for any input sequence the path P0, P1, ..., Pm it computes has length at most c times the optimum path. The line chasing problem is a variant of a more general convex body chasing problem, where the sets Xt are arbitrary convex sets. To date, the best competitive ratio for the line chasing problem was 28.1, even in the plane. We improve this bound by providing a simple 3-competitive algorithm for any dimension d. We complement this bound by a matching lower bound for algorithms that are memoryless in the sense of our algorithm, and a lower bound of 1.5358 for arbitrary algorithms. The latter bound also improves upon the previous lower bound of √2 ≈ 1.412 for convex body chasing in 2 dimensions.

Francia, Bd. 33, Nr. 2 (2006)