An approximation algorithm for interval data minmax regret combinatorial optimization problems
From MaRDI portal
Publication:1045926
DOI10.1016/j.ipl.2005.11.001zbMath1184.68640OpenAlexW2051407192MaRDI 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
Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (57)
Min-Max Regret Version of the Linear Time–Cost Tradeoff Problem with Multiple Milestones and Completely Ordered Jobs ⋮ An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion ⋮ 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 combinatorial optimization problems on matroids with uncertain weights ⋮ A mixed integer programming formulation for the total flow time single machine robust scheduling problem with interval data ⋮ On exact solutions for the minmax regret spanning tree problem ⋮ 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 ⋮ Robust min-max regret covering problems ⋮ The robust set covering problem with interval data ⋮ On the complexity of min-max-min robustness with two alternatives and budgeted uncertainty ⋮ 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) ⋮ A double oracle approach to minmax regret optimization problems with interval data ⋮ Robust Algorithms for TSP and Steiner Tree ⋮ A fix‐and‐optimize heuristic for the minmax regret shortest path arborescence problem under interval uncertainty ⋮ Min-max and min-max (relative) regret approaches to representatives selection problem ⋮ Complexity results for common due date scheduling problems with interval data and minmax regret criterion ⋮ Combinatorial optimization problems with balanced regret ⋮ Algorithms for the minmax regret path problem with interval data ⋮ Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets ⋮ Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty ⋮ Minmax regret bottleneck problems with solution-induced interval uncertainty structure ⋮ Algorithms and complexity analysis for robust single-machine scheduling problems ⋮ On a constant factor approximation for minmax regret problems using a symmetry point scenario ⋮ Complexity of the min-max (regret) versions of min cut problems ⋮ On a Class of Interval Data Minmax Regret CO Problems ⋮ On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data ⋮ Robust single machine scheduling with a flexible maintenance activity ⋮ 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 ⋮ Formulation and algorithms for the robust maximal covering location problem ⋮ Combinatorial two-stage minmax regret problems under interval uncertainty ⋮ Compromise solutions for robust combinatorial optimization with variable-sized uncertainty ⋮ A single-machine scheduling problem with uncertainty in processing times and outsourcing costs ⋮ Distributionally robust single machine scheduling with risk aversion ⋮ On robust online scheduling algorithms ⋮ On the approximability of minmax (regret) network optimization problems ⋮ Heuristics for the central tree problem ⋮ Complexity of the robust weighted independent set problems on interval graphs ⋮ A 2-approximation for minmax regret problems via a mid-point scenario optimal solution ⋮ A minmax regret version of the time-dependent shortest path problem ⋮ Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality ⋮ Some tractable instances of interval data minmax regret problems ⋮ On scenario aggregation to approximate robust combinatorial optimization problems ⋮ Query minimization under stochastic uncertainty ⋮ Optimal path discovery problem with homogeneous knowledge ⋮ Learning Control Sets for Lattice Planners from User Preferences ⋮ Min-max and min-max regret versions of combinatorial optimization problems: A survey ⋮ The Minimum Cost Query Problem on Matroids with Uncertainty Areas. ⋮ 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
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
This page was built for publication: An approximation algorithm for interval data minmax regret combinatorial optimization problems
