Home > Research > Publications & Outputs > On scenario aggregation to approximate robust c...

Electronic data

  • paper

    Rights statement: The final publication is available at Springer via http://dx.doi.org/10.1007/s11590-017-1206-x

    Accepted author manuscript, 251 KB, PDF-document

    Embargo ends: 23/10/18

    Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License

Links

Text available via DOI:

View graph of relations

On scenario aggregation to approximate robust combinatorial optimization problems

Research output: Contribution to journalJournal article

E-pub ahead of print
<mark>Journal publication date</mark>23/10/2017
<mark>Journal</mark>Optimization Letters
Number of pages11
<mark>State</mark>E-pub ahead of print
Early online date23/10/17
<mark>Original language</mark>English

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 (εK)(εK) -approximation for any desired ε>0ε>0 . Our method can be applied to min–max as well as min–max regret problems.

Bibliographic note

The final publication is available at Springer via http://dx.doi.org/10.1007/s11590-017-1206-x