Theorem 4 — a (15 + ε)-approximation for FL-MI with group constraints and non-uniform opening costs
OpenFacilityIncompatibilities.UniformMatroid.Supplement.theorem_4Fix . There are a deterministic oracle Turing machine and a polynomial such that the following holds for every FL-MI instance with clients and facilities, given by rational distances forming a (pseudo)metric and rational opening costs (arbitrary, not necessarily equal), whose client matroid (ground set ) is a partition matroid, and in which is feasible. Run on the input word of length with the independence oracle of , the machine halts within steps and outputs a facility set together with a feasible assignment (every independent in ) with
Here is the minimum cost of a feasible solution of the instance. The machine and the polynomial depend on only, not on the instance, the matroid or its groups; the algorithm sees the matroid only through the oracle.
This is the paper's companion result for non-uniform opening costs; the mission's goal, Theorem 3, treats a general matroid with uniform opening costs.
Formalization Note The input word encodes , , the distance table and the opening costs; the output word is the characteristic vector of followed by the code of every . Each oracle answer counts as one step. is in ℝ≥0∞. The hypothesis that is feasible is the paper's standing assumption (printed p.2).
Differences from the source:
- generalization: metric distances d (Definition 1) → a pseudometric (distinct points may be at distance 0); reason: every metric satisfies these axioms, so every instance of the source is covered
- encoding: "there exists a (15 + ε)-approximation algorithm" with polynomially many oracle calls and polynomial running time in |V_C|, |V_F| and the bit length of the data (printed p.2) → one oracle Turing machine T and one polynomial p, chosen after ε, with T halting within p(input length) steps on every instance and outputting an encoded feasible solution of cost ≤ (15 + ε)·OPT; reason: the input length is at least |V_C| + |V_F| and at most polynomial in them and the bit length, so the two time bounds are equivalent
- encoding: groups G_g with bounds b_g ≥ 0 (Definition 2) → a label map grp : Fin n → Fin n and bounds b : Fin n → ℕ; reason: a partition of n clients has at most n nonempty parts and a cardinality bound is equivalent to its integer part
import Mathlib import Definitions.Def_FacilityIncompatibilities_UniformMatroid_Supplement_NonUniform open scoped ENNReal
namespace FacilityIncompatibilities.UniformMatroid.Supplement
/-- **Theorem 4** (printed p.4 / PDF p.5): there exists a `(15 + ε)`-approximation algorithm for
FL-MI with group constraints and non-uniform facility-opening costs.
For every fixed `ε > 0` there are one deterministic oracle Turing machine `T` and one polynomial
`p` such that, for every rationally encoded instance with per-facility opening costs (metric
data, `f ≥ 0`, `V_F` feasible) and every client matroid `M` on exactly the clients that is a
partition matroid, the run of `T` with the independence oracle of `M` on the encoded instance
halts within `p(B)` steps (`B` the input length; every oracle answer counts one step) and outputs
the code of a facility set `S` with a feasible assignment `σ : V_C → S` of total cost at most
`(15 + ε) · OPT`. -/
theorem theorem_4 (ε : ℝ) (hε : 0 < ε) :
∃ (T : QAdvFew.PoQOracle.OTM) (p : Polynomial ℕ),
∀ (E : NUEncodedInstance) (M : Matroid (Fin E.n)),
(E.toInstance M).Valid → IsPartitionMatroid M →
(E.toInstance M).IsFeasible Finset.univ →
∃ t : ℕ, t ≤ p.eval E.encode.length ∧
T.result (indepOracle M) E.encode t ≠ none ∧
∃ (S : Finset (Fin E.m)) (σ : Fin E.n → Fin E.m),
T.output (indepOracle M) E.encode t = encodeSolution S σ ∧
(E.toInstance M).IsFeasibleAssignment S σ ∧
ENNReal.ofReal ((E.toInstance M).solCost S σ) ≤
ENNReal.ofReal (15 + ε) * (E.toInstance M).OPT := by sorry
end FacilityIncompatibilities.UniformMatroid.Supplement