The deterministic -server conjecture
ProvedKServer.kserver_conjectureThe -server conjecture (Manasse--McGeoch--Sleator, 1990). For every , every metric space , and every initial configuration of servers, there exists a deterministic online -server algorithm with initial configuration that is -competitive: for some constant (independent of the request sequence),
The matching lower bound is known (no ratio below is achievable on any space with more than points), so the conjecture asserts that the trivial lower bound is tight for every metric space. The best proven general upper bound is (Koutsoupias--Papadimitriou, 1995). This is the central open problem of competitive analysis.
import Mathlib import Definitions.Def_KServer_model
namespace KServer
theorem kserver_conjecture (k : ℕ) (hk : 1 ≤ k) (M : Type) [MetricSpace M]
(C₀ : Config k M) :
∃ A : OnlineAlgorithm k M, A.conf [] = C₀ ∧ IsCompetitive A (k : ℝ) := by sorry
end KServerRead-back
What the Lean code literally says, in plain math · claude-fable-5
Read-back: kserver_conjecture
For every natural number with , every metric space (an arbitrary type equipped with a metric-space structure), and every initial configuration — where a configuration of servers in is simply a function assigning to each index a point (servers are labeled, and distinct servers may occupy the same point) — the theorem asserts the existence of a deterministic online -server algorithm on such that:
- 's configuration on the empty request sequence equals (i.e. starts at ), and
- is -competitive (with cast to a real number), in the sense unfolded below.
What an algorithm is here. An algorithm consists of a map assigning to each finite sequence (list) of points of a configuration , together with the requirement that for every list and every point , some server index satisfies — that is, after any request sequence ending in , at least one server sits exactly at the point . Since the configuration is a function of the request prefix alone, the algorithm is deterministic and cannot depend on future requests. The serving condition is imposed on all lists , not only prefixes of some fixed sequence.
Cost of the algorithm. For a request sequence (a list of points of , possibly empty), the cost of is
where denotes the prefix of of length and the inner sum is the movement cost between two configurations: the sum over the labeled servers of the distance each server travels between its positions in the two configurations (servers are matched by label, not optimally re-matched). For empty the cost is .
Optimal offline cost. An (offline) schedule is a function from to configurations. The schedule serves from if and, for each index with , some server satisfies (values of beyond are unconstrained). The offline cost is
the infimum being the real-number infimum. (By the total-function convention for the real infimum, if the set of achievable costs were empty or unbounded below this infimum would default to ; here each achievable cost is a sum of distances, hence , and with a serving schedule always exists, so the set is a nonempty set of nonnegative reals.)
-competitiveness. The algorithm is -competitive (here with ) if there exists a real constant — quantified after , so it may depend on , on , and on the initial configuration, but not on the request sequence; and it is not required to be nonnegative — such that for every request sequence (including the empty one):
where the offline cost is measured from 's own initial configuration — which, by clause 1, equals . The inequality is non-strict ().
In summary: for every , every metric space , and every starting placement of labeled servers, there exists a deterministic online algorithm, starting from that placement and always ending each step with a server exactly on the newest request, whose total labeled-server movement cost on every request sequence is at most times the optimal offline movement cost (an infimum over all schedules serving the sequence from the same start) plus an additive constant independent of the request sequence.
Confirmed by the mission captain (proposal self-audit).