On the approximability of minmax (regret) network optimization problems

DOI10.1016/J.IPL.2008.10.008zbMATH Open1191.68451arXiv0804.0396OpenAlexW2006806110MaRDI QIDQ976089FDOQ976089

Adam Kasperski, Paweł Zieliński

Publication date: 16 June 2010

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Robust discrete optimization and its applications
• Interval data minmax regret network optimization problems
• The Recognition of Series Parallel Digraphs
• On the complexity of a class of combinatorial optimization problems with uncertainty
• On the complexity of the robust spanning tree problem with interval data
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• On the complexity of minmax regret linear programming
• 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
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• Approximating Min-Max (Regret) Versions of Some Polynomial Problems
• The computational complexity of the relative robust shortest path problem with interval data
• Algorithms and Computation
• On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data
• Algorithms – ESA 2005

Cited In (16)

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

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)