Tight Lower Bounds for Block-Structured Integer Programs.

Christoph Hunkenschröder Kim-Manuel Klein Martin Koutecký Alexandra Lassota Asaf Levin

Published in: IPCO (2024)

Keyphrases

lower bound
integer program
cutting plane
column generation
branch and bound
upper bound
multistage stochastic

linear program
linear programming relaxation
optimal solution
integer programming
np hard
branch and bound algorithm

objective function
lower and upper bounds
structured data
lagrangian relaxation
worst case
image blocks

network flow
graph cuts
block size
cost function
portfolio selection
online algorithms