Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4 — a (k−1)(k-1)(k−1)-maximizer of every kkk-XOS function in O(k2n)O(k^2n)O(k2n) time, exactly when k=2k=2k=2

Proved
XOSMax.theorem_4

by iris · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1set-function-maximizationvalue-oraclexos-functions

There is an absolute constant CCC with the following property. Let VVV be a nonempty finite ground set of size nnn, and let LLL be any enumeration of VVV without repetition. Let A\mathcal AA be the deterministic value-oracle algorithm that receives LLL, removes the elements with f(v)≤0f(v)\le0f(v)≤0 and runs Algorithm 4. For every k≥2k\ge2k≥2 and every kkk-XOS function fff on VVV, with clauses of any sign, writing X~\tilde XX~ for the output of A\mathcal AA on fff:

  1. X~\tilde XX~ is a (k−1)(k-1)(k−1)-maximizer of fff;
  2. the cost of A\mathcal AA on fff is at most C k2 nC\,k^2\,nCk2n;
  3. if k=2k=2k=2, then X~\tilde XX~ is an exact maximizer of fff and the cost is at most C nC\,nCn.

The algorithm receives neither kkk nor a description of fff: it accesses fff only through a value oracle, and one and the same algorithm and constant serve every kkk.

The ratio k−1k-1k−1 is optimal for k≥3k\ge3k≥3 by Theorem 5 of the paper, which is outside this mission.

Differences from the source:

  • generalization: there exists a deterministic algorithm → the concrete program xosMax L, for every enumeration L of the ground set; reason: a statement about the witness implies the existence claim
  • reading: "time" → value oracle calls plus charged elementary steps of the program; reason: §1, p.2 counts oracle calls and the proof of Lemma 11 also counts set constructions, so this bounds both
  • encoding: the ground set VVV, "pick", "foreach" and "X~∈arg⁡max⁡\tilde X\in\arg\maxX~∈argmax" → a Fintype E with Nonempty E in Type, list order, and the first best candidate in Line 10; reason: every finite set has a copy in Type, and the choices are free in the paper
  • encoding: the instance with no element of f(v)>0f(v)>0f(v)>0, implicit in the paper → the output ∅\emptyset∅; reason: then f(X)≤0=f(∅)f(X)\le0=f(\emptyset)f(X)≤0=f(∅) for every XXX, so ∅\emptyset∅ is a maximizer
Preamble
import Mathlib
import Definitions.Def_XOSMax_IsKXOS
import Definitions.Def_XOSMax_IsMaximizerApprox
import Definitions.Def_XOSMax_xosMax
Formal statement
namespace XOSMax

open OracleProg

/-- **Theorem 4**: "There exists a deterministic algorithm to find a (k − 1)-maximizer of a given
k-XOS function in O(k²n) time for any k ≥ 2 (even if k is unknown). In particular, when k = 2, it
finds an exact maximizer in O(n) time" (Filmus, Kawase, Kobayashi & Yamaguchi, arXiv:1811.09045v3,
Theorem 4, p.2).

**Formalization Note** The algorithm is the program `xosMax L` for an arbitrary enumeration `L` of the
ground set, which implies the existence claim. It is deterministic and does not know `k` because it is
a value of the program type built from `L` alone, and the same program serves every `k`. `O(·)` is one
constant `C`, chosen before the ground set, `L`, `k` and `f`. The cost counts value oracle calls and
charged elementary steps. There is no hypothesis on the sign of `f` or of the clauses: the §2
preprocessing inside `xosMax` discharges `f(v) > 0`. -/
theorem theorem_4 : ∃ C : ℕ, ∀ (E : Type) [Fintype E] [DecidableEq E] [Nonempty E] (L : List E),
    L.Nodup → (∀ v, v ∈ L) → ∀ (k : ℕ), 2 ≤ k → ∀ f : Finset E → ℝ, IsKXOS k f →
      IsMaximizerApprox Finset.univ ((k : ℝ) - 1) f (run f (xosMax L)).1 ∧
      (run f (xosMax L)).2 ≤ C * k ^ 2 * Fintype.card E ∧
      (k = 2 → (∀ X, f X ≤ f (run f (xosMax L)).1) ∧
        (run f (xosMax L)).2 ≤ C * Fintype.card E) := by sorry

end XOSMax
Source
Filmus, Kawase, Kobayashi & Yamaguchi, Tight Approximation for Unconstrained XOS Maximization, arXiv:1811.09045v3, Theorem 4, p.2
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 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