Managing Multiple Mobile Resources

Bj\"orn Feldkord; Friedhelm Meyer auf der Heide; Manuel Malatyali; Till Knollmann

arxiv: 1907.09834 · v1 · pith:VNERGQ4Xnew · submitted 2019-07-23 · 💻 cs.DS

Managing Multiple Mobile Resources

Bj\"orn Feldkord , Till Knollmann , Manuel Malatyali , Friedhelm Meyer auf der Heide This is my paper

Pith reviewed 2026-05-24 17:06 UTC · model grok-4.3

classification 💻 cs.DS

keywords mobile serversonline algorithmscompetitive analysispage migrationrequest localityeuclidean spaceaugmentationdeterministic algorithms

0 comments

The pith

A deterministic online algorithm simulates any k-page migration solution to manage k mobile servers under request locality and movement augmentation, yielding a competitive ratio polynomial in k, m_c/m_s, 1/δ and the simulated ratio.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that in the k-mobile server problem, where servers move at most m_s per round to serve distance-based requests in Euclidean space, no online algorithm achieves a competitive ratio independent of input length n, even with (1+δ) augmentation. Restricting the adversary to local request sequences, where each consecutive pair lies at most m_c apart, enables a positive result: any algorithm for classical k-page migration can be simulated and extended by one greedy server move per round to obtain bounded competitiveness. This matters because the locality assumption turns an impossible setting into one where the ratio depends only on k, the ratio m_c/m_s, the augmentation parameter, and the quality of the simulated page-migration algorithm, remaining independent of n.

Core claim

The central claim is that there exists a deterministic online algorithm which, given any algorithm for the classical k-Page Migration problem, achieves a competitive ratio polynomial in k, m_c/m_s, 1/δ and the competitive ratio of the simulated algorithm, when the online algorithm is allowed (1+δ)m_s movement augmentation and the request sequence obeys locality of m_c.

What carries the argument

Simulation of a given k-Page Migration algorithm combined with one greedy move of a single server each round.

If this is right

Without the locality restriction, no constant competitive ratio exists even with augmentation.
Constant lower bounds on the competitive ratio exist that depend on k, m_s and m_c.
The resulting ratio is independent of the total number of requests n.
Any competitive algorithm for k-page migration immediately yields a competitive algorithm for the mobile-server setting with only polynomial blow-up in the stated parameters.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The simulation-plus-greedy technique may apply directly to other geometric online problems that already possess locality assumptions.
Selecting a known constant-competitive k-page migration algorithm would produce an explicit, though large, constant for the mobile-server case.
If real-world request patterns exhibit similar locality, the polynomial dependence on m_c/m_s suggests tuning server speed relative to request spacing.

Load-bearing premise

The adversary must produce request sequences in which each request lies at distance at most m_c from the previous request.

What would settle it

A concrete request sequence obeying the m_c locality condition on which the total cost of the constructed algorithm exceeds the claimed polynomial multiple of the optimal offline cost.

Figures

Figures reproduced from arXiv: 1907.09834 by Bj\"orn Feldkord, Friedhelm Meyer auf der Heide, Manuel Malatyali, Till Knollmann.

**Figure 1.** Figure 1: Example for a transition from oi to oj. By definition, r crosses the border of inner(oi) after time step t1 (oi passes r after t1). The transition stops at step t2 when r has entered innert2 (oj) (oj receives r in t2). Note that oj’s position and the radius of its inner circle may change from t1 to t2. The distance moved by r is at most (t2−t1)·mc. The dotted line represents the estimation of dt1 (oi , oj)… view at source ↗

**Figure 2.** Figure 2: The line as used in the proof of Theorem 2. The circles indicate a possible configuration of [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗

**Figure 3.** Figure 3: The construction of a transition path. The transition path is marked by black points, while [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗

read the original abstract

We extend the Mobile Server Problem, introduced in SPAA'17, to a model where k identical mobile resources, here named servers, answer requests appearing at points in the Euclidean space. In order to reduce communication costs, the positions of the servers can be adapted by a limited distance m_s per round for each server. The costs are measured similar to the classical Page Migration Problem, i.e., answering a request induces costs proportional to the distance to the nearest server, and moving a server induces costs proportional to the distance multiplied with a weight D. We show that, in our model, no online algorithm can have a constant competitive ratio, i.e., one which is independent of the input length n, even if an augmented moving distance of (1+\delta)m_s is allowed for the online algorithm. Therefore we investigate a restriction of the power of the adversary dictating the sequence of requests: We demand locality of requests, i.e., that consecutive requests come from points in the Euclidean space with distance bounded by some constant m_c. We show constant lower bounds on the competitiveness in this setting (independent of n, but dependent on k, m_s and m_c). On the positive side, we present a deterministic online algorithm with bounded competitiveness when augmented moving distance and locality of requests is assumed. Our algorithm simulates any given algorithm for the classical k-Page Migration problem as guidance for its servers and extends it by a greedy move of one server in every round. The resulting competitive ratio is polynomial in the number of servers k, the ratio between m_c and m_s, the inverse of the augmentation factor 1/\delta and the competitive ratio of the simulated k-Page Migration algorithm.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

No constant competitive ratio is possible without the locality restriction even with augmentation, but the simulation of any k-page migration algorithm plus one greedy move per round yields an explicit polynomial ratio when locality holds.

read the letter

The core result is that the k-server mobile model admits no constant-competitive online algorithm without restricting the adversary, even under (1+δ) movement augmentation. Once requests are forced to be m_c-local, constant lower bounds exist that depend on k, m_s and m_c, and a deterministic algorithm achieves a competitive ratio polynomial in k, m_c/m_s, 1/δ and the ratio of any simulated k-page migration algorithm. That is the punchline from the abstract and stress-test note. The construction is new relative to the single-server SPAA'17 paper: it runs an existing page-migration algorithm to decide server positions and adds one greedy server move toward the current request each round. The reduction is plausible because page-migration already handles the cost structure of moving resources with distance-weighted penalties. The paper does a clean job separating the unrestricted case from the local case and stating the bounds explicitly in terms of external parameters rather than fitting them to the algorithm itself. The lower-bound argument that locality is necessary looks standard and direct. The main soft spot is the polynomial dependence; the degree is not stated in the abstract, so it could be high, but the authors do not claim anything tighter and the approach does not hide circularity. The Euclidean setting is a modeling choice that fits the prior work, not a flaw. The citation pattern is appropriate, building on the cited single-server result and classical page migration. This is squarely for researchers in online algorithms who already care about k-server, page migration, or mobile resources. The claims are standard-style competitive-analysis results with both impossibility and a constructive upper bound, so the work is coherent on its own terms. I would send it to peer review; the central construction and the necessity of locality are worth a referee's time even if the polynomial is not optimal.

Referee Report

0 major / 2 minor

Summary. The paper extends the Mobile Server Problem to k identical mobile servers in Euclidean space, where each server can move at most distance m_s per round. It proves that no online algorithm achieves a competitive ratio independent of the input length n, even under (1+δ) augmentation. Under the additional m_c-locality restriction on the adversary (consecutive requests at distance ≤ m_c), the paper gives lower bounds depending on k, m_s and m_c, and constructs a deterministic online algorithm that simulates an arbitrary k-Page Migration algorithm while adding one greedy move per round; the resulting competitive ratio is polynomial in k, m_c/m_s, 1/δ and the ratio of the simulated algorithm.

Significance. If the claims hold, the work is significant for online algorithms on mobile resources: it cleanly separates the necessity of locality from the possibility of constant (parameter-dependent) competitiveness, and supplies a general simulation technique that inherits any future improvement to k-Page Migration. The explicit polynomial dependence and the reduction are strengths that make the result reusable.

minor comments (2)

[Abstract] Abstract: the positive result is stated only after the locality assumption is introduced; the abstract should explicitly qualify the bounded competitiveness claim with both the augmentation and the m_c-locality hypotheses.
[Model / Preliminaries] The model section should include a short paragraph recalling the definition of competitive ratio used for the k-Page Migration problem, to make the reduction self-contained.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; result reduces to external k-Page Migration ratio

full rationale

The derivation constructs a new algorithm by simulating any given k-Page Migration algorithm plus one greedy move per round. The claimed competitive ratio is explicitly a polynomial in k, m_c/m_s, 1/δ and the competitive ratio of that external simulated algorithm; it is not fitted to the target instance or defined in terms of itself. The paper separately proves that constant competitiveness is impossible without the m_c-locality restriction, so the restriction is an explicit modeling assumption rather than a hidden self-reference. No load-bearing step reduces by construction to a self-citation, fitted parameter, or renamed known result. The analysis is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the Euclidean metric, the standard definition of competitive ratio, and the locality restriction on the adversary. No free parameters are introduced; the model parameters m_s, m_c, D, δ are part of the problem statement.

axioms (2)

domain assumption Requests lie in Euclidean space and movement costs are proportional to Euclidean distance.
Stated in the model definition in the abstract.
standard math Competitive ratio is measured against an optimal offline solution that knows the entire request sequence in advance.
Implicit in all statements about competitive ratios.

pith-pipeline@v0.9.0 · 5845 in / 1465 out tokens · 18107 ms · 2026-05-24T17:06:43.064051+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages · 1 internal anchor

[1]

A polylogarithmic-competitive algorithm for thek-server problem

Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. A polylogarithmic-competitive algorithm for thek-server problem. J. ACM, 62(5):40:1–40:49, 2015

work page 2015
[2]

On page migration and other relaxed task systems

Yair Bartal, Moses Charikar, and Piotr Indyk. On page migration and other relaxed task systems. Theor. Comput. Sci., 268(1):43–66, 2001

work page 2001
[3]

On the competitive ratio of the work function algorithm for the k-server problem

Yair Bartal and Elias Koutsoupias. On the competitive ratio of the work function algorithm for the k-server problem. Theor. Comput. Sci., 324(2-3):337–345, 2004

work page 2004
[4]

Dynamic beats fixed: On phase-based algorithms for file migration

Marcin Bienkowski, Jaroslaw Byrka, and Marcin Mucha. Dynamic beats fixed: On phase-based algorithms for file migration. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), pages 13:1–13:14, 2017

work page 2017
[5]

Black and Daniel D

David L. Black and Daniel D. Sleator. Competitive algorithms for replication and migration problems. Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon University, 1989

work page 1989
[6]

Cohen, Yin Tat Lee, James R

S´ ebastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry. k-server via multiscale entropic regularization. InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 3–16, 2018

work page 2018
[7]

Karloff, T

Marek Chrobak, Howard J. Karloff, T. H. Payne, and Sundar Vishwanathan. New results on server problems. SIAM J. Discrete Math., 4(2):172–181, 1991

work page 1991
[8]

The mobile server problem

Bj¨ orn Feldkord and Friedhelm Meyer auf der Heide. The mobile server problem. InProceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SP AA), pages 313–319, 2017

work page 2017
[9]

The Mobile Server Problem

Bj¨ orn Feldkord and Friedhelm Meyer auf der Heide. The mobile server problem. CoRR, abs/1904.05220, 2019

work page internal anchor Pith review Pith/arXiv arXiv 1904
[10]

Karp, Michael Luby, Lyle A

Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, and Neal E. Young. Competitive paging algorithms.J. Algorithms, 12(4):685–699, 1991

work page 1991
[11]

Papadimitriou

Elias Koutsoupias and Christos H. Papadimitriou. On the k-server conjecture. J. ACM , 42(5):971–983, 1995

work page 1995
[12]

James R. Lee. Fusible hsts and the randomized k-server conjecture. In59th IEEE Annual Symposium on F oundations of Computer Science, FOCS 2018, Paris, F rance, October 7-9, 2018, pages 438–449, 2018. 13

work page 2018
[13]

Manasse, Lyle A

Mark S. Manasse, Lyle A. McGeoch, and Daniel Dominic Sleator. Competitive algorithms for server problems. J. Algorithms, 11(2):208–230, 1990

work page 1990
[14]

A fast work function algorithm for solving the k-server problem

Tomislav Rudec, Alfonzo Baumgartner, and Robert Manger. A fast work function algorithm for solving the k-server problem. CEJOR, 21(1):187–205, 2013

work page 2013
[15]

A fast approximate implementation of the work function algorithm for solving thek-server problem

Tomislav Rudec and Robert Manger. A fast approximate implementation of the work function algorithm for solving thek-server problem. CEJOR, 23(3):699–722, 2015

work page 2015
[16]

Westbrook

Jeffery R. Westbrook. Randomized algorithms for multiprocessor page migration.SIAM J. Comput., 23(5):951–965, 1994. 14 A Details of Section 3 A.1 Proof of Theorem 2 Figure 2: The line as used in the proof of Theorem 2. The circles indicate a possible configuration of the servers of the online algorithm and the optimal solution at the beginning of the seco...

work page 1994
[17]

107548·kmc δ2 <d(ˆa′,ˆo′): We show that the condition of Lemma 18 applies: d(ˆa′,ˆo′) ≤ d(a∗′ ,ˆo′) ≤ d(a∗′ ,a∗)+d(a∗,r′)+d(r′,ˆo′) ≤ mc+d(a∗,r′)+2· δ 48·d(o∗′ ,o∗a′ ) ≤ mc+d(a∗,r′)+ 2 47·d(ˆa′,ˆo′) ⇔ 45 47·d(ˆa′,ˆo′)−mc ≤ d(a∗,r′) ⇒ 102970kmc δ2 ≤ d(a∗,r′) 25 Hence the lemma gives us ∆φ ≤ 4· 1 δms ( d(ˆa′,ˆo′)2−d(ˆa,ˆo)2) ≤ 4· 1 δms ( d(ˆa′,ˆo′)2−(d(ˆa′,...

work page
[18]

In all of the following cases, we make use of ∆ψ = √ 24D ε (∑k i=1d(a′ i,c′ i)−∑k i=1d(ai,ci) ) ≤ √ 24D ε ∑k i=1d(ci,c′ i)+ √ 24D ε (∑k i=1d(a′ i,c′ i)−∑k i=1d(ai,c′ i) )

We have d(a′ 1, c′ 1)− d(a1, c′ 1)≤ min(mc, 1 D(1−ε)·d(˜a,r′)). In all of the following cases, we make use of ∆ψ = √ 24D ε (∑k i=1d(a′ i,c′ i)−∑k i=1d(ai,ci) ) ≤ √ 24D ε ∑k i=1d(ci,c′ i)+ √ 24D ε (∑k i=1d(a′ i,c′ i)−∑k i=1d(ai,c′ i) ) . We distinguish the following cases with respect to the positioning of the pages ofK:

work page
[21]

It follows CAlg≤ 3·d(c∗′ ,r′)+ D·∑k i=2d(ai,a′ i) and ∆ψ≤ √ 24D ε ∑k i=1d(ci,c′ i)+ √ 28 ε·d(c∗′ ,r′)−D·∑k i=2d(ai,a′ i)

≤ d(c∗′ ,r′). It follows CAlg≤ 3·d(c∗′ ,r′)+ D·∑k i=2d(ai,a′ i) and ∆ψ≤ √ 24D ε ∑k i=1d(ci,c′ i)+ √ 28 ε·d(c∗′ ,r′)−D·∑k i=2d(ai,a′ i). 26

work page
[23]

If d(a1,a′ 1)= mc then CAlg≤3Dmc+D·∑k i=2d(ai,a′ i), otherwise CAlg≤2·d(˜a,r′)+D·∑k i=2d(ai,a′ i)

=− 1√ 2·min(mc, 1 D(1− ε)· d(˜a,r′)) and hence ∆ψ≤ √ 24D ε ∑k i=1d(ci,c′ i)− 4D ε ·min(mc, 1 D(1−ε)·d(˜a,r′))−D·∑k i=2d(ai,a′ i). If d(a1,a′ 1)= mc then CAlg≤3Dmc+D·∑k i=2d(ai,a′ i), otherwise CAlg≤2·d(˜a,r′)+D·∑k i=2d(ai,a′ i)

work page
[24]

d(a∗′ ,r′)>d(c∗′ ,r′) and c∗′ ̸=c′ 1: We assume c∗′ = c′

work page
[25]

In the case d(a2,a′ 2)= 1 D·d(˜a,r′), d(a′ 1,c′ 1)−d(a1,c′ 1)+ d(a′ 2,c′ 2)−d(a2,c′ 2)≤− ε D·d(˜a,r′)

It must hold a′ 2̸= c′ 2 and hence d(c′ 2,a′ 2)−d(c′ 2,a2)≤−min(ms, 1 D·d(˜a,r′)). In the case d(a2,a′ 2)= 1 D·d(˜a,r′), d(a′ 1,c′ 1)−d(a1,c′ 1)+ d(a′ 2,c′ 2)−d(a2,c′ 2)≤− ε D·d(˜a,r′). This gives us ∆ψ≤ √ 24D ε (∑k i=1d(ci,c′ i)− ε D·d(˜a,r′)−∑k i=3d(ai,a′ i)). With CAlg = d(a′ 1,r′)+ D·∑k i=1d(ai,a′ i)≤ 3·d(˜a,r′)+D·∑k i=3d(ai,a′ i) the bound follows. I...

work page
[26]

d(a∗′ ,r′)≤d(c∗′ ,r′): Since we assumeD≥2, we have D·d(a1,a′

work page
[27]

≤ d(a1,r′) ≤ d(a1,a′ 1)+d(a′ 1,r′) ⇒ D 2·d(a1,a′

work page
[28]

It follows ∆ψ≤Y·D mc δms ∑k i=1d(ci,c′ i)+Y· mc δms·d(c∗′ ,r′)−D·∑k i=2d(ai,a′ i)

≤ d(c∗′ ,r′). It follows ∆ψ≤Y·D mc δms ∑k i=1d(ci,c′ i)+Y· mc δms·d(c∗′ ,r′)−D·∑k i=2d(ai,a′ i)

work page
[29]

d(a∗′ ,r′)>d(c∗′ ,r′) and c∗′ =c′ 1: We know that d(a′ 1,c′ 1)− d(a1,c′ 1)≤− 1√ 2· d(a1,a′

work page
[30]

and hence ∆ ψ≤ √ 24D ε ∑k i=1 d(ci,c′ i)− 4D ε · d(a1,a′ 1)−D·∑k i=2d(ai,a′ i)

work page
[31]

d(a∗′ ,r′)>d(c∗′ ,r′) and c∗′ ̸=c′ 1: We assumec∗′ =c′

work page
[32]

This gives us d(a′ 1,c′ 1)−d(a1,c′ 1)+d(a′ 2,c′ 2)−d(a2,c′ 2)≤−ε·d(a2,a′ 2)

It must hold a′ 2̸=c′ 2 and hence d(c′ 2,a′ 2)−d(c′ 2,a2)≤−min(ms, 1 D·d(˜a,r′)). This gives us d(a′ 1,c′ 1)−d(a1,c′ 1)+d(a′ 2,c′ 2)−d(a2,c′ 2)≤−ε·d(a2,a′ 2). It follows ∆ψ≤ √ 24D ε (∑k i=1d(ci,c′ i)− ε·d(a2,a′ 2)−∑k i=3d(ai,a′ i))≤ √ 24D ε ∑k i=1d(ci,c′ i)−D·∑k i=1d(ai,a′ i). C.4 Proof of Lemma 25 Lemma 25. If d(a∗′ ,r′)>d(c∗′ ,r′), then ∆ψ≤Y· mc δms CK−...

work page
[33]

Otherwise, we assumec∗′ = c′

= min((1+δ 2)ms, 1 D(1−δ 2)·d(˜a,r′)). Otherwise, we assumec∗′ = c′

work page
[34]

This gives us d(a′ 1, c′ 1)− d(a1, c′

It must hold a′ 2̸= c′ 2 and hence d(c′ 2,a′ 2)−d(c′ 2,a2)≤− min(ms, 1 D· d(˜a, r′)). This gives us d(a′ 1, c′ 1)− d(a1, c′

work page
[35]

It follows ∆ ψ≤ Y· D mc δms(∑k i=1 d(ci, c′ i)− δ 2· d(a2, a′ 2)−∑k i=3 d(ai, a′ i))≤ Y· D mc δms ∑k i=1 d(ci, c′ i)− D·∑k i=1 d(ai, a′ i)− Y−4 2 D mc δms·d(a2,a′ 2)

+ d(a′ 2, c′ 2)− d(a2, c′ 2)≤− δ 2· d(a2, a′ 2). It follows ∆ ψ≤ Y· D mc δms(∑k i=1 d(ci, c′ i)− δ 2· d(a2, a′ 2)−∑k i=3 d(ai, a′ i))≤ Y· D mc δms ∑k i=1 d(ci, c′ i)− D·∑k i=1 d(ai, a′ i)− Y−4 2 D mc δms·d(a2,a′ 2). C.5 Proof of Lemma 26 Lemma 26. If d(a∗,r′)>102970Dkmc δ2 and r′∈inner(o∗′ ), then d(a′ i,ˆo′)−d(ai,ˆo′)≤−δ 8ms. Proof. By our construction o...

work page
[36]

107548D·kmc δ2 <d(ˆa′,ˆo′): We show that the condition of Lemma 26 applies: d(ˆa′,ˆo′) ≤ d(a∗′ ,ˆo′) ≤ d(a∗′ ,a∗)+d(a∗,r′)+d(r′,ˆo′) ≤ mc+d(a∗,r′)+2· δ 48·d(o∗′ ,o∗a′ ) ≤ mc+d(a∗,r′)+ 2 47·d(ˆa′,ˆo′) ⇔ 45 47·d(ˆa′,ˆo′)−mc ≤ d(a∗,r′) ⇒ 102970Dkmc δ2 ≤ d(a∗,r′) Hence the lemma gives us ∆φ ≤ 4· 1 δms ( d(ˆa′,ˆo′)2−d(ˆa,ˆo)2) ≤ 4· 1 δms ( d(ˆa′,ˆo′)2−(d(ˆa′,ˆ...

work page

[1] [1]

A polylogarithmic-competitive algorithm for thek-server problem

Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. A polylogarithmic-competitive algorithm for thek-server problem. J. ACM, 62(5):40:1–40:49, 2015

work page 2015

[2] [2]

On page migration and other relaxed task systems

Yair Bartal, Moses Charikar, and Piotr Indyk. On page migration and other relaxed task systems. Theor. Comput. Sci., 268(1):43–66, 2001

work page 2001

[3] [3]

On the competitive ratio of the work function algorithm for the k-server problem

Yair Bartal and Elias Koutsoupias. On the competitive ratio of the work function algorithm for the k-server problem. Theor. Comput. Sci., 324(2-3):337–345, 2004

work page 2004

[4] [4]

Dynamic beats fixed: On phase-based algorithms for file migration

Marcin Bienkowski, Jaroslaw Byrka, and Marcin Mucha. Dynamic beats fixed: On phase-based algorithms for file migration. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), pages 13:1–13:14, 2017

work page 2017

[5] [5]

Black and Daniel D

David L. Black and Daniel D. Sleator. Competitive algorithms for replication and migration problems. Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon University, 1989

work page 1989

[6] [6]

Cohen, Yin Tat Lee, James R

S´ ebastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry. k-server via multiscale entropic regularization. InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 3–16, 2018

work page 2018

[7] [7]

Karloff, T

Marek Chrobak, Howard J. Karloff, T. H. Payne, and Sundar Vishwanathan. New results on server problems. SIAM J. Discrete Math., 4(2):172–181, 1991

work page 1991

[8] [8]

The mobile server problem

Bj¨ orn Feldkord and Friedhelm Meyer auf der Heide. The mobile server problem. InProceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SP AA), pages 313–319, 2017

work page 2017

[9] [9]

The Mobile Server Problem

Bj¨ orn Feldkord and Friedhelm Meyer auf der Heide. The mobile server problem. CoRR, abs/1904.05220, 2019

work page internal anchor Pith review Pith/arXiv arXiv 1904

[10] [10]

Karp, Michael Luby, Lyle A

Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, and Neal E. Young. Competitive paging algorithms.J. Algorithms, 12(4):685–699, 1991

work page 1991

[11] [11]

Papadimitriou

Elias Koutsoupias and Christos H. Papadimitriou. On the k-server conjecture. J. ACM , 42(5):971–983, 1995

work page 1995

[12] [12]

James R. Lee. Fusible hsts and the randomized k-server conjecture. In59th IEEE Annual Symposium on F oundations of Computer Science, FOCS 2018, Paris, F rance, October 7-9, 2018, pages 438–449, 2018. 13

work page 2018

[13] [13]

Manasse, Lyle A

Mark S. Manasse, Lyle A. McGeoch, and Daniel Dominic Sleator. Competitive algorithms for server problems. J. Algorithms, 11(2):208–230, 1990

work page 1990

[14] [14]

A fast work function algorithm for solving the k-server problem

Tomislav Rudec, Alfonzo Baumgartner, and Robert Manger. A fast work function algorithm for solving the k-server problem. CEJOR, 21(1):187–205, 2013

work page 2013

[15] [15]

A fast approximate implementation of the work function algorithm for solving thek-server problem

Tomislav Rudec and Robert Manger. A fast approximate implementation of the work function algorithm for solving thek-server problem. CEJOR, 23(3):699–722, 2015

work page 2015

[16] [16]

Westbrook

Jeffery R. Westbrook. Randomized algorithms for multiprocessor page migration.SIAM J. Comput., 23(5):951–965, 1994. 14 A Details of Section 3 A.1 Proof of Theorem 2 Figure 2: The line as used in the proof of Theorem 2. The circles indicate a possible configuration of the servers of the online algorithm and the optimal solution at the beginning of the seco...

work page 1994

[17] [17]

107548·kmc δ2 <d(ˆa′,ˆo′): We show that the condition of Lemma 18 applies: d(ˆa′,ˆo′) ≤ d(a∗′ ,ˆo′) ≤ d(a∗′ ,a∗)+d(a∗,r′)+d(r′,ˆo′) ≤ mc+d(a∗,r′)+2· δ 48·d(o∗′ ,o∗a′ ) ≤ mc+d(a∗,r′)+ 2 47·d(ˆa′,ˆo′) ⇔ 45 47·d(ˆa′,ˆo′)−mc ≤ d(a∗,r′) ⇒ 102970kmc δ2 ≤ d(a∗,r′) 25 Hence the lemma gives us ∆φ ≤ 4· 1 δms ( d(ˆa′,ˆo′)2−d(ˆa,ˆo)2) ≤ 4· 1 δms ( d(ˆa′,ˆo′)2−(d(ˆa′,...

work page

[18] [18]

In all of the following cases, we make use of ∆ψ = √ 24D ε (∑k i=1d(a′ i,c′ i)−∑k i=1d(ai,ci) ) ≤ √ 24D ε ∑k i=1d(ci,c′ i)+ √ 24D ε (∑k i=1d(a′ i,c′ i)−∑k i=1d(ai,c′ i) )

We have d(a′ 1, c′ 1)− d(a1, c′ 1)≤ min(mc, 1 D(1−ε)·d(˜a,r′)). In all of the following cases, we make use of ∆ψ = √ 24D ε (∑k i=1d(a′ i,c′ i)−∑k i=1d(ai,ci) ) ≤ √ 24D ε ∑k i=1d(ci,c′ i)+ √ 24D ε (∑k i=1d(a′ i,c′ i)−∑k i=1d(ai,c′ i) ) . We distinguish the following cases with respect to the positioning of the pages ofK:

work page

[19] [21]

It follows CAlg≤ 3·d(c∗′ ,r′)+ D·∑k i=2d(ai,a′ i) and ∆ψ≤ √ 24D ε ∑k i=1d(ci,c′ i)+ √ 28 ε·d(c∗′ ,r′)−D·∑k i=2d(ai,a′ i)

≤ d(c∗′ ,r′). It follows CAlg≤ 3·d(c∗′ ,r′)+ D·∑k i=2d(ai,a′ i) and ∆ψ≤ √ 24D ε ∑k i=1d(ci,c′ i)+ √ 28 ε·d(c∗′ ,r′)−D·∑k i=2d(ai,a′ i). 26

work page

[20] [23]

If d(a1,a′ 1)= mc then CAlg≤3Dmc+D·∑k i=2d(ai,a′ i), otherwise CAlg≤2·d(˜a,r′)+D·∑k i=2d(ai,a′ i)

=− 1√ 2·min(mc, 1 D(1− ε)· d(˜a,r′)) and hence ∆ψ≤ √ 24D ε ∑k i=1d(ci,c′ i)− 4D ε ·min(mc, 1 D(1−ε)·d(˜a,r′))−D·∑k i=2d(ai,a′ i). If d(a1,a′ 1)= mc then CAlg≤3Dmc+D·∑k i=2d(ai,a′ i), otherwise CAlg≤2·d(˜a,r′)+D·∑k i=2d(ai,a′ i)

work page

[21] [24]

d(a∗′ ,r′)>d(c∗′ ,r′) and c∗′ ̸=c′ 1: We assume c∗′ = c′

work page

[22] [25]

In the case d(a2,a′ 2)= 1 D·d(˜a,r′), d(a′ 1,c′ 1)−d(a1,c′ 1)+ d(a′ 2,c′ 2)−d(a2,c′ 2)≤− ε D·d(˜a,r′)

It must hold a′ 2̸= c′ 2 and hence d(c′ 2,a′ 2)−d(c′ 2,a2)≤−min(ms, 1 D·d(˜a,r′)). In the case d(a2,a′ 2)= 1 D·d(˜a,r′), d(a′ 1,c′ 1)−d(a1,c′ 1)+ d(a′ 2,c′ 2)−d(a2,c′ 2)≤− ε D·d(˜a,r′). This gives us ∆ψ≤ √ 24D ε (∑k i=1d(ci,c′ i)− ε D·d(˜a,r′)−∑k i=3d(ai,a′ i)). With CAlg = d(a′ 1,r′)+ D·∑k i=1d(ai,a′ i)≤ 3·d(˜a,r′)+D·∑k i=3d(ai,a′ i) the bound follows. I...

work page

[23] [26]

d(a∗′ ,r′)≤d(c∗′ ,r′): Since we assumeD≥2, we have D·d(a1,a′

work page

[24] [27]

≤ d(a1,r′) ≤ d(a1,a′ 1)+d(a′ 1,r′) ⇒ D 2·d(a1,a′

work page

[25] [28]

It follows ∆ψ≤Y·D mc δms ∑k i=1d(ci,c′ i)+Y· mc δms·d(c∗′ ,r′)−D·∑k i=2d(ai,a′ i)

≤ d(c∗′ ,r′). It follows ∆ψ≤Y·D mc δms ∑k i=1d(ci,c′ i)+Y· mc δms·d(c∗′ ,r′)−D·∑k i=2d(ai,a′ i)

work page

[26] [29]

d(a∗′ ,r′)>d(c∗′ ,r′) and c∗′ =c′ 1: We know that d(a′ 1,c′ 1)− d(a1,c′ 1)≤− 1√ 2· d(a1,a′

work page

[27] [30]

and hence ∆ ψ≤ √ 24D ε ∑k i=1 d(ci,c′ i)− 4D ε · d(a1,a′ 1)−D·∑k i=2d(ai,a′ i)

work page

[28] [31]

d(a∗′ ,r′)>d(c∗′ ,r′) and c∗′ ̸=c′ 1: We assumec∗′ =c′

work page

[29] [32]

This gives us d(a′ 1,c′ 1)−d(a1,c′ 1)+d(a′ 2,c′ 2)−d(a2,c′ 2)≤−ε·d(a2,a′ 2)

It must hold a′ 2̸=c′ 2 and hence d(c′ 2,a′ 2)−d(c′ 2,a2)≤−min(ms, 1 D·d(˜a,r′)). This gives us d(a′ 1,c′ 1)−d(a1,c′ 1)+d(a′ 2,c′ 2)−d(a2,c′ 2)≤−ε·d(a2,a′ 2). It follows ∆ψ≤ √ 24D ε (∑k i=1d(ci,c′ i)− ε·d(a2,a′ 2)−∑k i=3d(ai,a′ i))≤ √ 24D ε ∑k i=1d(ci,c′ i)−D·∑k i=1d(ai,a′ i). C.4 Proof of Lemma 25 Lemma 25. If d(a∗′ ,r′)>d(c∗′ ,r′), then ∆ψ≤Y· mc δms CK−...

work page

[30] [33]

Otherwise, we assumec∗′ = c′

= min((1+δ 2)ms, 1 D(1−δ 2)·d(˜a,r′)). Otherwise, we assumec∗′ = c′

work page

[31] [34]

This gives us d(a′ 1, c′ 1)− d(a1, c′

It must hold a′ 2̸= c′ 2 and hence d(c′ 2,a′ 2)−d(c′ 2,a2)≤− min(ms, 1 D· d(˜a, r′)). This gives us d(a′ 1, c′ 1)− d(a1, c′

work page

[32] [35]

It follows ∆ ψ≤ Y· D mc δms(∑k i=1 d(ci, c′ i)− δ 2· d(a2, a′ 2)−∑k i=3 d(ai, a′ i))≤ Y· D mc δms ∑k i=1 d(ci, c′ i)− D·∑k i=1 d(ai, a′ i)− Y−4 2 D mc δms·d(a2,a′ 2)

+ d(a′ 2, c′ 2)− d(a2, c′ 2)≤− δ 2· d(a2, a′ 2). It follows ∆ ψ≤ Y· D mc δms(∑k i=1 d(ci, c′ i)− δ 2· d(a2, a′ 2)−∑k i=3 d(ai, a′ i))≤ Y· D mc δms ∑k i=1 d(ci, c′ i)− D·∑k i=1 d(ai, a′ i)− Y−4 2 D mc δms·d(a2,a′ 2). C.5 Proof of Lemma 26 Lemma 26. If d(a∗,r′)>102970Dkmc δ2 and r′∈inner(o∗′ ), then d(a′ i,ˆo′)−d(ai,ˆo′)≤−δ 8ms. Proof. By our construction o...

work page

[33] [36]

107548D·kmc δ2 <d(ˆa′,ˆo′): We show that the condition of Lemma 26 applies: d(ˆa′,ˆo′) ≤ d(a∗′ ,ˆo′) ≤ d(a∗′ ,a∗)+d(a∗,r′)+d(r′,ˆo′) ≤ mc+d(a∗,r′)+2· δ 48·d(o∗′ ,o∗a′ ) ≤ mc+d(a∗,r′)+ 2 47·d(ˆa′,ˆo′) ⇔ 45 47·d(ˆa′,ˆo′)−mc ≤ d(a∗,r′) ⇒ 102970Dkmc δ2 ≤ d(a∗,r′) Hence the lemma gives us ∆φ ≤ 4· 1 δms ( d(ˆa′,ˆo′)2−d(ˆa,ˆo)2) ≤ 4· 1 δms ( d(ˆa′,ˆo′)2−(d(ˆa′,ˆ...

work page