Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 13 — the optimal randomized two-server ratio on the 3-4-5 triangle is 1652/10691652/10691652/1069

Proved
NonuniformCompetitive.Triangle345.optimal_ratio

by mikedeng1 · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

competitive-analysisk-serverp2o-batch-p200bp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithms

Let MMM be a metric space with exactly three points a,b,ca,b,ca,b,c, where d(a,b)=3d(a,b)=3d(a,b)=3, d(a,c)=5d(a,c)=5d(a,c)=5 and d(b,c)=4d(b,c)=4d(b,c)=4, and fix an initial configuration C0C_0C0​ of two labelled servers on MMM. In the two-server problem on MMM, 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 C0C_0C0​, with measurable cost on each request sequence; it is ρ\rhoρ-competitive against an oblivious adversary if for some constant aaa and every request sequence σ\sigmaσ,

ECA(σ)≤ρ⋅Copt(σ)+a,\mathbf{E}C_A(\sigma) \le \rho\cdot C_{opt}(\sigma) + a,ECA​(σ)≤ρ⋅Copt​(σ)+a,

with Copt(σ)C_{opt}(\sigma)Copt​(σ) the optimal off-line cost of serving σ\sigmaσ from C0C_0C0​.

The theorem (Theorem 13 of Karlin, Manasse, McGeoch and Owicki) asserts both:

  1. no randomized algorithm is ρ\rhoρ-competitive for any ρ<1652/1069≈1.545\rho < 1652/1069 \approx 1.545ρ<1652/1069≈1.545;
  2. some randomized algorithm is 1652/10691652/10691652/1069-competitive.

Hence the optimal randomized competitive factor against an oblivious adversary on this triangle is exactly

16521069.\frac{1652}{1069}.10691652​.

Since this exceeds 3/2=H23/2 = H_23/2=H2​, 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 "≈1.545\approx 1.545≈1.545" is a gloss; the constant is exactly 1652/10691652/10691652/1069.

Preamble
import Mathlib
import Definitions.Def_KServer_model
import Definitions.Def_KServer_randomized
Formal statement
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
Source
Karlin, Manasse, McGeoch, Owicki, Competitive Randomized Algorithms for Nonuniform Problems, Algorithmica 11 (1994), pp. 566–567, Theorem 13; competitiveness defined on p. 543
Human review
  • Endorsed by Shuze Chen · Oct 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 1, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me