Gasoline Problem: Breaking the Factor-2 Barrier

Empirical evidence for sub-2 approximation and PTAS feasibility for the Gasoline optimization problem.

1.059
Best Avg Ratio (Greedy+Swap)
1.400
Worst-Case Ratio (n=7)
100%
PTAS Success (eps<=0.3)
0.689
Avg Integrality Gap (n=7)
6
Strategies Tested

Average Approximation Ratio by Strategy (n=7)

Worst-Case Ratio by Strategy and Size

Average Ratio Scaling with Problem Size

PTAS Success Rate by Epsilon (n=7)

Strategy Comparison (n=7, 30 instances)

StrategyAvg RatioMax RatioMin RatioMedian
PTAS Decomposition1.0081.2501.01.0
Greedy + Swap1.0591.4001.01.0
Greedy + 3-Opt1.1041.5001.01.0
Sorted1.1531.6671.01.0
Greedy1.2472.0001.01.25
LP Rounding1.6233.5001.01.5

PTAS Feasibility Results

n / eps0.050.100.150.200.300.50
n=5100%100%100%100%100%100%
n=6100%100%100%100%100%100%
n=7100%100%100%100%100%95%