Goemans Michel X.

Michel X. Goemans

Information about the author Michel X. Goemans will soon be added to the site.
Found 15 papers in total
A 1.47-approximation algorithm for a preemptive single-machine scheduling problem
A 1.47-approximation algorithm for a preemptive single-machine scheduling problem
2000
In this note, we give a 1.47-approximation algorithm for the preemtpive scheduling of...
An improved approximation ratio for the minimum latency problem
An improved approximation ratio for the minimum latency problem
1998
Given a tour visiting n points in a metric space, the latency of one of these points p...
An efficient approximation algorithm for the survivable network design problem
An efficient approximation algorithm for the survivable network design problem
1998
The survivable network design problem is to construct a minimum-cost subgraph...
Semidefinite programming in combinatorial optimization
Semidefinite programming in combinatorial optimization
1997
We discuss the use of semidefinite programming for combinatorial optimization...
Computational experience with an approximation algorithm on large-scale Euclidean matching instances
Computational experience with an approximation algorithm on large-scale Euclidean matching instances
1996
We consider a 2-approximation algorithm for Euclidean minimum-cost perfect matching...
Computational experience with an approximation algorithm on large-scale Euclidean matching instances
Computational experience with an approximation algorithm on large-scale Euclidean matching instances
1996
The authors consider a 2-approximation algorithm for Euclidean minimum-cost perfect...
Worst-case comparison of valid inequalities for the TSP
Worst-case comparison of valid inequalities for the TSP
1995
The paper considers most of the known classes of valid inequalities for the graphical...
Approximating minimum-cost graph problems with spanning tree edges
Approximating minimum-cost graph problems with spanning tree edges
1994
Building on work of Imielinska, Kalantari and Khachiyan, the authors show how to find...
The Steiner tree polytope and related polyhedra
The Steiner tree polytope and related polyhedra
1994
The paper considers the vertex-weighted version of the undirected Steiner tree...
Arborescence polytopes for series-parallel graphs
Arborescence polytopes for series-parallel graphs
1994
This paper considers some polytopes associated with arborescences in a series-parallel...
A note on the prize collecting traveling salesman problem
A note on the prize collecting traveling salesman problem
1993
The authors study the version of the prize collecting traveling salesman problem,...
Survivable networks, linear programming relaxations and the parsimonious property
Survivable networks, linear programming relaxations and the parsimonious property
1993
The authors consider the survivable network design problem-the problem of designing,...
2-Change for k-connected networks
2-Change for k-connected networks
1991
The authors consider the problem of designing a k- connected network at minimum...
Probabilistic analysis of the Held and Karp lower bound for the Euclidean traveling salesman problem
Probabilistic analysis of the Held and Karp lower bound for the Euclidean traveling salesman problem
1991
The authors analyze probabilistically the classical Held-Karp lower bound derived from...
Valid inequalities and separation for mixed 0-1 constraints with variable upper bounds
Valid inequalities and separation for mixed 0-1 constraints with variable upper bounds
1989
The polyhedral structure of the convex hull of regions is investigated defined by a...
Papers per page: