More Like this

1. Tight Bounds for Parallel Paging and Green Paging

   https://doi.org/10.1137/1.9781611976465.180  

   Agrawal, Kunal; Bender, Michael A.; Das, Rathish; Kuszmaul, William; Peserico, Enoch; Scquizzato, Michele (January 2021, Proc.\ 32th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA))

   null (Ed.)

   In the parallel paging problem, there are $$\pP$$ processors that share a cache of size $$k$$. The goal is to partition the cache among the \procs over time in order to minimize their average completion time. For this long-standing open problem, we give tight upper and lower bounds of $$\Theta(\log \p)$ on the competitive ratio with $O(1)$ resource augmentation. A key idea in both our algorithms and lower bounds is to relate the problem of parallel paging to the seemingly unrelated problem of green paging. In green paging, there is an energy-optimized processor that can temporarily turn off one or more of its cache banks (thereby reducing power consumption), so that the cache size varies between a maximum size $$k$$ and a minimum size $$k/\p$$. The goal is to minimize the total energy consumed by the computation, which is proportional to the integral of the cache size over time. We show that any efficient solution to green paging can be converted into an efficient solution to parallel paging, and that any lower bound for green paging can be converted into a lower bound for parallel paging, in both cases in a black-box fashion. We then show that, with $O(1)$ resource augmentation, the optimal competitive ratio for deterministic online green paging is $$\Theta(\log \p)$$, which, in turn, implies the same bounds for deterministic online parallel paging. 

   more » « less
2. Online Paging with Heterogeneous Cache Slots

   https://doi.org/10.1007/s00453-024-01270-z  

   Chrobak, Marek; Haney, Samuel; Liaee, Mehraneh; Panigrahi, Debmalya; Rajaraman, Rajmohan; Sundaram, Ravi; Young, Neal_E (October 2024, Algorithmica)

   Abstract It is natural to generalize the online$$k$$ $k$-Server problem by allowing each request to specify not only a pointp, but also a subsetSof servers that may serve it. To date, only a few special cases of this problem have been studied. The objective of the work presented in this paper has been to more systematically explore this generalization in the case of uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a pagep, but also a subsetSof cache slots, and is satisfied by having a copy ofpin some slot inS. We call this problemSlot-Heterogenous Paging. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family$${\mathcal {S}}\subseteq 2^{[k]}$$ $S\subseteq 2^{\left[k\right]}$of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache sizekand family$${\mathcal {S}}$$ $S$:If all request sets are allowed ($${\mathcal {S}}=2^{[k]}\setminus \{\emptyset \}$$ $S=2^{\left[k\right]}\backslash \left\{\varnothing \right\}$), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging ($${\mathcal {S}}=\{[k]\}$$ $S=\left\{\right[k\left]\right\}$).As a function of$$|{\mathcal {S}}|$$ $\left|S\right|$andk, the optimal deterministic ratio is polynomial: at most$$O(k^2|{\mathcal {S}}|)$$ $O\left(k^2\right|S\left|\right)$and at least$$\Omega (\sqrt{|{\mathcal {S}}|})$$ $\Omega \left(\sqrt{\left|S\right|}\right)$.For any laminar family$${\mathcal {S}}$$ $S$of heighth, the optimal ratios areO(hk) (deterministic) and$$O(h^2\log k)$$ $O(h^{2}logk)$(randomized).The special case of laminar$${\mathcal {S}}$$ $S$that we callAll-or-One Pagingextends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio forweightedAll-or-One Paging is$$\Theta (k)$$ $\Theta \left(k\right)$. Offline All-or-One Paging is$$\mathbb{N}\mathbb{P}$$ $NP$-hard.Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set$$P$$ $P$ofpages, and is satisfied by fetching any page from$$P$$ $P$into the cache. The optimal ratios for the latter problem (with laminar family of heighth) are at mosthk(deterministic) and$$hH_k$$ $h{H}_k$(randomized). 

   more » « less
3. Efficient Algorithms and Hardness Results for the Weighted k-Server Problem

   https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2023.12  

   Gupta, Anupam; Kumar, Amit; Panigrahi, Debmalya (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Megow, Nicole; Smith, Adam (Ed.)

   In this paper, we study the weighted k-server problem on the uniform metric in both the offline and online settings. We start with the offline setting. In contrast to the (unweighted) k-server problem which has a polynomial-time solution using min-cost flows, there are strong computational lower bounds for the weighted k-server problem, even on the uniform metric. Specifically, we show that assuming the unique games conjecture, there are no polynomial-time algorithms with a sub-polynomial approximation factor, even if we use c-resource augmentation for c < 2. Furthermore, if we consider the natural LP relaxation of the problem, then obtaining a bounded integrality gap requires us to use at least 𝓁 resource augmentation, where 𝓁 is the number of distinct server weights. We complement these results by obtaining a constant-approximation algorithm via LP rounding, with a resource augmentation of (2+ε)𝓁 for any constant ε > 0. In the online setting, an exp(k) lower bound is known for the competitive ratio of any randomized algorithm for the weighted k-server problem on the uniform metric. In contrast, we show that 2𝓁-resource augmentation can bring the competitive ratio down by an exponential factor to only O(𝓁² log 𝓁). Our online algorithm uses the two-stage approach of first obtaining a fractional solution using the online primal-dual framework, and then rounding it online. 

   more » « less
4. Online Algorithms for Weighted Paging with Predictions

   https://doi.org/10.1145/3548774  

   Jiang, Zhihao; Panigrahi, Debmalya; Sun, Kevin (October 2022, ACM Transactions on Algorithms)

   In this article, we initiate the study of the weighted paging problem with predictions. This continues the recent line of work in online algorithms with predictions, particularly that of Lykouris and Vassilvitski (ICML 2018) and Rohatgi (SODA 2020) on unweighted paging with predictions. We show that unlike unweighted paging, neither a fixed lookahead nor a knowledge of the next request for every page is sufficient information for an algorithm to overcome the existing lower bounds in weighted paging. However, a combination of the two, which we call strong per request prediction (SPRP), suffices to give a 2-competitive algorithm. We also explore the question of gracefully degrading algorithms with increasing prediction error, and give both upper and lower bounds for a set of natural measures of prediction error. 

   more » « less
5. Online k-Median with Consistent Clusters

   https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.20  

   Moseley, Benjamin; Newman, Heather; Pruhs, Kirk (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Kumar, Amit; Ron-Zewi, Noga (Ed.)

   We consider the problem in which n points arrive online over time, and upon arrival must be irrevocably assigned to one of k clusters where the objective is the standard k-median objective. Lower-bound instances show that for this problem no online algorithm can achieve a competitive ratio bounded by any function of n. Thus we turn to a beyond worst-case analysis approach, namely we assume that the online algorithm is a priori provided with a predicted budget B that is an upper bound to the optimal objective value (e.g., obtained from past instances). Our main result is an online algorithm whose competitive ratio (measured against B) is solely a function of k. We also give a lower bound showing that the competitive ratio of every algorithm must depend on k. 

   more » « less