Michel X. Goemans

According to our database, Michel X. Goemans authored at least 92 papers between 1990 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

Shrunk subspaces via operator Sinkhorn iteration.

Cole Franks, Tasuku Soma, Michel X. Goemans

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2020

Polynomiality for Bin Packing with a Constant Number of Item Types.

Michel X. Goemans, Thomas Rothvoss

J. ACM, 2020

2019

Doubly-Efficient Pseudo-Deterministic Proofs.

Michel X. Goemans, Shafi Goldwasser, Dhiraj Holden

Electron. Colloquium Comput. Complex., 2019

2018

Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach.

Chiheon Kim, Afonso S. Bandeira, Michel X. Goemans

CoRR, 2018

2017

Matroids Are Immune to Braess' Paradox.

Satoru Fujishige, Michel X. Goemans, Tobias Harks, Britta Peis, Rico Zenklusen

Math. Oper. Res., 2017

An <i>O</i>(log <i>n</i>/log log <i>n</i>)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem.

Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi

Oper. Res., 2017

Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares.

Chiheon Kim, Afonso S. Bandeira, Michel X. Goemans

CoRR, 2017

Discrete Newton's Algorithm for Parametric Submodular Function Minimization.

Michel X. Goemans, Swati Gupta, Patrick Jaillet

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Approximating Incremental Combinatorial Optimization Problems.

Michel X. Goemans, Francisco Unda

Proceedings of the Approximation, 2017

2016

Solving Combinatorial Games using Products, Projections and Lexicographically Optimal Bases.

Swati Gupta, Michel X. Goemans, Patrick Jaillet

CoRR, 2016

2015

Congestion games viewed from M-convexity.

Satoru Fujishige, Michel X. Goemans, Tobias Harks, Britta Peis, Rico Zenklusen

Oper. Res. Lett., 2015

Smallest compact formulation for the permutahedron.

Michel X. Goemans

Math. Program., 2015

2014

Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs.

Wang Chi Cheung, Michel X. Goemans, Sam Chiu-wai Wong

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.

Michel X. Goemans, José A. Soto

SIAM J. Discret. Math., 2013

2012

A flow model based on polylinking system.

Michel X. Goemans, Satoru Iwata, Rico Zenklusen

Math. Program., 2012

Matroids and integrality gaps for hypergraphic steiner tree relaxations.

Michel X. Goemans, Neil Olver, Thomas Rothvoß, Rico Zenklusen

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

Tight Approximation Algorithms for Maximum Separable Assignment Problems.

Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko

Math. Oper. Res., 2011

2010

Symmetric Submodular Function Minimization Under Hereditary Family Constraints

Michel X. Goemans, José A. Soto

CoRR, 2010

An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem.

Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

Approximating the smallest <i>k</i>-edge connected spanning subgraph by LP-rounding.

Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson

Networks, 2009

Combining Approximation Algorithms for the Prize-Collecting TSP

Michel X. Goemans

CoRR, 2009

A Randomized Rounding Algorithm for the Asymmetric Traveling Salesman Problem

Michel X. Goemans, Nicholas J. A. Harvey, Kamal Jain, Mohit Singh

CoRR, 2009

Approximating submodular functions everywhere.

Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, Vahab S. Mirrokni

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

An algorithmic framework for wireless information flow.

Michel X. Goemans, Satoru Iwata, Rico Zenklusen

Proceedings of the 47th Annual Allerton Conference on Communication, 2009

2008

Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity.

Brian C. Dean, Michel X. Goemans, Jan Vondrák

Math. Oper. Res., 2008

2007

Improved Bounds on Nonblocking 3-Stage Clos Networks.

José R. Correa, Michel X. Goemans

SIAM J. Comput., 2007

2006

Approximating fluid schedules in crossbar packet-switches and Banyan networks.

Michael Rosenblum, Constantine Caramanis, Michel X. Goemans, Vahid Tarokh

IEEE/ACM Trans. Netw., 2006

Covering minimum spanning trees of random subgraphs.

Michel X. Goemans, Jan Vondrák

Random Struct. Algorithms, 2006

On the Integrality Ratio for the Asymmetric Traveling Salesman Problem.

Moses Charikar, Michel X. Goemans, Howard J. Karloff

Math. Oper. Res., 2006

Market sharing games applied to content distribution in ad hoc networks.

Michel X. Goemans, Li (Erran) Li, Vahab S. Mirrokni, Marina Thottan

IEEE J. Sel. Areas Commun., 2006

Tight approximation algorithms for maximum general assignment problems.

Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Stochastic Covering and Adaptivity.

Michel X. Goemans, Jan Vondrák

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

The Unsplittable Stable Marriage Problem.

Brian C. Dean, Michel X. Goemans, Nicole Immorlica

Proceedings of the Fourth IFIP International Conference on Theoretical Computer Science (TCS 2006), 2006

Minimum Bounded Degree Spanning Trees.

Michel X. Goemans

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.

Brian C. Dean, Michel X. Goemans, Nicole Immorlica

Proceedings of the Algorithms, 2006

2005

Adaptivity and approximation for stochastic packing problems.

Brian C. Dean, Michel X. Goemans, Jan Vondrák

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Sink Equilibria and Convergence.

Michel X. Goemans, Vahab S. Mirrokni, Adrian Vetta

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

Trade-offs on the location of the core node in a network.

Jean-François Macq, Michel X. Goemans

Networks, 2004

Approximation algorithms for M_AX-3-C_UT and other problems via complex semidefinite programming.

Michel X. Goemans, David P. Williamson

J. Comput. Syst. Sci., 2004

Cooperative facility location games.

Michel X. Goemans, Martin Skutella

J. Algorithms, 2004

An approximate König's theorem for edge-coloring weighted bipartite graphs.

José R. Correa, Michel X. Goemans

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Universal Bounds on Buffer Size for Packetizing Fluid Policies in Input Queued, Crossbar Switches.

Michael Rosenblum, Michel X. Goemans, Vahid Tarokh

Proceedings of the Proceedings IEEE INFOCOM 2004, 2004

On the Integrality Ratio for Asymmetric TSP.

Moses Charikar, Michel X. Goemans, Howard J. Karloff

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

Wide partitions, Latin tableaux, and Rota's basis conjecture.

Timothy Y. Chow, C. Kenneth Fan, Michel X. Goemans, Jan Vondrák

Adv. Appl. Math., 2003

Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling.

Brian C. Dean, Michel X. Goemans

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2002

Single Machine Scheduling with Release Dates.

Michel X. Goemans, Maurice Queyranne, Andreas S. Schulz, Martin Skutella, Yaoguang Wang

SIAM J. Discret. Math., 2002

2001

Approximate Edge Splitting.

Michel X. Goemans

SIAM J. Discret. Math., 2001

When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?

Michel X. Goemans, Levent Tunçel

Math. Oper. Res., 2001

Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming.

Michel X. Goemans, David P. Williamson

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Using Complex Semidefinite Programming for Approximating MAX E2-LIN3.

Michel X. Goemans

Proceedings of the Approximation, 2001

2000

Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler.

Michel X. Goemans, David P. Williamson

SIAM J. Discret. Math., 2000

A 1.47-approximation algorithm for a preemptive single-machine scheduling problem.

Michel X. Goemans, Joel Wein, David P. Williamson

Oper. Res. Lett., 2000

1999

Semidefinite Programs and Association Schemes.

Michel X. Goemans, Franz Rendl

Computing, 1999

On the Single-Source Unsplittable Flow Problem.

Yefim Dinitz, Naveen Garg, Michel X. Goemans

Comb., 1999

Improved Bounds for On-Line Load Balancing.

Matthew Andrews, Michel X. Goemans, Lisa Zhang

Algorithmica, 1999

1998

The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover.

Jon M. Kleinberg, Michel X. Goemans

SIAM J. Discret. Math., 1998

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

Fabián A. Chudak, Michel X. Goemans, Dorit S. Hochbaum, David P. Williamson

Oper. Res. Lett., 1998

An improved approximation ratio for the minimum latency problem.

Michel X. Goemans, Jon M. Kleinberg

Math. Program., 1998

An efficient approximation algorithm for the survivable network design problem.

Harold N. Gabow, Michel X. Goemans, David P. Williamson

Math. Program., 1998

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

Michel X. Goemans, David P. Williamson

Comb., 1998

1997

Semidefinite programming in combinatorial optimization.

Michel X. Goemans

Math. Program., 1997

Improved Approximation Algorithms for Scheduling with Release Dates.

Michel X. Goemans

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996

Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances.

David P. Williamson, Michel X. Goemans

INFORMS J. Comput., 1996

The Constrained Minimum Spanning Tree Problem (Extended Abstract).

R. Ravi, Michel X. Goemans

Proceedings of the Algorithm Theory, 1996

Primal-Dual Approximation Algorithms for Feedback Problems.

Michel X. Goemans, David P. Williamson

Proceedings of the Integer Programming and Combinatorial Optimization, 1996

The Strongest Facets of the Acyclic Subgraph Polytope Are Unknown.

Michel X. Goemans, Leslie A. Hall

Proceedings of the Integer Programming and Combinatorial Optimization, 1996

A Supermodular Relaxation for Scheduling with Release Dates.

Michel X. Goemans

Proceedings of the Integer Programming and Combinatorial Optimization, 1996

1995

A General Approximation Technique for Constrained Forest Problems.

Michel X. Goemans, David P. Williamson

SIAM J. Comput., 1995

Worst-case comparison of valid inequalities for the TSP.

Michel X. Goemans

Math. Program., 1995

Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming.

Michel X. Goemans, David P. Williamson

J. ACM, 1995

An Approximation Algorithm for Scheduling on Three Dedicated Machines.

Michel X. Goemans

Discret. Appl. Math., 1995

A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems.

David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani

Comb., 1995

Minimizing Submodular Functions over Families of Sets.

Michel X. Goemans, V. S. Ramakrishnan

Comb., 1995

Aproximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DICUT.

Uriel Feige, Michel X. Goemans

Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

1994

New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem.

Michel X. Goemans, David P. Williamson

SIAM J. Discret. Math., 1994

Approximating minimum-cost graph problems with spanning tree edges.

Michel X. Goemans, David P. Williamson

Oper. Res. Lett., 1994

The Steiner tree polytope and related polyhedra.

Michel X. Goemans

Math. Program., 1994

Arborescence Polytopes for Series-parallel Graphs.

Michel X. Goemans

Discret. Appl. Math., 1994

On the Maximum Number of Triangles in Wheel-Free Graphs.

Zoltán Füredi, Michel X. Goemans, Daniel J. Kleitman

Comb. Probab. Comput., 1994

Number of faults a system can withstand without repairs.

Michel X. Goemans, Nancy A. Lynch, Isaac Saias

CoRR, 1994

.879-approximation algorithms for MAX CUT and MAX 2SAT.

Michel X. Goemans, David P. Williamson

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Improved Approximation Algorithms for Network Design Problems.

Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, David P. Williamson

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993

A catalog of steiner tree formulations.

Michel X. Goemans, Young-Soo Myung

Networks, 1993

Survivable networks, linear programming relaxations and the parsimonious property.

Michel X. Goemans, Dimitris Bertsimas

Math. Program., 1993

A note on the prize collecting traveling salesman problem.

Daniel Bienstock, Michel X. Goemans, David Simchi-Levi, David P. Williamson

Math. Program., 1993

A Lower Bound on the Expected Cost of an Optimal Assignment.

Michel X. Goemans, Muralidharan S. Kodialam

Math. Oper. Res., 1993

A generalization of Petersen's theorem.

Michel X. Goemans

Discret. Math., 1993

A new \frac34-approximation algorithm for MAX SAT.

Michel X. Goemans, David P. Williamson

Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993

1992

Polyhedral Description of Trees and Arborescences.

Michel X. Goemans

Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference, 1992

1991

2-Change for k-connected networks.

Michel X. Goemans, Kalyan T. Talluri

Oper. Res. Lett., 1991

Probabilistic Analysis of the Held and Karp Lower Bound for the Euclidean Traveling Salesman Problem.

Michel X. Goemans, Dimitris J. Bertsimas

Math. Oper. Res., 1991

1990

On the Parsimonious Property of Connectivity Problems.

Michel X. Goemans, Dimitris Bertsimas

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990