VibeMathedMath problems solved with AI
Sign in

Two-size Gasoline: the tight approximation guarantee for iterative rounding

For a Gasoline instance with deliveries xi∈{1,K}x_i\in\{1,K\}, fixed positive integer demands yiy_i, equal list lengths and equal total supply and demand, does the position-first Iterative Rounding algorithm always return a schedule using at most twice the minimum storage capacity? At each position it tries each remaining delivery, solves the fractional assignment LP with the chosen prefix fixed, and takes a minimum-score candidate. Capacity includes every delivery peak and consumption trough, with a freely chosen initial stock. This is Conjecture 3.1.1 of Lorieau (2024), the {1,K}\{1,K\} case of Rajkovic's conjecture for the one-dimensional problem.

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Approximation algorithms; inventory and buffer scheduling
Posed by
Lucas Lorieau, Iterative Rounding algorithms for the Extended Gasoline Problem (2024), Conjecture 3.1.1, p. 21; algorithm due to Rajkovic (2022).
Year posed
2024
Years open
2y
Solved
2026-10-01
Model
OpenAI Codex (GPT-6 Astra)
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Significance
6 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

For every integer K≥2K\ge2, deliveries in {1,K}\{1,K\} and positive integer demands, we prove CIR≤Linit+K−2≤OPT+K−2C_{\mathrm{IR}}\le L_{\mathrm{init}}+K-2\le\mathrm{OPT}+K-2, where LinitL_{\mathrm{init}} is the initial fractional assignment-LP optimum. The upper bound permits every exact tie choice. For every K≥3K\ge3, an explicit family with 2K−32K-3 days has Linit=OPT=KL_{\mathrm{init}}=\mathrm{OPT}=K and CIR=2K−2C_{\mathrm{IR}}=2K-2 under original-index tie breaking. Hence the exact worst-case ratio for that rule is 2−2/K2-2/K, with uniform supremum 22; the algorithm is optimal when K=2K=2. The proof also yields an implementation using O(n) arithmetic operations instead of repeated LP solves. This settles the stated two-size positive-integer case, not the unrestricted one-dimensional or multidimensional conjectures. An additional exact finite example shows that preferring the smaller delivery on ties need not be optimal (capacity 7 versus 5); no improved universal guarantee for that alternative rule is claimed.

What the AI did

Under human direction, Codex selected and investigated the conjecture, searched prior work, derived the exact suffix-LP formula and rounding invariant, constructed a sharpness family, developed the Lean formalization, and implemented exact verification and the interactive laboratory. The human chose the research objectives, supervised the workflow, requested prior-work checks and formal verification, and reviewed the publication materials. No independent human mathematical verification is claimed.

Verification

A clean Azure build passed all nine Lean modules using Lean 4.34.0 and a pinned mathlib revision. Nanoda independently checked 9,451 declarations in the dependency closure of 12 audited targets. The allowed axioms were only propext, Classical.choice and Quot.sound; the export contained no unsafe or partial declarations. Both Lean and Nanoda rejected deliberately invalid controls. The project uses no custom axioms, sorry/admit, native_decide, or modified kernel/checker rules. Separate Python and JavaScript implementations agreed on 20 fixed examples and 271 candidate scores, with an independent cycle-path LP oracle. The main universal guarantee and full parameterized sharpness family are formalized; the O(n) arithmetic-complexity claim is separate mathematical/code analysis. The formal statements and their correspondence to the original algorithm have not been independently audited by a human expert. No peer review is claimed; this is a repository announcement.

Sources

Submitted by ZestyRaven517 on

Changelog2 changes

Discussion