online_cycle_augmentation_reduction_to_tl_hitting_set
Let n be a natural number, L a finite set of pairs (i, j) of integers satisfying 0 ≤ i < j < n, w a real cost function on pairs, and α a real number. If an online algorithm Alg maintaining subsets of L irrevocably (Alg reqs ⊆ L and Alg reqs ⊆ Alg (reqs ++ [r])) is feasible and α-competitive for hitting arriving TL-rectangles ((p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2)) for all valid cut sequences (1 ≤ c.1 ≤ c.2 < n), then Alg is also feasible and α-competitive for covering all arriving cuts ((c.1 ≤ p.1 ∧ p.1 ≤ c.2) ↔ ¬(c.1 ≤ p.2 ∧ p.2 ≤ c.2)) in Online Cycle Augmentation.
Statement
open Finset BigOperators in theorem online_cycle_augmentation_reduction_to_tl_hitting_set (n : ℕ) (L : Finset (ℤ × ℤ)) (hL : ∀ p ∈ L, 0 ≤ p.1 ∧ p.1 < p.2 ∧ p.2 < (n : ℤ)) (w : (ℤ × ℤ) → ℝ) (α : ℝ) (Alg : List (ℤ × ℤ) → Finset (ℤ × ℤ)) (h_online : (∀ reqs, Alg reqs ⊆ L) ∧ (∀ reqs r, Alg reqs ⊆ Alg (reqs ++ [r]))) (h_tl_hit : ∀ reqs, (∀ c ∈ reqs, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) → ∀ c ∈ reqs, ∃ p ∈ Alg reqs, (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2)) (h_tl_comp : ∀ reqs, (∀ c ∈ reqs, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) → ∀ F ⊆ L, (∀ c ∈ reqs, ∃ p ∈ F, (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2)) → ∑ p ∈ Alg reqs, w p ≤ α * ∑ p ∈ F, w p) : ((∀ cuts, (∀ c ∈ cuts, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) → ∀ c ∈ cuts, ∃ p ∈ Alg cuts, ((c.1 ≤ p.1 ∧ p.1 ≤ c.2) ↔ ¬(c.1 ≤ p.2 ∧ p.2 ≤ c.2))) ∧ ∀ cuts, (∀ c ∈ cuts, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) → ∀ F ⊆ L, (∀ c ∈ cuts, ∃ p ∈ F, ((c.1 ≤ p.1 ∧ p.1 ≤ c.2) ↔ ¬(c.1 ≤ p.2 ∧ p.2 ≤ c.2))) → ∑ p ∈ Alg cuts, w p ≤ α * ∑ p ∈ F, w p)
- Formalizes
- arXiv:2611.08570 Theorem 1.10
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- cycle_link_crosses_cut_iff_tl_rectFor integers i, j, a, b, n satisfying 0 ≤ i < j < n and 1 ≤ a ≤ b < n, candidate link (i, j) crosses cycle cut [a, b] (meaning (a ≤ i ∧ i…
- card_candidate_links_le_sqFor every natural number n and every finite set L of pairs of integers (i, j) satisfying 0 ≤ i < j < n, the cardinality of L is at most n…
Read back from the Lean
Given:
- a natural number n,
- a finite set of integer pairs L : Finset (ℤ × ℤ) such that for every p ∈ L, 0 ≤ p.1 < p.2 < n,
- a weight function w : (ℤ × ℤ) → ℝ,
- a real number α,
- an algorithm Alg : List (ℤ × ℤ) → Finset (ℤ × ℤ),
- a hypothesis h_online asserting that for every list reqs, Alg reqs ⊆ L, and for every list reqs and pair r, Alg reqs ⊆ Alg (reqs ++ [r]),
- a hypothesis h_tl_hit asserting that for every list reqs of integer pairs, if every c ∈ reqs satisfies 1 ≤ c.1 ≤ c.2 < n, then for every c ∈ reqs, there exists p ∈ Alg reqs such that either (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) or (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2),
- a hypothesis h_tl_comp asserting that for every list reqs where every c ∈ reqs satisfies 1 ≤ c.1 ≤ c.2 < n, and for every sub-finset F ⊆ L, if for every c ∈ reqs there exists p ∈ F satisfying (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2), then ∑ p ∈ Alg reqs, w p ≤ α * ∑ p ∈ F, w p,
the theorem asserts that:
1. For every list cuts, if every c ∈ cuts satisfies 1 ≤ c.1 ≤ c.2 < n, then for every c ∈ cuts, there exists p ∈ Alg cuts such that (c.1 ≤ p.1 ∧ p.1 ≤ c.2) ↔ ¬(c.1 ≤ p.2 ∧ p.2 ≤ c.2) (that is, exactly one of p.1, p.2 lies in [c.1, c.2]), and
2. For every list cuts, if every c ∈ cuts satisfies 1 ≤ c.1 ≤ c.2 < n, then for every F ⊆ L, if every c ∈ cuts has some p ∈ F satisfying (c.1 ≤ p.1 ∧ p.1 ≤ c.2) ↔ ¬(c.1 ≤ p.2 ∧ p.2 ≤ c.2), then ∑ p ∈ Alg cuts, w p ≤ α * ∑ p ∈ F, w p.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem reduces Online Cycle Augmentation to the online hitting set problem for top-left (TL) rectangles. The reduction relies on lemma cycle_link_crosses_cut_iff_tl_rect, which establishes that a cycle link crosses an interval cut if and only if the link hits the cut's corresponding TL-rectangle. Feasibility holds because the online algorithm hits every arriving TL-rectangle, which translates directly to crossing every arriving cut. Competitiveness follows because any valid offline cut cover is also a valid hitting set for the TL-rectangles, transferring the competitive ratio directly.
Alg is feasible for Online Cycle Augmentation: for any valid cut sequence, every cut is crossed by an edge chosen by Alg.
The theorem splits into two parts: feasibility and competitiveness. For feasibility, consider any valid cut sequence and cut c. By the TL-hitting feasibility assumption (h_tl_hit), Alg selects an edge p hitting the TL-rectangle of c. Since Alg only purchases edges from the pool L (by h_online), p satisfies the bounds 0 ≤ p.1 < p.2 < n. By lemma cycle_link_crosses_cut_iff_tl_rect, hitting the TL-rectangle is equivalent to crossing the cut c, so p crosses c.
uses
cycle_link_crosses_cut_iff_tl_rectconstructor · intro cuts hcuts c hc obtain ⟨p, hp, h_rect⟩ := h_tl_hit cuts hcuts c hc have hpL : p ∈ L := h_online.1 cuts hp have hp_valid := hL p hpL have hc_valid := hcuts c hc have h_equiv := cycle_link_crosses_cut_iff_tl_rect p.1 p.2 c.1 c.2 (n : ℤ) hp_valid hc_valid refine ⟨p, hp, ?_⟩ exact h_equiv.mpr h_rect
Alg is α-competitive for Online Cycle Augmentation: its cost on any cut sequence is at most α times the cost of any feasible cut-covering edge set F ⊆ L.
Let F ⊆ L be any offline edge set that covers all cuts in the sequence. For each cut c, some edge p ∈ F crosses c. Because p ∈ L, lemma cycle_link_crosses_cut_iff_tl_rect implies that p also hits the TL-rectangle of c. Thus F is a feasible hitting set for all arriving TL-rectangles. We then apply the assumed α-competitiveness of Alg for hitting TL-rectangles (h_tl_comp) against F to conclude that the total weight of edges chosen by Alg is at most α times the total weight of F.
uses
cycle_link_crosses_cut_iff_tl_rect· intro cuts hcuts F hFL hF_cross have hF_tl : ∀ c ∈ cuts, ∃ p ∈ F, (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2) := by intro c hc obtain ⟨p, hp, h_cross⟩ := hF_cross c hc have hpL : p ∈ L := hFL hp have hp_valid := hL p hpL have hc_valid := hcuts c hc have h_equiv := cycle_link_crosses_cut_iff_tl_rect p.1 p.2 c.1 c.2 (n : ℤ) hp_valid hc_valid refine ⟨p, hp, ?_⟩ exact h_equiv.mp h_cross exact h_tl_comp cuts hcuts F hFL hF_tl
cycle_link_crosses_cut_iff_tl_rect- An edge (i, j) with 0 ≤ i < j < n crosses an interval cut [a, b] with 1 ≤ a ≤ b < n (that is, exactly one endpoint lies in [a, b]) if and only if (i, j) hits the top-left (TL) rectangle: either i ≤ a - 1 ∧ a ≤ j ≤ b, or a ≤ i ≤ b ∧ b + 1 ≤ j.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finset BigOperators in/-- Theorem 1.10: An α-competitive online algorithm for TL-rectangle hitting set yields an α-competitive online algorithm for Online Cycle Augmentation. -/theorem online_cycle_augmentation_reduction_to_tl_hitting_set (n : ℕ) (L : Finset (ℤ × ℤ)) (hL : ∀ p ∈ L, 0 ≤ p.1 ∧ p.1 < p.2 ∧ p.2 < (n : ℤ)) (w : (ℤ × ℤ) → ℝ) (α : ℝ) (Alg : List (ℤ × ℤ) → Finset (ℤ × ℤ)) (h_online : (∀ reqs, Alg reqs ⊆ L) ∧ (∀ reqs r, Alg reqs ⊆ Alg (reqs ++ [r]))) (h_tl_hit : ∀ reqs, (∀ c ∈ reqs, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) → ∀ c ∈ reqs, ∃ p ∈ Alg reqs, (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2)) (h_tl_comp : ∀ reqs, (∀ c ∈ reqs, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) → ∀ F ⊆ L, (∀ c ∈ reqs, ∃ p ∈ F, (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2)) → ∑ p ∈ Alg reqs, w p ≤ α * ∑ p ∈ F, w p) : ((∀ cuts, (∀ c ∈ cuts, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) → ∀ c ∈ cuts, ∃ p ∈ Alg cuts, ((c.1 ≤ p.1 ∧ p.1 ≤ c.2) ↔ ¬(c.1 ≤ p.2 ∧ p.2 ≤ c.2))) ∧ ∀ cuts, (∀ c ∈ cuts, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) → ∀ F ⊆ L, (∀ c ∈ cuts, ∃ p ∈ F, ((c.1 ≤ p.1 ∧ p.1 ≤ c.2) ↔ ¬(c.1 ≤ p.2 ∧ p.2 ≤ c.2))) → ∑ p ∈ Alg cuts, w p ≤ α * ∑ p ∈ F, w p) := by constructor · intro cuts hcuts c hc obtain ⟨p, hp, h_rect⟩ := h_tl_hit cuts hcuts c hc have hpL : p ∈ L := h_online.1 cuts hp have hp_valid := hL p hpL have hc_valid := hcuts c hc have h_equiv := cycle_link_crosses_cut_iff_tl_rect p.1 p.2 c.1 c.2 (n : ℤ) hp_valid hc_valid refine ⟨p, hp, ?_⟩ exact h_equiv.mpr h_rect · intro cuts hcuts F hFL hF_cross have hF_tl : ∀ c ∈ cuts, ∃ p ∈ F, (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2) := by intro c hc obtain ⟨p, hp, h_cross⟩ := hF_cross c hc have hpL : p ∈ L := hFL hp have hp_valid := hL p hpL have hc_valid := hcuts c hc have h_equiv := cycle_link_crosses_cut_iff_tl_rect p.1 p.2 c.1 c.2 (n : ℤ) hp_valid hc_valid refine ⟨p, hp, ?_⟩ exact h_equiv.mp h_cross exact h_tl_comp cuts hcuts F hFL hF_tl