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

DOI10.1016/J.ORL.2004.12.002zbMATH Open1141.90457OpenAlexW2039863186MaRDI QIDQ813974FDOQ813974

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

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

zbMATH Keywords

assignment problemcomplexityNP-hardmin-maxmin-max regret

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Robust discrete optimization and its applications
• On the robust shortest path problem.
• Interval data minmax regret network optimization problems
• The robust spanning tree problem with interval data
• On the complexity of the robust spanning tree problem with interval data
• A note on shortest path, assignment, and transportation problems
• Complexity of robust single facility location problems on networks with uncertain edge lengths.
• Minmax regret linear resource allocation problems.

Cited In (45)

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

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)