|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Scale-Free Allocation, Amortized Convexity, and Myopic Weighted Paging | | Nikhil Bansal
; Christian Coester
; Ravi Kumar
; Manish Purohit
; Erik Vee
; | | Date: |
18 Nov 2020 | | Abstract: | Inspired by Belady’s optimal algorithm for unweighted paging, we consider a
natural myopic model for weighted paging in which an algorithm has access to
the relative ordering of all pages with respect to the time of their next
arrival. 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$. Our model and results also simultaneously generalize the
paging with predictions (Lykouris and Vassilvitskii, 2018) and the interleaved
paging (Barve et al., 2000; Cao et al., 1994; Kumar et al., 2019) settings to
the weighted case.
Perhaps more interestingly, our techniques shed light on a family of
interconnected geometric allocation problems. We show that the competitiveness
of myopic weighted paging lies in between that of two similar problems called
soft and strict allocation. While variants of the allocation problem have been
studied previously in the context of the $k$-server problem, our formulation
exhibits a certain scale-free property that poses significant technical
challenges. Consequently, simple multiplicative weight update algorithms do not
seem to work here; instead, we are forced to use a novel technique that
decouples the rate of change of the allocation variables from their value. For
offline unweighted paging, we also provide an alternate proof of the optimality
of Belady’s classic Farthest in Future algorithm, which may be of independent
interest. | | Source: | arXiv, 2011.09076 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER