Theorem 3 — no online algorithm beats 26/27 on a 6-cycle, and none reaches 1 − o(1) on k disjoint 6-cycles
ProvedOnlineStochMatching.Hardness.theorem_3This is Theorem 3 of Feldman, Mehta, Mirrokni and Muthukrishnan, in two parts.
- A single instance. On the 6-cycle instance (advertisers , impression types , edges , uniform distribution, ), every randomized online algorithm has
- A family with . For let be the instance made of disjoint copies of the 6-cycle, with the uniform distribution on its impression types and arrivals. There are a constant and a threshold such that for every and every randomized online algorithm on ,
The paper writes the second part as "there exists a family of instances with for which no algorithm can achieve an expected approximation of "; part 2 is the explicit form of that statement on the paper's own family: the best achievable expected approximation factor on stays below a fixed constant smaller than for all large , so it does not tend to .
The theorem shows that the expected approximation factor of online algorithms in the i.i.d. model is bounded strictly away from , which separates the problem from its offline version and frames the paper's positive results ( and ).
Formalization Note Expectations are over the algorithm's randomness (a probability distribution on deterministic online algorithms) and the uniform i.i.d. arrivals. The constant and the threshold are chosen before and before the algorithm. The paper's numerical value (Appendix B) rests on approximations and is not part of the statement. On these instances every impression type has an adjacent advertiser, so on every arrival sequence and the ratio is never .
import Mathlib import Definitions.Def_OnlineStochMatching_Hardness_Model import Definitions.Def_OnlineStochMatching_Hardness_SixCycle
namespace OnlineStochMatching.Hardness
/-- Theorem 3 (p. 4; details App. B, p. 13). (a) On the 6-cycle instance (`n = 3`), no randomized
online algorithm has expected approximation factor above `26/27`. (b) On the family of `k`
disjoint 6-cycles with uniform arrivals and `n = 3k`, there is a constant `c < 1` such that for
all large `k` no randomized online algorithm has expected approximation factor above `c`; so
the best achievable expected factor does not tend to `1` as `n → ∞`. -/
theorem theorem_3 :
(∀ P : PMF (OnlineAlg Adv Imp 3), randExpectedRatio cycleEdge P ≤ 26 / 27) ∧
∃ c : ℝ, c < 1 ∧ ∃ K₀ : ℕ, ∀ k : ℕ, K₀ ≤ k →
∀ P : PMF (OnlineAlg (Fin k × Adv) (Fin k × Imp) (3 * k)),
randExpectedRatio (kCycleEdge k) P ≤ c := by sorry
end OnlineStochMatching.Hardness
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.