Michel X. Goemans

According to our database1, Michel X. Goemans authored at least 81 papers between 1990 and 2017.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2008, "For contributions to the theory of approximation algorithms and mathematical programming.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
Matroids Are Immune to Braess' Paradox.
Math. Oper. Res., 2017

An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem.
Operations Research, 2017

Discrete Newton's Algorithm for Parametric Submodular Function Minimization.
Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Approximating Incremental Combinatorial Optimization Problems.
Proceedings of the Approximation, 2017

2015
Congestion games viewed from M-convexity.
Oper. Res. Lett., 2015

Smallest compact formulation for the permutahedron.
Math. Program., 2015

2014
Polynomiality for Bin Packing with a Constant Number of Item Types.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013
Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations.
SIAM J. Discrete Math., 2013

2012
A flow model based on polylinking system.
Math. Program., 2012

Matroids and integrality gaps for hypergraphic steiner tree relaxations.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011
Tight Approximation Algorithms for Maximum Separable Assignment Problems.
Math. Oper. Res., 2011

2010
An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009
Approximating submodular functions everywhere.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2007
Improved Bounds on Nonblocking 3-Stage Clos Networks.
SIAM J. Comput., 2007

2006
Approximating fluid schedules in crossbar packet-switches and Banyan networks.
IEEE/ACM Trans. Netw., 2006

On the Integrality Ratio for the Asymmetric Traveling Salesman Problem.
Math. Oper. Res., 2006

Tight approximation algorithms for maximum general assignment problems.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Stochastic Covering and Adaptivity.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

The Unsplittable Stable Marriage Problem.
Proceedings of the Fourth IFIP International Conference on Theoretical Computer Science (TCS 2006), 2006

Minimum Bounded Degree Spanning Trees.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data.
Proceedings of the Algorithms, 2006

2005
Approximating the smallest k-edge connected spanning subgraph by LP-rounding.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Adaptivity and approximation for stochastic packing problems.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Sink Equilibria and Convergence.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming.
J. Comput. Syst. Sci., 2004

An approximate König's theorem for edge-coloring weighted bipartite graphs.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Trade-offs on the location of the core node in a network.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Covering minimum spanning trees of random subgraphs.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Market sharing games applied to content distribution in ad-hoc networks.
Proceedings of the 5th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, 2004

Universal Bounds on Buffer Size for Packetizing Fluid Policies in Input Queued, Crossbar Switches.
Proceedings of the Proceedings IEEE INFOCOM 2004, 2004

Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

On the Integrality Ratio for Asymmetric TSP.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2002
Single Machine Scheduling with Release Dates.
SIAM J. Discrete Math., 2002

2001
Approximate Edge Splitting.
SIAM J. Discrete Math., 2001

When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
Math. Oper. Res., 2001

Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Using Complex Semidefinite Programming for Approximating MAX E2-LIN3.
Proceedings of the Approximation, 2001

2000
A 1.47-approximation algorithm for a preemptive single-machine scheduling problem.
Oper. Res. Lett., 2000

Cooperative facility location games.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999
Semidefinite Programs and Association Schemes.
Computing, 1999

Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998
The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover.
SIAM J. Discrete Math., 1998

A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs.
Oper. Res. Lett., 1998

Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs.
Combinatorica, 1998

On the Single-Source Unsplittable Flow Problem.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
Semidefinite programming in combinatorial optimization.
Math. Program., 1997

Improved Approximation Algorithms for Scheduling with Release Dates.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996
The Constrained Minimum Spanning Tree Problem (Extended Abstract).
Proceedings of the Algorithm Theory, 1996

An Improved Approximation Ratio for the Minimum Latency Problem.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Primal-Dual Approximation Algorithms for Feedback Problems.
Proceedings of the Integer Programming and Combinatorial Optimization, 1996

The Strongest Facets of the Acyclic Subgraph Polytope Are Unknown.
Proceedings of the Integer Programming and Combinatorial Optimization, 1996

A Supermodular Relaxation for Scheduling with Release Dates.
Proceedings of the Integer Programming and Combinatorial Optimization, 1996

Improved Bounds for On-line Load Balancing.
Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

1995
Worst-case comparison of valid inequalities for the TSP.
Math. Program., 1995

Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming.
J. ACM, 1995

An Approximation Algorithm for Scheduling on Three Dedicated Machines.
Discrete Applied Mathematics, 1995

Minimizing Submodular Functions over Families of Sets.
Combinatorica, 1995

Aproximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DICUT.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

1994
New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem.
SIAM J. Discrete Math., 1994

Approximating minimum-cost graph problems with spanning tree edges.
Oper. Res. Lett., 1994

The Steiner tree polytope and related polyhedra.
Math. Program., 1994

Arborescence Polytopes for Series-parallel Graphs.
Discrete Applied Mathematics, 1994

On the Maximum Number of Triangles in Wheel-Free Graphs.
Combinatorics, Probability & Computing, 1994

.879-approximation algorithms for MAX CUT and MAX 2SAT.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Improved Approximation Algorithms for Network Design Problems.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993
A catalog of steiner tree formulations.
Networks, 1993

Survivable networks, linear programming relaxations and the parsimonious property.
Math. Program., 1993

A note on the prize collecting traveling salesman problem.
Math. Program., 1993

A Lower Bound on the Expected Cost of an Optimal Assignment.
Math. Oper. Res., 1993

A generalization of Petersen's theorem.
Discrete Mathematics, 1993

A primal-dual approximation algorithm for generalized Steiner network problems.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

A new \frac34-approximation algorithm for MAX SAT.
Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993

An efficient approximation algorithm for the survivable network design problem.
Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993

1992
A General Approximation Technique for Constrained Forest Problems.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Polyhedral Description of Trees and Arborescences.
Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference, 1992

1991
2-Change for k-connected networks.
Oper. Res. Lett., 1991

Probabilistic Analysis of the Held and Karp Lower Bound for the Euclidean Traveling Salesman Problem.
Math. Oper. Res., 1991

1990
On the Parsimonious Property of Connectivity Problems.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990


  Loading...