On the approximability of minmax (regret) network optimization problems

DOI10.1016/J.IPL.2008.10.008MaRDI QIDQ976089zbMATH OpenOpenAlexFDO

Authors 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)

Abstract: In this paper the minmax (regret) versions of some basic polynomially solvable deterministic network problems are discussed. It is shown that if the number of scenarios is unbounded, then the problems under consideration are not approximable within $lo{g}^{1-epsilon}K$ for any $epsilon>0$ unless NP $subseteq$ DTIME$(n^{mathrmpolylogn})$, where $K$ is the number of scenarios.

Recommendations

• Approximating Min-Max (Regret) Versions of Some Polynomial Problems
• Approximation of min-max and min-max regret versions of some combinatorial optimization problems
• Algorithms – ESA 2005
• General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems
• An approximation algorithm for interval data minmax regret combinatorial optimization problems

Cites work

• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Algorithms and Computation
• Algorithms – ESA 2005
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• Approximating Min-Max (Regret) Versions of Some Polynomial Problems
• Approximation of min-max and min-max regret versions of some combinatorial optimization problems
• Complexity of the min-max and min-max regret assignment problems
• Interval data minmax regret network optimization problems
• Network flows. Theory, algorithms, and applications.
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• On the complexity of a class of combinatorial optimization problems with uncertainty
• On the complexity of minmax regret linear programming
• On the complexity of the robust spanning tree problem with interval data
• On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data
• Robust discrete optimization and its applications
• The Recognition of Series Parallel Digraphs
• The computational complexity of the relative robust shortest path problem with interval data
• The hardness of approximate optima in lattices, codes, and systems of linear equations

Cited in

(21)

• Algorithms and Computation
• Complexity of the min-max (regret) versions of min cut problems
• Improved Algorithms for Computing Minmax Regret 1-Sink and 2-Sink on Path Network
• On the approximability of robust spanning tree problems
• Approximating the shortest path problem with scenarios
• A randomized algorithm for the min-Max selecting items problem with uncertain weights
• The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows
• Socially fair network design via iterative rounding
• General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems
• Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty
• Algorithms – ESA 2005
• Using the WOWA operator in robust discrete optimization problems
• An \(O(mn)\) algorithm for the 1-maximin problem on a network
• Robust discrete optimization problems with the WOWA criterion
• Approximating a two-machine flow shop scheduling under discrete scenario uncertainty
• Approximating Min-Max (Regret) Versions of Some Polynomial Problems
• Recoverable robust shortest path problems
• Approximability of the robust representatives selection problem
• Min-max and min-max (relative) regret approaches to representatives selection problem
• Minmax regret location--allocation problem on a network under uncertainty
• Combinatorial optimization problems with uncertain costs and the OWA criterion

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976089)