Michel X. Goemans

115 papers A* 31A 1B 10Misc 1Journal 65Unranked 6

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