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

@article{citeulike:3463714, 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.}, author = {Aissi, Hassene and Bazgan, Cristina and Vanderpooten, Daniel}, citeulike-article-id = {3463714}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.ejor.2008.09.012}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0377221708007625}, day = {01}, doi = {10.1016/j.ejor.2008.09.012}, issn = {03772217}, journal = {European Journal of Operational Research}, keywords = {discrete, regret, robust, uncertainty}, month = {September}, number = {2}, pages = {427--438}, posted-at = {2009-11-06 16:10:03}, priority = {2}, title = {Min–max and min–max regret versions of combinatorial optimization problems: A survey}, url = {http://dx.doi.org/10.1016/j.ejor.2008.09.012}, volume = {197}, year = {2009} }

TY - JOUR ID - citeulike:3463714 L3 - citeulike-article-id:3463714 N2 - 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. IS - 2 JF - European Journal of Operational Research SN - 03772217 EP - 438 TI - Min–max and min–max regret versions of combinatorial optimization problems: A survey VL - 197 SP - 427 KW - discrete KW - regret KW - robust KW - uncertainty AU - Aissi, Hassene AU - Bazgan, Cristina AU - Vanderpooten, Daniel PY - 2009/09/01/ UR - http://dx.doi.org/10.1016/j.ejor.2008.09.012 ER -