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, 252 KB, PDF document

    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 Journal/MagazineJournal articlepeer-review

Published

Standard

On scenario aggregation to approximate robust combinatorial optimization problems. / Chassein, André; Goerigk, Marc.
In: Optimization Letters, Vol. 12, No. 7, 10.2018, p. 1523-1533.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

APA

Vancouver

Chassein A, Goerigk M. On scenario aggregation to approximate robust combinatorial optimization problems. Optimization Letters. 2018 Oct;12(7):1523-1533. Epub 2017 Oct 23. doi: 10.1007/s11590-017-1206-x

Author

Chassein, André ; Goerigk, Marc. / On scenario aggregation to approximate robust combinatorial optimization problems. In: Optimization Letters. 2018 ; Vol. 12, No. 7. pp. 1523-1533.

Bibtex

@article{ca059f5758824004a55571249c3ccdcd,
title = "On scenario aggregation to approximate robust combinatorial optimization problems",
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.",
keywords = "Robust combinatorial optimization , Approximation algorithms, Scenario aggregation , Min–max optimization, Min–max regret optimization ",
author = "Andr{\'e} Chassein and Marc Goerigk",
note = "The final publication is available at Springer via http://dx.doi.org/10.1007/s11590-017-1206-x",
year = "2018",
month = oct,
doi = "10.1007/s11590-017-1206-x",
language = "English",
volume = "12",
pages = "1523--1533",
journal = "Optimization Letters",
issn = "1862-4472",
publisher = "Springer Verlag",
number = "7",

}

RIS

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 -