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 update complexity of selection and related problems, A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem, Min-max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty, On exact solutions for the minmax regret spanning tree problem, 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, A minmax regret version of the time-dependent shortest path 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), Algorithms and complexity analysis for robust single-machine scheduling problems, 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, A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs, Minmax regret combinatorial optimization problems with investments, The robust (minmax regret) assembly line worker assignment and balancing problem, A double oracle approach to minmax regret optimization problems with interval data, Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets, Robust single machine scheduling with a flexible maintenance activity, Formulation and algorithms for the robust maximal covering location problem, Compromise solutions for robust combinatorial optimization with variable-sized uncertainty, Distributionally robust single machine scheduling with risk aversion, On scenario aggregation to approximate robust combinatorial optimization problems, Min-max and min-max (relative) regret approaches to representatives selection problem, A single-machine scheduling problem with uncertainty in processing times and outsourcing costs, Complexity of the robust weighted independent set problems on interval graphs, Algorithms for the minmax regret path problem with interval data, Optimal path discovery problem with homogeneous knowledge, Complexity results for common due date scheduling problems with interval data and minmax regret criterion, 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, Min-Max Regret Version of the Linear Time–Cost Tradeoff Problem with Multiple Milestones and Completely Ordered Jobs
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
