Iterative Rounding Approximation Guarantee for the Gasoline Problem

Interactive exploration of an open problem: determining the worst-case approximation ratio of the iterative rounding algorithm for the Gasoline problem and its d-dimensional generalization.

Open Problem
570+
Problem Instances Tested
1.30
Max Observed IR/OPT Ratio
d=1..4
Dimensions Studied
2d
Conjectured Worst-Case Bound

Research Summary

The Gasoline problem seeks a minimum-cost permutation matching fuel supplies to consumption demands along a circular route. The iterative rounding algorithm solves an LP relaxation over doubly stochastic matrices and fixes columns one by one.

Status: OPEN PROBLEM The approximation guarantee of this algorithm is unknown (Nikoleit et al., 2026). The 2-approximation conjecture was disproved for d ≥ 2, but no formal bound exists for any dimension.

Key Findings from Our Study

  • 1D case (d=1): Maximum observed ratio is 1.20, supporting the 2-approximation conjecture Supported
  • 2D case (d=2): Maximum observed ratio is 1.30, well below the conjectured bound of 4 Below Bound
  • Higher dimensions: LP relaxation becomes structurally loose, with the objective (sum) mismatching the stock size (max) Open
  • Scale matters: Known counterexamples (ratio > 2) require n ≥ 62, beyond exact enumeration range

The Gasoline Problem

Originally from Lovasz's Combinatorial Problems and Exercises (1979): gas stations on a circular route each provide fuel x_i and require fuel y_i to reach the next station. The optimization version minimizes the tank capacity needed.

Formal Definition

Input: X = {x_1,...,x_n}, Y = {y_1,...,y_n} with sum(X) = sum(Y)
Goal: Find permutation pi minimizing eta(pi) = max_{k,l} |Sum_{i=k..l} x_{pi(i)} - Sum_{i=k..l-1} y_i|

d-Dimensional Generalization

Each x_i, y_i become d-dimensional vectors. The bound must hold coordinate-wise for each dimension j in [d]. This models scheduling with d types of non-renewable resources.

The Open Problem

Determine the worst-case approximation ratio of the iterative rounding algorithm that solves the LP relaxation and fixes columns one by one. The 2-approximation conjecture was disproved for d ≥ 2 by Nikoleit et al. (2026), but the true guarantee is unknown.

Known Results

YearAuthorsResult
1979LovaszClassical gasoline puzzle existence proof
1998Kellerer et al.Stock size: 3/2-approx; 2-approx algorithms
2016Newman, Roglin, Seif1.79-approx (alternating); 2-approx via doubly stochastic LP
2022RajkovicIterative rounding algorithm; conjectured 2-approx
2026Nikoleit et al.Counterexamples via Co-FunSearch: ratio > 2 for d ≥ 2

The Iterative Rounding Algorithm

LP Relaxation

The integer program uses a permutation matrix Z in {0,1}^{nxn}. The LP relaxation replaces this with Z ≥ 0, doubly stochastic. By the Birkhoff-von Neumann theorem, the feasible set is the Birkhoff polytope.

min Sum_j (beta_j - alpha_j)
s.t. prefix-sum constraints for each position m and dimension j
     Z*1 = 1, 1^T*Z = 1^T, Z ≥ 0

Algorithm Steps

  1. Solve the LP relaxation to obtain doubly stochastic Z*
  2. For each column c = 1, 2, ..., n:
    • For each available row r, tentatively fix column c to unit vector e_r
    • Re-solve the reduced LP with this fixing
    • Choose the row r minimizing the reduced LP value
  3. After n steps, Z is a permutation matrix; return the permutation pi

Complexity

Each step requires solving O(n) reduced LPs. With n columns, the total is O(n^2) LP solves, each of size O(n^2) variables. Overall: O(n^5) time.

Why It Is Hard to Analyze

  • Compounding error: Each column fixing affects all subsequent columns
  • Circular structure: Prefix sums wrap around, creating feedback
  • Dimensional coupling: In d dimensions, constraints interact across coordinates
  • Extreme point structure: The augmented Birkhoff polytope has complex geometry

Comparison Algorithms

  • Greedy: At each position, assign the item minimizing current deviation
  • Newman Rounding: Solve LP, extract permutation via Hungarian algorithm
  • Exact (brute force): Enumerate all n! permutations (feasible for n ≤ 8)

Exact Approximation Ratios

Maximum observed IR/OPT ratios from 240 random instances with exact solutions:

Dimension Scaling

Maximum and mean IR/OPT ratios vs. dimension d. The conjectured 2d bound grows linearly while observed ratios remain near 1.0-1.2.

Detailed Statistics

dnMaxMeanStd2d
151.1831.0190.0462
251.0971.0110.0274
341.1311.0160.0316
441.0241.0040.0088

Integrality Gap Analysis

Integrality gap (OPT_IP / OPT_LP) across 180 instances. For d=1, the LP provides a valid lower bound (gap ≥ 1). For d ≥ 2, the sum-vs-max objective mismatch causes the measured ratio to fall below 1.

Known Counterexamples (Nikoleit et al., 2026)

dk|X|IR costOPTRatio
2562122363.389
26126250683.676
35124186404.650
These counterexamples require n ≥ 62, far beyond our exact enumeration range (n ≤ 8). The gap between our small-instance measurements (max ratio 1.30) and these large-instance counterexamples (ratio > 3) indicates that worst-case behavior is a phenomenon of scale.

Interactive Gasoline Instance Explorer

Generate random Gasoline problem instances and visualize the prefix-sum deviation under different permutations.

Adjust parameters and click Generate to create a Gasoline problem instance.

Permutation Comparison

For the current instance, compare the prefix-sum profiles under different algorithms:

References

  1. Nikoleit, F., Foerster, K.-T., Schmid, S. (2026). The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristics. arXiv:2601.16849.
  2. Lovasz, L. (1979). Combinatorial Problems and Exercises. North-Holland.
  3. Kellerer, H., Kotov, V., Rendl, F., Woeginger, G.J. (1998). A stock size problem. Operations Research, 46(3), S183-S194.
  4. Newman, A., Roglin, H., Seif, J. (2016). On the Gasoline Puzzle and Semirandom Relaxations. ESA 2016.
  5. Rajkovic, S. (2022). Iterative Rounding for the Gasoline Problem. PhD thesis, U. Bonn.
  6. Jain, K. (2001). A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. Combinatorica, 21(1), 39-60.
  7. Lau, L.C., Ravi, R., Singh, M. (2011). Iterative Methods in Combinatorial Optimization. Cambridge University Press.
  8. Birkhoff, G. (1946). Three Observations on Linear Algebra. Univ. Nac. Tucuman, Rev. Ser. A, 5, 147-151.

Reproducibility

All code and data are available in the project repository:

  • code/experiments.py - Experiment runner (generates data/)
  • code/generate_figures.py - Figure generation (generates paper/figures/)
  • data/ - CSV files with all experimental results
  • paper/main.tex - LaTeX source (ACM sigconf format)