Approximation Algorithms for Cost-robust Discrete Minimization Problems Based on their LP-Relaxations

Khaled Elbassioni

doi:10.1007/s00453-022-00987-z

Approximation Algorithms for Cost-robust Discrete Minimization Problems Based on their LP-Relaxations

Khaled Elbassioni

Electrical Engineering

Research output: Contribution to journal › Article › 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
Pages (from-to)	3622-3654
Number of pages	33
Journal	Algorithmica (New York)
Volume	84
Issue number	12
DOIs	https://doi.org/10.1007/s00453-022-00987-z
State	Published - Dec 2022

Keywords

Approximation algorithms
Discrete optimization
Linear programming
Randomized rounding
Robust optimization

Access to Document

10.1007/s00453-022-00987-z

Cite this

@article{a76e5137eeb64121ab141f1e8ce3c199,

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 = "Funding Information: K. Elbassioni: Partially supported by Abu Dhabi Education & Knowledge-Abu Dhabi Award for Research Excellence (AARE18-152) Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2022",

month = dec,

doi = "10.1007/s00453-022-00987-z",

language = "British English",

volume = "84",

pages = "3622--3654",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer New York",

number = "12",

}

TY - JOUR

T1 - Approximation Algorithms for Cost-robust Discrete Minimization Problems Based on their LP-Relaxations

AU - Elbassioni, Khaled

N1 - Funding Information: K. Elbassioni: Partially supported by Abu Dhabi Education & Knowledge-Abu Dhabi Award for Research Excellence (AARE18-152) Publisher Copyright: © 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2022/12

Y1 - 2022/12

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=85131529829&partnerID=8YFLogxK

U2 - 10.1007/s00453-022-00987-z

DO - 10.1007/s00453-022-00987-z

M3 - Article

AN - SCOPUS:85131529829

SN - 0178-4617

VL - 84

SP - 3622

EP - 3654

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 12

ER -

Approximation Algorithms for Cost-robust Discrete Minimization Problems Based on their LP-Relaxations

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this