Theorem 12 — the optimal randomized two-server ratio on the 1-d-d isosceles triangle is
ProvedNonuniformCompetitive.Isosceles.optimal_ratioLet be an integer and let be the isosceles triangle with edge lengths , , : a metric space consisting of exactly three points , , with
In the two-server problem on , two mobile servers occupy points of ; each request names a point, which must be covered by a server after the request is served, and the cost is the total distance the servers move. A randomized on-line algorithm is a probability distribution over deterministic on-line algorithms (each of which decides its configuration from the requests seen so far), and its expected cost on a request sequence is . Such an algorithm is -competitive against an oblivious adversary from the initial configuration if every algorithm in its support starts in and there is a constant such that, for every finite request sequence ,
where is the least cost of serving from with full knowledge of .
Write and
Theorem 12. For every initial configuration of the two servers:
- no randomized on-line algorithm is competitive against an oblivious adversary from within a factor less than
that is, if is -competitive from then ; 2. there is a randomized on-line algorithm that is -competitive against an oblivious adversary from .
The ratio equals on the equilateral triangle (), increases with , and tends to . The deterministic optimal ratio on every such triangle is , so randomization strictly helps.
Formalization Note The model is the platform's published KServer_model and KServer_randomized (labelled servers Fin 2 → M, a randomized algorithm as a probability measure over deterministic on-line algorithms whose cost on each sequence is measurable, expected cost as a lower Lebesgue integral in , the off-line optimum as a real infimum over schedules starting at ). The triangle is any metric space whose points are exactly at the stated distances; every such space is isometric to the paper's triangle. The claim is stated for every initial configuration , including both servers on one point; the paper's argument absorbs the initial partial phase into the additive constant.
import Mathlib import Definitions.Def_KServer_model import Definitions.Def_KServer_randomized import Definitions.Def_NonuniformCompetitive_Isosceles_isoscelesRatio
namespace NonuniformCompetitive.Isosceles
/-- Theorem 12 (Karlin–Manasse–McGeoch–Owicki, Competitive Randomized Algorithms for Nonuniform
Problems, Algorithmica 11 (1994), p. 564). Consider the two-server problem on an isosceles
triangle with integer edge lengths `1, d, d` (`1 ≤ d`): a metric space consisting of exactly the
three points `a, b, c` with `dist a b = 1` and `dist a c = dist b c = d`. From every initial
configuration `C₀` of the two servers:
1. no randomized algorithm is competitive against an oblivious adversary within a factor less
than `(e_{2d-1} + 1/(4d)) / ((e_{2d-1} - 1) + 1/(2d))`, and
2. some randomized algorithm achieves this competitive factor. -/
theorem optimal_ratio {M : Type} [MetricSpace M] (d : ℕ) (hd : 1 ≤ d) (a b c : M)
(hM : ∀ x : M, x = a ∨ x = b ∨ x = c)
(hab : dist a b = 1) (hac : dist a c = d) (hbc : dist b c = d)
(C₀ : KServer.Config 2 M) :
(∀ (A : KServer.RandomizedAlgorithm 2 M) (ρ : ℝ), A.IsCompetitiveFrom C₀ ρ →
isoscelesRatio d ≤ ρ) ∧
∃ A : KServer.RandomizedAlgorithm 2 M, A.IsCompetitiveFrom C₀ (isoscelesRatio d) := by sorry
end NonuniformCompetitive.Isosceles
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.