arXiv Open Access 2019

Some Black-box Reductions for Objective-robust Discrete Optimization Problems Based on their LP-Relaxations

Khaled Elbassioni

Lihat Sumber

Abstrak

We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. We show how an integrality gap verifier for the linear programming relaxation of the non-robust version of the problem can be used to derive approximation algorithms for the robust version.

Topik & Kata Kunci

cs.DS math.OC

Penulis (1)

Khaled Elbassioni

Format Sitasi

APA MLA BibTeX

Elbassioni, K. (2019). Some Black-box Reductions for Objective-robust Discrete Optimization Problems Based on their LP-Relaxations. https://arxiv.org/abs/1907.06786

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2019
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓