Michel X Goemans
Information about the author Michel X Goemans will soon be added to the site.
Matroids Are Immune to Braess’ Paradox
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
We present a randomized O (log n /log log n )‐approximation algorithm for the...
Tight Approximation Algorithms for Maximum Separable Assignment Problems
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
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
We consider a stochastic variant of the NP–hard 0/1 knapsack problem, in...
On the integrality ratio for the asymmetric traveling salesman problem
We improve the lower bound on the integrality ratio of the Held–Karp bound for...
Papers per page: