On the approximability of minmax (regret) network optimization problems
From MaRDI portal
Publication:976089
DOI10.1016/j.ipl.2008.10.008zbMath1191.68451arXiv0804.0396MaRDI 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
Approximating a two-machine flow shop scheduling under discrete scenario uncertainty, Combinatorial optimization problems with uncertain costs and the OWA criterion, On the approximability of robust spanning tree problems, Using the WOWA operator in robust discrete optimization problems, Approximability of the robust representatives selection problem, Min-max and min-max (relative) regret approaches to representatives selection problem, Socially fair network design via iterative rounding, Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty, A randomized algorithm for the min-Max selecting items problem with uncertain weights, Robust Discrete Optimization Problems with the WOWA Criterion, Recoverable robust shortest path problems, The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows
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
