Tag
integrality-gap
- Sep 4, 2025 Randomized Rounding of Linear Programs into Integer Solutions How solving a linear relaxation and rounding each variable by its own probability produces integer solutions whose expected cost is within the relaxation bound, and where the argument needs repair. algorithms
- May 27, 2024 Fractional Relaxation and the Knapsack Integrality Gap Why the density-ordered greedy rule is exactly optimal for fractional knapsack, how the 0/1 version loses a factor of two, and what value scaling buys back. algorithms