Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-Relaxations

Khaled Elbassioni

doi:10.1007/978-3-030-61792-9_3

Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-Relaxations

Khaled Elbassioni

Electrical Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. Assuming the existence of an integrality gap verifier with a bounded approximation guarantee for the LP relaxation of the non-robust version of the problem, we derive approximation algorithms for the robust version under different types of uncertainty, including polyhedral and ellipsoidal uncertainty.

Original language	British English
Title of host publication	LATIN 2020
Subtitle of host publication	Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings
Editors	Yoshiharu Kohayakawa, Flávio Keidi Miyazawa
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	27-37
Number of pages	11
ISBN (Print)	9783030617912
DOIs	https://doi.org/10.1007/978-3-030-61792-9_3
State	Published - 2020
Event	14th Latin American Symposium on Theoretical Informatics, LATIN 2020 - Sao Paulo, Brazil Duration: 5 Jan 2021 → 8 Jan 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12118 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th Latin American Symposium on Theoretical Informatics, LATIN 2020
Country/Territory	Brazil
City	Sao Paulo
Period	5/01/21 → 8/01/21

Keywords

Approximation algorithms
Discrete optimization
Linear programming
Randomized rounding
Robust optimization

Access to Document

10.1007/978-3-030-61792-9_3

Cite this

Elbassioni, K. (2020). Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-Relaxations. In Y. Kohayakawa, & F. K. Miyazawa (Eds.), LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings (pp. 27-37). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12118 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-61792-9_3

Elbassioni, Khaled. / Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-Relaxations. LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. editor / Yoshiharu Kohayakawa ; Flávio Keidi Miyazawa. Springer Science and Business Media Deutschland GmbH, 2020. pp. 27-37 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e33e651db437438e969b8ff37795ec6f,

title = "Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-Relaxations",

abstract = "We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. Assuming the existence of an integrality gap verifier with a bounded approximation guarantee for the LP relaxation of the non-robust version of the problem, we derive approximation algorithms for the robust version under different types of uncertainty, including polyhedral and ellipsoidal uncertainty.",

keywords = "Approximation algorithms, Discrete optimization, Linear programming, Randomized rounding, Robust optimization",

author = "Khaled Elbassioni",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 14th Latin American Symposium on Theoretical Informatics, LATIN 2020 ; Conference date: 05-01-2021 Through 08-01-2021",

year = "2020",

doi = "10.1007/978-3-030-61792-9_3",

language = "British English",

isbn = "9783030617912",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "27--37",

editor = "Yoshiharu Kohayakawa and Miyazawa, {Fl{\'a}vio Keidi}",

booktitle = "LATIN 2020",

address = "Germany",

}

Elbassioni, K 2020, Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-Relaxations. in Y Kohayakawa & FK Miyazawa (eds), LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12118 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 27-37, 14th Latin American Symposium on Theoretical Informatics, LATIN 2020, Sao Paulo, Brazil, 5/01/21. https://doi.org/10.1007/978-3-030-61792-9_3

Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-Relaxations. / Elbassioni, Khaled.
LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. ed. / Yoshiharu Kohayakawa; Flávio Keidi Miyazawa. Springer Science and Business Media Deutschland GmbH, 2020. p. 27-37 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12118 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-Relaxations

AU - Elbassioni, Khaled

PY - 2020

Y1 - 2020

N2 - We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. Assuming the existence of an integrality gap verifier with a bounded approximation guarantee for the LP relaxation of the non-robust version of the problem, we derive approximation algorithms for the robust version under different types of uncertainty, including polyhedral and ellipsoidal uncertainty.

AB - We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. Assuming the existence of an integrality gap verifier with a bounded approximation guarantee for the LP relaxation of the non-robust version of the problem, we derive approximation algorithms for the robust version under different types of uncertainty, including polyhedral and ellipsoidal uncertainty.

KW - Approximation algorithms

KW - Discrete optimization

KW - Linear programming

KW - Randomized rounding

KW - Robust optimization

UR - http://www.scopus.com/inward/record.url?scp=85097716920&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-61792-9_3

DO - 10.1007/978-3-030-61792-9_3

M3 - Conference contribution

AN - SCOPUS:85097716920

SN - 9783030617912

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 27

EP - 37

BT - LATIN 2020

A2 - Kohayakawa, Yoshiharu

A2 - Miyazawa, Flávio Keidi

PB - Springer Science and Business Media Deutschland GmbH

T2 - 14th Latin American Symposium on Theoretical Informatics, LATIN 2020

Y2 - 5 January 2021 through 8 January 2021

ER -

Elbassioni K. Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-Relaxations. In Kohayakawa Y, Miyazawa FK, editors, LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2020. p. 27-37. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-61792-9_3

Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-Relaxations

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this