Complexity of the min-max and min-max regret assignment problems

DOI10.1016/J.ORL.2004.12.002MaRDI QIDQ813974zbMATHOpenAlexFDO

Authors 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

assignment problem complexity NP-hard min-max min-max regret

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60) Discrete location and assignment (90B80)

Recommendations

Complexity of the min-max (regret) versions of min cut problems
Algorithms and Computation
Exact and heuristic algorithms for the interval data robust assignment problem
On the complexity of minmax regret linear programming
On the complexity of constructing a minmax regret solution for the two-machine flow shop problem under the interval uncertainty

Cites work

scientific article; zbMATH DE number 3639144 (Why is no real title available?)
scientific article; zbMATH DE number 3231692 (Why is no real title available?)
A note on shortest path, assignment, and transportation problems
Complexity of robust single facility location problems on networks with uncertain edge lengths.
Interval data minmax regret network optimization problems
Minmax regret linear resource allocation problems.
On the complexity of the robust spanning tree problem with interval data
On the robust shortest path problem.
Robust discrete optimization and its applications
The robust spanning tree problem with interval data

Cited in

(46)

Algorithms and Computation
Minimizing the number of late jobs on a single machine under due date uncertainty
Robustness in operational research and decision aiding: a multi-faceted issue
Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling
Min-max and min-max regret versions of combinatorial optimization problems: A survey
Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets
A note on the nonexistence of oracle-polynomial algorithms for robust combinatorial optimization
Complexity of the min-max (regret) versions of min cut problems
An improved reduction method for the robust optimization of the assignment problem
Maximum excess dominance: identifying impractical solutions in linear problems with interval coefficients
Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty
Computing Min-Max Regret Solutions in Possibilistic Combinatorial Optimization Problems
A MIP formulation for the minmax regret total completion time in scheduling with unrelated parallel machines
Minmax regret combinatorial optimization problems with investments
Robust approach to restricted items selection problem
On the complexity of the assignment problem with ordinal data
Possibilistic bottleneck combinatorial optimization problems with ill-known weights
The complexity of bottleneck labeled graph problems
Multistage robust discrete optimization via quantified integer programming
The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows
Solution algorithms for unrelated machines minmax regret scheduling problem with interval processing times and the total flow time criterion
Minmax regret bottleneck problems with solution-induced interval uncertainty structure
Approximating the min-max (regret) selecting items problem
Approximation and resolution of min-max and min-max regret versions of combinatorial optimization problems. (Abstract of Thesis)
New models for the robust shortest path problem: complexity, resolution and generalization
Robust minmax regret combinatorial optimization problems with a resource-dependent uncertainty polyhedron of scenarios
Complexity of interval minmax regret scheduling on parallel identical machines with total completion time criterion
Complexity of min-max-min robustness for combinatorial optimization under discrete uncertainty
An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion
Robust combinatorial optimization under budgeted-ellipsoidal uncertainty
Efficient Algorithms for k-Regret Minimizing Sets
Robust combinatorial optimization under convex and discrete cost uncertainty
Robust balanced optimization
Complexity of minimizing the total flow time with interval data and minmax regret criterion
Combinatorial two-stage minmax regret problems under interval uncertainty
The Complexity of Bottleneck Labeled Graph Problems
On a constant factor approximation for minmax regret problems using a symmetry point scenario
On the approximability of minmax (regret) network optimization problems
On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data
A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem
Complexity of the robust weighted independent set problems on interval graphs
Routing optimization under uncertainty
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
Heuristic algorithms for the minmax regret flow-shop problem with interval processing times
Exact and heuristic algorithms for the interval data robust assignment problem

This page was built for publication: Complexity of the min-max and min-max regret assignment problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q813974)