Goemans Michel X

Michel X Goemans

Information about the author Michel X Goemans will soon be added to the site.
Found 6 papers in total
Matroids Are Immune to Braess’ Paradox
Matroids Are Immune to Braess’ Paradox
2017
The famous Braess paradox describes the counterintuitive phenomenon in which, in...
An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
2017
We present a randomized O (log n /log log n )‐approximation algorithm for the...
Tight Approximation Algorithms for Maximum Separable Assignment Problems
Tight Approximation Algorithms for Maximum Separable Assignment Problems
2011
A separable assignment problem ( SAP ) is defined by a set of bins and a set of items...
Approximating the smallest k-edge connected spanning subgraph by LP-rounding
Approximating the smallest k-edge connected spanning subgraph by LP-rounding
2009
The smallest k-ECSS problem is, given a graph along with an integer k , find a...
Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
2008
We consider a stochastic variant of the NP–hard 0/1 knapsack problem, in...
On the integrality ratio for the asymmetric traveling salesman problem
On the integrality ratio for the asymmetric traveling salesman problem
2006
We improve the lower bound on the integrality ratio of the Held–Karp bound for...
Papers per page: