Min-max and min-max regret versions of combinatorial optimization problems: A survey

Hassene Aissi, Cristina Bazgan and Daniel Vanderpooten

European Journal of Operational Research, 2009, vol. 197, issue 2, 427-438

Abstract: Min-max and min-max regret criteria are commonly used to define robust solutions. After motivating the use of these criteria, we present general results. Then, we survey complexity results for the min-max and min-max regret versions of some combinatorial optimization problems: shortest path, spanning tree, assignment, min cut, min s-t cut, knapsack. Since most of these problems are NP-hard, we also investigate the approximability of these problems. Furthermore, we present algorithms to solve these problems to optimality.

Keywords: Min-max; Min-max; regret; Combinatorial; optimization; Complexity; Approximation; Robustness (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (71)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00762-5
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:197:y:2009:i:2:p:427-438

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().