Submitted manuscript
Research output: Working paper
Research output: Working paper
}
TY - UNPB
T1 - On Scenario Aggregation to Approximate Robust Optimization Problems
AU - Chassein, André
AU - Goerigk, Marc
PY - 2016/11/29
Y1 - 2016/11/29
N2 - As most robust combinatorial min-max and min-max regret problems with discrete uncertainty sets are NP-hard, research into 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)-approximation for any desired ε>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 into 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)-approximation for any desired ε>0. Our method can be applied to min-max as well as min-max regret problems.
M3 - Working paper
BT - On Scenario Aggregation to Approximate Robust Optimization Problems
ER -