No small linear program approximates vertex cover within a factor 2 - ɛ
Year of publication: |
2019
|
---|---|
Authors: | Bazzi, Abbas ; Fiorini, Samuel ; Pokutta, Sebastian ; Svensson, Ola Nils Anders |
Published in: |
Mathematics of operations research. - Catonsville, MD : INFORMS, ISSN 0364-765X, ZDB-ID 195683-8. - Vol. 44.2019, 1, p. 147-172
|
Subject: | extended formulations | hardness of approximation | independent set | linear programming | vertex cover | Theorie | Theory | Mathematische Optimierung | Mathematical programming |
-
Carousel greedy : a generalized greedy algorithm with applications in optimization
Cerrone, Carmine, (2017)
-
On polyhedral approximations of the positive semidefinite cone
Fawzi, Hamza, (2021)
-
On the extension complexity of scheduling polytopes
Tiwary, Hans Raj, (2020)
- More ...
-
Approximation limits of linear programs (beyond hierarchies)
Braun, Gábor, (2015)
-
A simple O(log log(rank))-competitive algorithm for the matroid secretary problem
Feldman, Moran, (2018)
-
Minimizing the sum of weighted completion times in a concurrent open shop
Mastrolilli, Monaldo, (2010)
- More ...