Complexity of the min-max and min-max regret assignment problems
From MaRDI portal
Publication:813974
DOI10.1016/j.orl.2004.12.002zbMath1141.90457OpenAlexW2039863186MaRDI QIDQ813974
Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten
Publication date: 2 February 2006
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2004.12.002
Abstract computational complexity for mathematical programming problems (90C60) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (38)
Robust approach to restricted items selection problem ⋮ Robust minmax regret combinatorial optimization problems with a resource-dependent uncertainty polyhedron of scenarios ⋮ An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion ⋮ A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem ⋮ Heuristic algorithms for the minmax regret flow-shop problem with interval processing times ⋮ Minmax regret combinatorial optimization problems with investments ⋮ Complexity of min-max-min robustness for combinatorial optimization under discrete uncertainty ⋮ New models for the robust shortest path problem: complexity, resolution and generalization ⋮ Approximation and resolution of min-max and min-max regret versions of combinatorial optimization problems. (Abstract of Thesis) ⋮ Multistage robust discrete optimization via quantified integer programming ⋮ Min-max and min-max (relative) regret approaches to representatives selection problem ⋮ The Complexity of Bottleneck Labeled Graph Problems ⋮ A note on the nonexistence of oracle-polynomial algorithms for robust combinatorial optimization ⋮ The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows ⋮ Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets ⋮ Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty ⋮ Exact and heuristic algorithms for the interval data robust assignment problem ⋮ Minmax regret bottleneck problems with solution-induced interval uncertainty structure ⋮ Possibilistic bottleneck combinatorial optimization problems with ill-known weights ⋮ 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 ⋮ A MIP formulation for the minmax regret total completion time in scheduling with unrelated parallel machines ⋮ Minimizing the number of late jobs on a single machine under due date uncertainty ⋮ Robust combinatorial optimization under budgeted-ellipsoidal uncertainty ⋮ On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data ⋮ Solution algorithms for unrelated machines minmax regret scheduling problem with interval processing times and the total flow time criterion ⋮ Robust combinatorial optimization under convex and discrete cost uncertainty ⋮ Robust balanced optimization ⋮ Combinatorial two-stage minmax regret problems under interval uncertainty ⋮ AN IMPROVED REDUCTION METHOD FOR THE ROBUST OPTIMIZATION OF THE ASSIGNMENT PROBLEM ⋮ On the approximability of minmax (regret) network optimization problems ⋮ Maximum excess dominance: identifying impractical solutions in linear problems with interval coefficients ⋮ Complexity of interval minmax regret scheduling on parallel identical machines with total completion time criterion ⋮ The complexity of bottleneck labeled graph problems ⋮ Routing Optimization Under Uncertainty ⋮ Min-max and min-max regret versions of combinatorial optimization problems: A survey ⋮ Robustness in operational research and decision aiding: a multi-faceted issue ⋮ Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights
Cites Work
- Unnamed Item
- Unnamed Item
- Robust discrete optimization and its applications
- On the robust shortest path problem.
- Minmax regret linear resource allocation problems.
- On the complexity of the robust spanning tree problem with interval data
- Complexity of robust single facility location problems on networks with uncertain edge lengths.
- Interval data minmax regret network optimization problems
- A note on shortest path, assignment, and transportation problems
- The robust spanning tree problem with interval data
This page was built for publication: Complexity of the min-max and min-max regret assignment problems
