Theorem 4 — a -maximizer of every -XOS function in time, exactly when
ProvedXOSMax.theorem_4approximation-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1set-function-maximizationvalue-oraclexos-functions
There is an absolute constant with the following property. Let be a nonempty finite ground set of size , and let be any enumeration of without repetition. Let be the deterministic value-oracle algorithm that receives , removes the elements with and runs Algorithm 4. For every and every -XOS function on , with clauses of any sign, writing for the output of on :
- is a -maximizer of ;
- the cost of on is at most ;
- if , then is an exact maximizer of and the cost is at most .
The algorithm receives neither nor a description of : it accesses only through a value oracle, and one and the same algorithm and constant serve every .
The ratio is optimal for 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 enumerationLof 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 , "pick", "foreach" and "" → a
Fintype EwithNonempty EinType, list order, and the first best candidate in Line 10; reason: every finite set has a copy inType, and the choices are free in the paper - encoding: the instance with no element of , implicit in the paper → the output ; reason: then for every , so 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.