Theorem 13 — the optimal randomized two-server ratio on the 3-4-5 triangle is
ProvedNonuniformCompetitive.Triangle345.optimal_ratioLet be a metric space with exactly three points , where , and , and fix an initial configuration of two labelled servers on . In the two-server problem on , each request must be covered by a server once it is issued, and the cost is the total distance moved by the servers. A randomized on-line algorithm is a probability distribution over deterministic on-line algorithms starting in , with measurable cost on each request sequence; it is -competitive against an oblivious adversary if for some constant and every request sequence ,
with the optimal off-line cost of serving from .
The theorem (Theorem 13 of Karlin, Manasse, McGeoch and Owicki) asserts both:
- no randomized algorithm is -competitive for any ;
- some randomized algorithm is -competitive.
Hence the optimal randomized competitive factor against an oblivious adversary on this triangle is exactly
Since this exceeds , it shows that the harmonic-number bounds known for paging on uniform spaces do not extend to non-uniform metric spaces.
Formalization Note The model is the platform's KServer_model / KServer_randomized. The triangle is encoded by hypotheses on an arbitrary metric space. Both claims are stated for every initial configuration, including both servers on one point; the additive constant absorbs the start. The paper's "" is a gloss; the constant is exactly .
import Mathlib import Definitions.Def_KServer_model import Definitions.Def_KServer_randomized
namespace NonuniformCompetitive.Triangle345
/-- Karlin–Manasse–McGeoch–Owicki (Algorithmica 11, 1994), Theorem 13 (pp. 566–567): on the
triangle with edge lengths 3, 4, 5 (`d(a,b) = 3`, `d(a,c) = 5`, `d(b,c) = 4`), the optimal
randomized competitive factor of the two-server problem against an oblivious adversary is exactly
`1652/1069`: no randomized algorithm starting from `C₀` is competitive within a smaller factor,
and some randomized algorithm starting from `C₀` achieves it. Stated for every initial
configuration `C₀`. -/
theorem optimal_ratio
{M : Type} [MetricSpace M] (a b c : M) (hM : ∀ x : M, x = a ∨ x = b ∨ x = c)
(hab : dist a b = 3) (hac : dist a c = 5) (hbc : dist b c = 4)
(C₀ : KServer.Config 2 M) :
(∀ (A : KServer.RandomizedAlgorithm 2 M) (ρ : ℝ), A.IsCompetitiveFrom C₀ ρ → (1652 / 1069 : ℝ) ≤ ρ) ∧
∃ A : KServer.RandomizedAlgorithm 2 M, A.IsCompetitiveFrom C₀ (1652 / 1069) := by sorry
end NonuniformCompetitive.Triangle345
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.