New Integrality Gap Results for the Firefighters Problem on Trees.

Parinya Chalermsook Daniel Vaz

Published in: WAOA (2016)

Keyphrases

integrality gap
linear programming relaxation
decision trees
linear program
lower bound
arbitrarily close
approximation algorithms
valid inequalities
linear programming
np hardness
knapsack problem
column generation
agnostic learning