Complexity of the min-max and min-max regret assignment problems
From MaRDI portal
Publication:813974
DOI10.1016/j.orl.2004.12.002zbMath1141.90457MaRDI QIDQ813974
Cristina Bazgan, Daniel Vanderpooten, Hassene Aissi
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
90C60: Abstract computational complexity for mathematical programming problems
90B80: Discrete location and assignment
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
AN IMPROVED REDUCTION METHOD FOR THE ROBUST OPTIMIZATION OF THE ASSIGNMENT PROBLEM, The complexity of bottleneck labeled graph problems, A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem, New models for the robust shortest path problem: complexity, resolution and generalization, 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, Solution algorithms for unrelated machines minmax regret scheduling problem with interval processing times and the total flow time criterion, Exact and heuristic algorithms for the interval data robust assignment problem, Minimizing the number of late jobs on a single machine under due date uncertainty, 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, On the approximability of minmax (regret) network optimization problems, 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, Robust minmax regret combinatorial optimization problems with a resource-dependent uncertainty polyhedron of scenarios, 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, Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets, Complexity of interval minmax regret scheduling on parallel identical machines with total completion time criterion, Min-max and min-max (relative) regret approaches to representatives selection problem, A MIP formulation for the minmax regret total completion time in scheduling with unrelated parallel machines, On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data, Routing Optimization Under Uncertainty, The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows, The Complexity of Bottleneck Labeled Graph Problems
Cites Work
- 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
- Unnamed Item
- Unnamed Item
