On the approximability of minmax (regret) network optimization problems

DOI10.1016/j.ipl.2008.10.008zbMath1191.68451arXiv0804.0396OpenAlexW2006806110MaRDI QIDQ976089

Adam Kasperski, Paweł Zieliński

Publication date: 16 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0804.0396

zbMATH Keywords

computational complexityapproximationcombinatorial problemsminmax regretminmax

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Mathematical programming (90C99)

Related Items (12)

Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty ⋮ Recoverable robust shortest path problems ⋮ On the approximability of robust spanning tree problems ⋮ Min-max and min-max (relative) regret approaches to representatives selection problem ⋮ Using the WOWA operator in robust discrete optimization problems ⋮ The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows ⋮ Approximating a two-machine flow shop scheduling under discrete scenario uncertainty ⋮ Combinatorial optimization problems with uncertain costs and the OWA criterion ⋮ A randomized algorithm for the min-Max selecting items problem with uncertain weights ⋮ Approximability of the robust representatives selection problem ⋮ Robust Discrete Optimization Problems with the WOWA Criterion ⋮ Socially fair network design via iterative rounding

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The computational complexity of the relative robust shortest path problem with interval data
• Complexity of the min-max and min-max regret assignment problems
• Approximation of min-max and min-max regret versions of some combinatorial optimization problems
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• Robust discrete optimization and its applications
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• On the complexity of the robust spanning tree problem with interval data
• Interval data minmax regret network optimization problems
• On the complexity of minmax regret linear programming
• On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data
• Approximating Min-Max (Regret) Versions of Some Polynomial Problems
• The Recognition of Series Parallel Digraphs
• Algorithms – ESA 2005
• Algorithms and Computation
• On the complexity of a class of combinatorial optimization problems with uncertainty

This page was built for publication: On the approximability of minmax (regret) network optimization problems