On scenario aggregation to approximate robust combinatorial optimization problems |
| |
Authors: | André Chassein Marc Goerigk |
| |
Institution: | 1.Fachbereich Mathematik,Technische Universit?t Kaiserslautern,Kaiserslautern,Germany;2.Department of Management Science,Lancaster University,Lancashire,UK |
| |
Abstract: | 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 \((\varepsilon K)\)-approximation for any desired \(\varepsilon > 0\). Our method can be applied to min–max as well as min–max regret problems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|