Michel X. Goemans

Publication Activity (10 Years)

Years Active: 1990-2023
Publications (10 Years): 15

Top Venues

CoRR

SODA

Oper. Res. Lett.

APPROX-RANDOM

Publications

Cole Franks, Tasuku Soma, Michel X. Goemans
Shrunk subspaces via operator Sinkhorn iteration. SODA (2023)
Cole Franks, Tasuku Soma, Michel X. Goemans
Shrunk subspaces via operator Sinkhorn iteration. CoRR (2022)
Michel X. Goemans, Thomas Rothvoss
Polynomiality for Bin Packing with a Constant Number of Item Types. J. ACM 67 (6) (2020)
Michel X. Goemans, Shafi Goldwasser, Dhiraj Holden
Doubly-Efficient Pseudo-Deterministic Proofs. Electron. Colloquium Comput. Complex. 26 (2019)
Michel X. Goemans, Shafi Goldwasser, Dhiraj Holden
Doubly-Efficient Pseudo-Deterministic Proofs. CoRR (2019)
Chiheon Kim, Afonso S. Bandeira, Michel X. Goemans
Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach. CoRR (2018)
Michel X. Goemans, Francisco Unda
Approximating Incremental Combinatorial Optimization Problems. APPROX-RANDOM (2017)
Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi
)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem. Oper. Res. 65 (4) (2017)
Satoru Fujishige, Michel X. Goemans, Tobias Harks, Britta Peis, Rico Zenklusen
Matroids Are Immune to Braess' Paradox. Math. Oper. Res. 42 (3) (2017)
Michel X. Goemans, Swati Gupta, Patrick Jaillet
Discrete Newton's Algorithm for Parametric Submodular Function Minimization. IPCO (2017)
Chiheon Kim, Afonso S. Bandeira, Michel X. Goemans
Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares. CoRR (2017)
Swati Gupta, Michel X. Goemans, Patrick Jaillet
Solving Combinatorial Games using Products, Projections and Lexicographically Optimal Bases. CoRR (2016)
Satoru Fujishige, Michel X. Goemans, Tobias Harks, Britta Peis, Rico Zenklusen
Congestion games viewed from M-convexity. Oper. Res. Lett. 43 (3) (2015)
Satoru Fujishige, Michel X. Goemans, Tobias Harks, Britta Peis, Rico Zenklusen
Matroids are Immune to Braess Paradox. CoRR (2015)
Michel X. Goemans
Smallest compact formulation for the permutahedron. Math. Program. 153 (1) (2015)
Wang Chi Cheung, Michel X. Goemans, Sam Chiu-wai Wong
Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs. SODA (2014)
Michel X. Goemans, Thomas Rothvoß
Polynomiality for Bin Packing with a Constant Number of Item Types. SODA (2014)
Michel X. Goemans, José A. Soto
Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations. SIAM J. Discret. Math. 27 (2) (2013)
Michel X. Goemans, Thomas Rothvoß
Polynomiality for Bin Packing with a Constant Number of Item Types. CoRR (2013)
Michel X. Goemans, Neil Olver, Thomas Rothvoß, Rico Zenklusen
Matroids and integrality gaps for hypergraphic steiner tree relaxations. STOC (2012)
Michel X. Goemans, Satoru Iwata, Rico Zenklusen
A flow model based on polylinking system. Math. Program. 135 (1-2) (2012)
Michel X. Goemans, Neil Olver, Thomas Rothvoß, Rico Zenklusen
Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations CoRR (2011)
Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko
Tight Approximation Algorithms for Maximum Separable Assignment Problems. Math. Oper. Res. 36 (3) (2011)
Michel X. Goemans, José A. Soto
Symmetric Submodular Function Minimization Under Hereditary Family Constraints CoRR (2010)
Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi
An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem. SODA (2010)
Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, Vahab S. Mirrokni
Approximating submodular functions everywhere. SODA (2009)
Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson
-edge connected spanning subgraph by LP-rounding. Networks 53 (4) (2009)
Michel X. Goemans
Combining Approximation Algorithms for the Prize-Collecting TSP CoRR (2009)
Michel X. Goemans, Nicholas J. A. Harvey, Kamal Jain, Mohit Singh
A Randomized Rounding Algorithm for the Asymmetric Traveling Salesman Problem CoRR (2009)
Michel X. Goemans, Satoru Iwata, Rico Zenklusen
An algorithmic framework for wireless information flow. Allerton (2009)
Brian C. Dean, Michel X. Goemans, Jan Vondrák
Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity. Math. Oper. Res. 33 (4) (2008)
José R. Correa, Michel X. Goemans
Improved Bounds on Nonblocking 3-Stage Clos Networks. SIAM J. Comput. 37 (3) (2007)
Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko
Tight approximation algorithms for maximum general assignment problems. SODA (2006)
Michael Rosenblum, Constantine Caramanis, Michel X. Goemans, Vahid Tarokh
Approximating fluid schedules in crossbar packet-switches and Banyan networks. IEEE/ACM Trans. Netw. 14 (6) (2006)
Michel X. Goemans, Erran L. Li, Vahab S. Mirrokni, Marina Thottan
Market sharing games applied to content distribution in ad hoc networks. IEEE J. Sel. Areas Commun. 24 (5) (2006)
Brian C. Dean, Michel X. Goemans, Nicole Immorlica
Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data. ESA (2006)
Brian C. Dean, Michel X. Goemans, Nicole Immorlica
The Unsplittable Stable Marriage Problem. IFIP TCS (2006)
Moses Charikar, Michel X. Goemans, Howard J. Karloff
On the Integrality Ratio for the Asymmetric Traveling Salesman Problem. Math. Oper. Res. 31 (2) (2006)
Michel X. Goemans, Jan Vondrák
Stochastic Covering and Adaptivity. LATIN (2006)
Michel X. Goemans
Minimum Bounded Degree Spanning Trees. FOCS (2006)
Michel X. Goemans, Jan Vondrák
Covering minimum spanning trees of random subgraphs. Random Struct. Algorithms 29 (3) (2006)
Michel X. Goemans, Vahab S. Mirrokni, Adrian Vetta
Sink Equilibria and Convergence. FOCS (2005)
Brian C. Dean, Michel X. Goemans, Jan Vondrák
Adaptivity and approximation for stochastic packing problems. SODA (2005)
Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson
-edge connected spanning subgraph by LP-rounding. SODA (2005)
Michel X. Goemans, David P. Williamson
and other problems via complex semidefinite programming. J. Comput. Syst. Sci. 68 (2) (2004)
Michel X. Goemans, Erran L. Li, Vahab S. Mirrokni, Marina Thottan
Market sharing games applied to content distribution in ad-hoc networks. MobiHoc (2004)
Michael Rosenblum, Michel X. Goemans, Vahid Tarokh
Universal Bounds on Buffer Size for Packetizing Fluid Policies in Input Queued, Crossbar Switches. INFOCOM (2004)
Jean-François Macq, Michel X. Goemans
Trade-offs on the location of the core node in a network. SODA (2004)
Brian C. Dean, Michel X. Goemans, Jan Vondrák
Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity. FOCS (2004)
Moses Charikar, Michel X. Goemans, Howard J. Karloff
On the Integrality Ratio for Asymmetric TSP. FOCS (2004)
Michel X. Goemans, Jan Vondrák
Covering minimum spanning trees of random subgraphs. SODA (2004)
José R. Correa, Michel X. Goemans
An approximate König's theorem for edge-coloring weighted bipartite graphs. STOC (2004)
Jean-François Macq, Michel X. Goemans
Trade-offs on the location of the core node in a network. Networks 44 (3) (2004)
Michel X. Goemans, Martin Skutella
Cooperative facility location games. J. Algorithms 50 (2) (2004)
Brian C. Dean, Michel X. Goemans
Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling. ICALP (2003)
Timothy Y. Chow, C. Kenneth Fan, Michel X. Goemans, Jan Vondrák
Wide partitions, Latin tableaux, and Rota's basis conjecture. Adv. Appl. Math. 31 (2) (2003)
Michel X. Goemans, Maurice Queyranne, Andreas S. Schulz, Martin Skutella, Yaoguang Wang
Single Machine Scheduling with Release Dates. SIAM J. Discret. Math. 15 (2) (2002)
Michel X. Goemans
Approximate Edge Splitting. SIAM J. Discret. Math. 14 (1) (2001)
Michel X. Goemans, Levent Tunçel
When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures? Math. Oper. Res. 26 (4) (2001)
Michel X. Goemans
Using Complex Semidefinite Programming for Approximating MAX E2-LIN3. RANDOM-APPROX (2001)
Michel X. Goemans, David P. Williamson
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. STOC (2001)
Michel X. Goemans, Joel Wein, David P. Williamson
A 1.47-approximation algorithm for a preemptive single-machine scheduling problem. Oper. Res. Lett. 26 (4) (2000)
Michel X. Goemans, Martin Skutella
Cooperative facility location games. SODA (2000)
Michel X. Goemans, David P. Williamson
Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. SIAM J. Discret. Math. 13 (3) (2000)
Yefim Dinitz, Naveen Garg, Michel X. Goemans
On the Single-Source Unsplittable Flow Problem. Comb. 19 (1) (1999)
Michel X. Goemans, Franz Rendl
Semidefinite Programs and Association Schemes. Computing 63 (4) (1999)
Michel X. Goemans, David P. Williamson
Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. SODA (1999)
Matthew Andrews, Michel X. Goemans, Lisa Zhang
Improved Bounds for On-Line Load Balancing. Algorithmica 23 (4) (1999)
Yefim Dinitz, Naveen Garg, Michel X. Goemans
On the Single-Source Unsplittable Flow Problem. FOCS (1998)
Michel X. Goemans, David P. Williamson
Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs. Comb. 18 (1) (1998)
Fabián A. Chudak, Michel X. Goemans, Dorit S. Hochbaum, David P. Williamson
A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett. 22 (4-5) (1998)
Jon M. Kleinberg, Michel X. Goemans
The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover. SIAM J. Discret. Math. 11 (2) (1998)
Harold N. Gabow, Michel X. Goemans, David P. Williamson
An efficient approximation algorithm for the survivable network design problem. Math. Program. 82 (1998)
Michel X. Goemans, Jon M. Kleinberg
An improved approximation ratio for the minimum latency problem. Math. Program. 82 (1998)
Michel X. Goemans
Semidefinite programming in combinatorial optimization. Math. Program. 79 (1997)
Michel X. Goemans
Improved Approximation Algorithms for Scheduling with Release Dates. SODA (1997)
R. Ravi, Michel X. Goemans
The Constrained Minimum Spanning Tree Problem (Extended Abstract). SWAT (1996)
Matthew Andrews, Michel X. Goemans, Lisa Zhang
Improved Bounds for On-line Load Balancing. COCOON (1996)
Michel X. Goemans
A Supermodular Relaxation for Scheduling with Release Dates. IPCO (1996)
Michel X. Goemans, Leslie A. Hall
The Strongest Facets of the Acyclic Subgraph Polytope Are Unknown. IPCO (1996)
Michel X. Goemans, David P. Williamson
Primal-Dual Approximation Algorithms for Feedback Problems. IPCO (1996)
Michel X. Goemans, Jon M. Kleinberg
An Improved Approximation Ratio for the Minimum Latency Problem. SODA (1996)
David P. Williamson, Michel X. Goemans
Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. INFORMS J. Comput. 8 (1) (1996)
Michel X. Goemans, David P. Williamson
Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42 (6) (1995)
Michel X. Goemans
Worst-case comparison of valid inequalities for the TSP. Math. Program. 69 (1995)
Michel X. Goemans, David P. Williamson
A General Approximation Technique for Constrained Forest Problems. SIAM J. Comput. 24 (2) (1995)
Michel X. Goemans, V. S. Ramakrishnan
Minimizing Submodular Functions over Families of Sets. Comb. 15 (4) (1995)
David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani
A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems. Comb. 15 (3) (1995)
Uriel Feige, Michel X. Goemans
Aproximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DICUT. ISTCS (1995)
Michel X. Goemans
An Approximation Algorithm for Scheduling on Three Dedicated Machines. Discret. Appl. Math. 61 (1) (1995)
Michel X. Goemans, David P. Williamson
Approximating minimum-cost graph problems with spanning tree edges. Oper. Res. Lett. 16 (4) (1994)
David P. Williamson, Michel X. Goemans
Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. SODA (1994)
Michel X. Goemans, Nancy A. Lynch, Isaac Saias
Number of faults a system can withstand without repairs. CoRR (1994)
Michel X. Goemans
Arborescence Polytopes for Series-parallel Graphs. Discret. Appl. Math. 51 (3) (1994)
Michel X. Goemans, David P. Williamson
New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem. SIAM J. Discret. Math. 7 (4) (1994)
Michel X. Goemans, David P. Williamson
.879-approximation algorithms for MAX CUT and MAX 2SAT. STOC (1994)
Zoltán Füredi, Michel X. Goemans, Daniel J. Kleitman
On the Maximum Number of Triangles in Wheel-Free Graphs. Comb. Probab. Comput. 3 (1994)
Michel X. Goemans
The Steiner tree polytope and related polyhedra. Math. Program. 63 (1994)
Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, David P. Williamson
Improved Approximation Algorithms for Network Design Problems. SODA (1994)
Daniel Bienstock, Michel X. Goemans, David Simchi-Levi, David P. Williamson
A note on the prize collecting traveling salesman problem. Math. Program. 59 (1993)

Michel X. Goemans.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Michel X. Goemans