Michel X. Goemans

Michel X. Goemans, José R. Correa (Eds.): Integer Programming and Combinatorial Optimization - 16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings. Lecture Notes in Computer Science 7801, Springer 2013, isbn 978-3-642-36693-2

Michel X. Goemans, Satoru Iwata, Rico Zenklusen: A flow model based on polylinking system. Math. Program. 135(1-2): 1-23 (2012)

Michel X. Goemans, Neil Olver, Thomas Rothvoß, Rico Zenklusen: Matroids and integrality gaps for hypergraphic steiner tree relaxations. STOC 2012: 1161-1176

Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko: Tight Approximation Algorithms for Maximum Separable Assignment Problems. Math. Oper. Res. 36(3): 416-431 (2011)

Michel X. Goemans, Neil Olver, Thomas Rothvoß, Rico Zenklusen: Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations. CoRR abs/1111.7280 (2011)

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: 379-389

Michel X. Goemans, José A. Soto: Symmetric Submodular Function Minimization Under Hereditary Family Constraints. CoRR abs/1007.2140 (2010)

Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson: Approximating the smallest k-edge connected spanning subgraph by LP-rounding. Networks 53(4): 345-357 (2009)

Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, Vahab S. Mirrokni: Approximating submodular functions everywhere. SODA 2009: 535-544

Michel X. Goemans, Nicholas J. A. Harvey, Kamal Jain, Mohit Singh: A Randomized Rounding Algorithm for the Asymmetric Traveling Salesman Problem. CoRR abs/0909.0941 (2009)

Michel X. Goemans: Combining Approximation Algorithms for the Prize-Collecting TSP. CoRR abs/0910.0553 (2009)

Brian C. Dean, Michel X. Goemans, Jan Vondrák: Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity. Math. Oper. Res. 33(4): 945-964 (2008)

José R. Correa, Michel X. Goemans: Improved Bounds on Nonblocking 3-Stage Clos Networks. SIAM J. Comput. 37(3): 870-894 (2007)

Michel X. Goemans, Li Li, Vahab S. Mirrokni, Marina Thottan: Market sharing games applied to content distribution in ad hoc networks. IEEE Journal on Selected Areas in Communications 24(5): 1020-1033 (2006)

Moses Charikar, Michel X. Goemans, Howard J. Karloff: On the Integrality Ratio for the Asymmetric Traveling Salesman Problem. Math. Oper. Res. 31(2): 245-252 (2006)

Michel X. Goemans, Jan Vondrák: Covering minimum spanning trees of random subgraphs. Random Struct. Algorithms 29(3): 257-276 (2006)

Michael Rosenblum, Constantine Caramanis, Michel X. Goemans, Vahid Tarokh: Approximating fluid schedules in crossbar packet-switches and Banyan networks. IEEE/ACM Trans. Netw. 16(6): 1374-1387 (2006)

Brian C. Dean, Michel X. Goemans, Nicole Immorlica: Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data. ESA 2006: 268-279

Michel X. Goemans: Minimum Bounded Degree Spanning Trees. FOCS 2006: 273-282

Brian C. Dean, Michel X. Goemans, Nicole Immorlica: The Unsplittable Stable Marriage Problem. IFIP TCS 2006: 65-75

Michel X. Goemans, Jan Vondrák: Stochastic Covering and Adaptivity. LATIN 2006: 532-543

Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko: Tight approximation algorithms for maximum general assignment problems. SODA 2006: 611-620

Michel X. Goemans, Vahab S. Mirrokni, Adrian Vetta: Sink Equilibria and Convergence. FOCS 2005: 142-154

Brian C. Dean, Michel X. Goemans, Jan Vondrák: Adaptivity and approximation for stochastic packing problems. SODA 2005: 395-404

Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson: Approximating the smallest k-edge connected spanning subgraph by LP-rounding. SODA 2005: 562-571

Michel X. Goemans, Martin Skutella: Cooperative facility location games. J. Algorithms 50(2): 194-214 (2004)

Michel X. Goemans, David P. Williamson: Approximation algorithms for M_AX-3-C_UT and other problems via complex semidefinite programming. J. Comput. Syst. Sci. 68(2): 442-470 (2004)

Jean-François Macq, Michel X. Goemans: Trade-offs on the location of the core node in a network. Networks 44(3): 179-186 (2004)

Moses Charikar, Michel X. Goemans, Howard J. Karloff: On the Integrality Ratio for Asymmetric TSP. FOCS 2004: 101-107

Brian C. Dean, Michel X. Goemans, Jan Vondrák: Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity. FOCS 2004: 208-217

Michael Rosenblum, Michel X. Goemans, Vahid Tarokh: Universal Bounds on Buffer Size for Packetizing Fluid Policies in Input Queued, Crossbar Switches. INFOCOM 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: 55-66

Jean-François Macq, Michel X. Goemans: Trade-offs on the location of the core node in a network. SODA 2004: 597-604

Michel X. Goemans, Jan Vondrák: Covering minimum spanning trees of random subgraphs. SODA 2004: 934-941

José R. Correa, Michel X. Goemans: An approximate König's theorem for edge-coloring weighted bipartite graphs. STOC 2004: 398-406

Brian C. Dean, Michel X. Goemans: Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling. ICALP 2003: 1138-1152

Lawrence L. Larmore, Michel X. Goemans (Eds.): Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA. ACM 2003, isbn 1-58113-674-9

Michel X. Goemans, Maurice Queyranne, Andreas S. Schulz, Martin Skutella, Yaoguang Wang: Single Machine Scheduling with Release Dates. SIAM J. Discrete Math. 15(2): 165-192 (2002)

Michel X. Goemans, Levent Tunçel: When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures? Math. Oper. Res. 26(4): 796-815 (2001)

Michel X. Goemans: Approximate Edge Splitting. SIAM J. Discrete Math. 14(1): 138-141 (2001)

Michel X. Goemans: Using Complex Semidefinite Programming for Approximating MAX E2-LIN3. RANDOM-APPROX 2001: 1

Michel X. Goemans, David P. Williamson: Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. STOC 2001: 443-452

Michel X. Goemans, Klaus Jansen, José D. P. Rolim, Luca Trevisan (Eds.): 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. Lecture Notes in Computer Science 2129, Springer 2001, isbn 3-540-42470-9

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): 149-154 (2000)

Michel X. Goemans, David P. Williamson: Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. SIAM J. Discrete Math. 13(3): 281-294 (2000)

Michel X. Goemans, Martin Skutella: Cooperative facility location games. SODA 2000: 76-85

Matthew Andrews, Michel X. Goemans, Lisa Zhang: Improved Bounds for On-Line Load Balancing. Algorithmica 23(4): 278-301 (1999)

Yefim Dinitz, Naveen Garg, Michel X. Goemans: On the Single-Source Unsplittable Flow Problem. Combinatorica 19(1): 17-41 (1999)

Michel X. Goemans, Franz Rendl: Semidefinite Programs and Association Schemes. Computing 63(4): 331-340 (1999)

Michel X. Goemans, David P. Williamson: Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. SODA 1999: 366-375

Michel X. Goemans, David P. Williamson: Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs. Combinatorica 18(1): 37-59 (1998)

Harold N. Gabow, Michel X. Goemans, David P. Williamson: An efficient approximation algorithm for the survivable network design problem. Math. Program. 82: 13-40 (1998)

Michel X. Goemans, Jon M. Kleinberg: An improved approximation ratio for the minimum latency problem. Math. Program. 82: 111-124 (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): 111-118 (1998)

Jon M. Kleinberg, Michel X. Goemans: The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover. SIAM J. Discrete Math. 11(2): 196-204 (1998)

Yefim Dinitz, Naveen Garg, Michel X. Goemans: On the Single-Source Unsplittable Flow Problem. FOCS 1998: 290-299

Michel X. Goemans: Semidefinite programming in combinatorial optimization. Math. Program. 79: 143-161 (1997)

Michel X. Goemans: Improved Approximation Algorithms for Scheduling with Release Dates. SODA 1997: 591-598

David P. Williamson, Michel X. Goemans: Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. INFORMS Journal on Computing 8(1): 29-40 (1996)

Matthew Andrews, Michel X. Goemans, Lisa Zhang: Improved Bounds for On-line Load Balancing. COCOON 1996: 1-10

Michel X. Goemans, David P. Williamson: Primal-Dual Approximation Algorithms for Feedback Problems. IPCO 1996: 147-161

Michel X. Goemans: A Supermodular Relaxation for Scheduling with Release Dates. IPCO 1996: 288-300

Michel X. Goemans, Leslie A. Hall: The Strongest Facets of the Acyclic Subgraph Polytope Are Unknown. IPCO 1996: 415-429

Michel X. Goemans, Jon M. Kleinberg: An Improved Approximation Ratio for the Minimum Latency Problem. SODA 1996: 152-158

R. Ravi, Michel X. Goemans: The Constrained Minimum Spanning Tree Problem (Extended Abstract). SWAT 1996: 66-75

David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani: A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems. Combinatorica 15(3): 435-454 (1995)

Michel X. Goemans, V. S. Ramakrishnan: Minimizing Submodular Functions over Families of Sets. Combinatorica 15(4): 499-513 (1995)

Michel X. Goemans: An Approximation Algorithm for Scheduling on Three Dedicated Machines. Discrete Applied Mathematics 61(1): 49-59 (1995)

Michel X. Goemans, David P. Williamson: Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42(6): 1115-1145 (1995)

Michel X. Goemans: Worst-case comparison of valid inequalities for the TSP. Math. Program. 69: 335-349 (1995)

Michel X. Goemans, David P. Williamson: A General Approximation Technique for Constrained Forest Problems. SIAM J. Comput. 24(2): 296-317 (1995)

Uriel Feige, Michel X. Goemans: Aproximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DICUT. ISTCS 1995: 182-189

Zoltán Füredi, Michel X. Goemans, Daniel J. Kleitman: On the Maximum Number of Triangles in Wheel-Free Graphs. Combinatorics, Probability & Computing 3: 63-75 (1994)

Michel X. Goemans: Arborescence Polytopes for Series-parallel Graphs. Discrete Applied Mathematics 51(3): 277-289 (1994)

Michel X. Goemans: The Steiner tree polytope and related polyhedra. Math. Program. 63: 157-182 (1994)

Michel X. Goemans, David P. Williamson: New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem. SIAM J. Discrete Math. 7(4): 656-666 (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: 223-232

David P. Williamson, Michel X. Goemans: Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. SODA 1994: 355-364

Michel X. Goemans, David P. Williamson: .879-approximation algorithms for MAX CUT and MAX 2SAT. STOC 1994: 422-431

Michel X. Goemans: A generalization of Petersen's theorem. Discrete Mathematics 115(1-3): 277-282 (1993)

Daniel Bienstock, Michel X. Goemans, David Simchi-Levi, David P. Williamson: A note on the prize collecting traveling salesman problem. Math. Program. 59: 413-420 (1993)

Michel X. Goemans, Dimitris Bertsimas: Survivable networks, linear programming relaxations and the parsimonious property. Math. Program. 60: 145-166 (1993)

Michel X. Goemans, Young-Soo Myung: A catalog of steiner tree formulations. Networks 23(1): 19-28 (1993)

Harold N. Gabow, Michel X. Goemans, David P. Williamson: An efficient approximation algorithm for the survivable network design problem. IPCO 1993: 57-74

Michel X. Goemans, David P. Williamson: A new \frac34-approximation algorithm for MAX SAT. IPCO 1993: 313-321

David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani: A primal-dual approximation algorithm for generalized Steiner network problems. STOC 1993: 708-717

Michel X. Goemans: Polyhedral Description of Trees and Arborescences. IPCO 1992: 1-14

Michel X. Goemans, David P. Williamson: A General Approximation Technique for Constrained Forest Problems. SODA 1992: 307-316

Michel X. Goemans, Dimitris Bertsimas: On the Parsimonious Property of Connectivity Problems. SODA 1990: 388-396