On the Robust Knapsack Problem

DOI10.1137/120880355zbMath1306.90134OpenAlexW2043033472MaRDI QIDQ5408207

Ulrich Pferschy, Michele Monaci

Publication date: 9 April 2014

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/120880355

zbMATH Keywords

knapsack problemrobust optimizationworst-case ratio

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items (14)

Packing a Knapsack of Unknown Capacity ⋮ Robust optimization approach for a chance-constrained binary knapsack problem ⋮ Robust combinatorial optimization with variable cost uncertainty ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Exact algorithms for the 0-1 time-bomb knapsack problem ⋮ Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms ⋮ The robust knapsack problem with queries ⋮ Knapsack with variable weights satisfying linear constraints ⋮ A branch and bound algorithm for robust binary optimization with budget uncertainty ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Tolerance analysis for 0-1 knapsack problems ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Exact lexicographic scheduling and approximate rescheduling ⋮ Formulations and algorithms for the recoverable \({\varGamma}\)-robust knapsack problem

This page was built for publication: On the Robust Knapsack Problem