An approximation algorithm for interval data minmax regret combinatorial optimization problems
From MaRDI portal
Publication:1045926
DOI10.1016/j.ipl.2005.11.001zbMath1184.68640MaRDI QIDQ1045926
Paweł Zieliński, Adam Kasperski
Publication date: 18 December 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2005.11.001
68R05: Combinatorics in computer science
90C27: Combinatorial optimization
68W25: Approximation algorithms
Related Items
On a Class of Interval Data Minmax Regret CO Problems, Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality, The robust set covering problem with interval data, Minmax regret bottleneck problems with solution-induced interval uncertainty structure, On a constant factor approximation for minmax regret problems using a symmetry point scenario, On robust online scheduling algorithms, Heuristics for the central tree problem, On combinatorial optimization problems on matroids with uncertain weights, Minimax regret spanning arborescences under uncertain costs, Approximation and resolution of min-max and min-max regret versions of combinatorial optimization problems. (Abstract of Thesis), Complexity of the min-max (regret) versions of min cut problems, A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion, Simulated annealing algorithm for the robust spanning tree problem, On the approximability of minmax (regret) network optimization problems, A 2-approximation for minmax regret problems via a mid-point scenario optimal solution, Some tractable instances of interval data minmax regret problems, Min-max and min-max regret versions of combinatorial optimization problems: A survey, A polynomial solvable minimum risk spanning tree problem with interval data, The minimum spanning tree problem with fuzzy costs, Choosing robust solutions in discrete optimization problems with fuzzy costs, Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights, Min-max and min-max (relative) regret approaches to representatives selection problem, Complexity of the robust weighted independent set problems on interval graphs, On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data, A mixed integer programming formulation for the total flow time single machine robust scheduling problem with interval data
Cites Work
- The computational complexity of the relative robust shortest path problem with interval data
- A branch and bound algorithm for the robust spanning tree problem with interval data
- Robust discrete optimization and its applications
- A branch and bound algorithm for the robust shortest path problem with interval data.
- On the complexity of the robust spanning tree problem with interval data
- Interval data minmax regret network optimization problems
- An exact algorithm for the robust shortest path problem with interval data
- On the complexity of a class of combinatorial optimization problems with uncertainty
- The robust spanning tree problem with interval data
