On the approximability of minmax (regret) network optimization problems
From MaRDI portal
Publication:976089
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
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the approximability of minmax (regret) network optimization problems
