Rights statement: The final publication is available at Springer via http://dx.doi.org/10.1007/s11590-017-1206-x
Accepted author manuscript, 252 KB, PDF document
Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License
Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - On scenario aggregation to approximate robust combinatorial optimization problems
AU - Chassein, André
AU - Goerigk, Marc
N1 - The final publication is available at Springer via http://dx.doi.org/10.1007/s11590-017-1206-x
PY - 2018/10
Y1 - 2018/10
N2 - As most robust combinatorial min–max and min–max regret problems with discrete uncertainty sets are NP-hard, research in approximation algorithm and approximability bounds has been a fruitful area of recent work. A simple and well-known approximation algorithm is the midpoint method, where one takes the average over all scenarios, and solves a problem of nominal type. Despite its simplicity, this method still gives the best-known bound on a wide range of problems, such as robust shortest path or robust assignment problems. In this paper, we present a simple extension of the midpoint method based on scenario aggregation, which improves the current best K-approximation result to an (εK)(εK) -approximation for any desired ε>0ε>0 . Our method can be applied to min–max as well as min–max regret problems.
AB - As most robust combinatorial min–max and min–max regret problems with discrete uncertainty sets are NP-hard, research in approximation algorithm and approximability bounds has been a fruitful area of recent work. A simple and well-known approximation algorithm is the midpoint method, where one takes the average over all scenarios, and solves a problem of nominal type. Despite its simplicity, this method still gives the best-known bound on a wide range of problems, such as robust shortest path or robust assignment problems. In this paper, we present a simple extension of the midpoint method based on scenario aggregation, which improves the current best K-approximation result to an (εK)(εK) -approximation for any desired ε>0ε>0 . Our method can be applied to min–max as well as min–max regret problems.
KW - Robust combinatorial optimization
KW - Approximation algorithms
KW - Scenario aggregation
KW - Min–max optimization
KW - Min–max regret optimization
U2 - 10.1007/s11590-017-1206-x
DO - 10.1007/s11590-017-1206-x
M3 - Journal article
VL - 12
SP - 1523
EP - 1533
JO - Optimization Letters
JF - Optimization Letters
SN - 1862-4472
IS - 7
ER -