Michel X. Goemans

Leighton Family Professor of Applied Mathematics MIT, Room 2-351 Department of Mathematics Cambridge, MA 02139 USA Phone: 617-253-2688 Fax: 617-253-4358 "lastname"@math.mit.edu Member of Theory of Computation Group (TOC) at MIT Computer Science and Artificial Intelligence Laboratories (CSAIL) Member of Operations Research Center (ORC).

Short bio To prospective students/interns/postdocs Selected publications Teaching Ph.D. students Consulting Course notes GW matching algorithm

Research interests:

• Fall '08: 18.415 Advanced Algorithms
• Spring '07: 18.433 Combinatorial Optimization
• Fall '06: 18.409 Topics in Theoretical Computer Science: Metric Embeddings.
• Spring '06: 18.434 Undergraduate Seminar in Theoretical Computer Science.
• Fall '05: 18.433 Combinatorial Optimization.
• Fall '04: 18.06 Linear Algebra.
• Spring '04: 18.997: Topics in Combinatorial Optimization. See also archive on the OCW site.
• Fall '03: 18.06 Linear Algebra.
• Spring '03:
  • 18.997: Graduate course on polytopes.
  • Recitation for 18.02.
• Spring '02:
  • 18.410J/6.046J Introduction to Algorithms
  • Recitations in 18.06 Linear Algebra.
• Fall '01: 18.415J/6.854J Advanced Algorithms. See the archive on the OCW site. Old webpage.

• Nick Harvey
• Jose Soto

Former Ph.D. students and Postdocs:

• David P. Williamson (Professor, Cornell University)
• V.S. Ramakrishnan (Chief Scientist, ProfitLogic)
• Jon Kleinberg (Associate Professor, Cornell University)
• Matthew Andrews (Bell Labs)
• András Benczúr (Hungarian Academy of Sciences)
• José R. Correa (Assistant Professor, Universidad Adolfo Ibanez)
• Mohammad Mahdian (Yahoo Research)
• Michael Rosenblum (UC Berkeley)
• Jan Vondrák (Princeton U.)
• Brian Dean (Assistant Professor, Clemson University)
• Vahab S. Mirrokni (Microsoft Research)
• Fumei Lam (Brown U.).
• Kevin Cheung (Carleton U.)
• Gautier Stauffer (IBM).

By topic: Semidefinite Programming -- Scheduling -- Primal-Dual Approximation Algorithms

• M.X. Goemans, Minimum Bounded-Degree Spanning Trees, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, 273--282.

• M.X. Goemans and J. Vondrak, Stochastic Covering and Adaptivity, Proceedings of LATIN 2006, 2006, 532--543. Link

• L. Fleischer, M.X. Goemans, V.S. Mirrokni and M. Sviridenko, Tight Approximation Algorithms for Maximum General Assignment Problems,, Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, Miami, Florida, 2006, pp 611--620.

• M.X. Goemans, V.S. Mirrokni and A. Vetta, Sink Equilibria and Convergence, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, 2005, pp. 142--154.

• H.N. Gabow, M.X. Goemans, E. Tardos and D.P Williamson, Approximating the Smallest k-edge Connected Spanning Subgraph by LP Rounding, Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, Vancouver, British Columbia, 2005, pp. 562-571.

• B. Dean, M.X. Goemans and J. Vondrak, Adaptivity and Approximation for Stochastic Packing Problems, Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, Vancouver, British Columbia, 2005, pp. 395--404.

• B. Dean, M.X. Goemans and J. Vondrak, Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, 2004, pp. 208--217. Journal version (with many improvements) being submitted to Mathematics of Operations Research.

• M. Charikar, M.X. Goemans and H. Karloff, On the Integrality Ratio for the Asymmetric Traveling Salesman Problem, Mathematics of Operations Research, 31, pp. 245--252, 2006.

• J. Correa and M.X. Goemans, Improved Bounds on Nonblocking 3-Stage Clos Networks, SIAM J. Comput, 37, pp. 870--894, 2007. Preliminary version as: J. Correa and M.X. Goemans, An Approximate Konig's Theorem for Edge Coloring Weighted Bipartite Graphs, 36th ACM Symposium on Theory of Computing, Chicago, IL, 2004, pp. 398--406.

• M.X. Goemans and J. Vondrak, Covering Minimum Spanning Trees of Random Subgraphs, 15th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, 2004, pp. 927--934. (Improved) journal version in Random Structures and Algorithms, Vol. 29, pp. 257--276, 2006.

• M.X. Goemans, L. Li, V.S. Mirrokni and M. Thottan, Market Sharing Games Applied to Content Distribution in Ad-Hoc Networks, Fifth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), Tokyo, Japan, 2004, pp. 55--66. Journal version (with same title) in IEEE Journal on Selected Areas in Communication, Vol. 24, pp. 1020--1033, 2006.

• J.-F. Macq and M.X. Goemans, Trade-offs on the Location of the Core Node in a Network, Networks, 44, 2004, pp. 179--186. Reprint. Preliminary version in the Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, 2004, pp. 590--597.

• M. Rosenblum, M.X. Goemans and V. Tarokh, Universal Bounds on Buffer Size for Packetizing Fluid Policies in Input Queued, Crossbar Switches, INFOCOM 2004, pp. 1127--1135.

• M. Rosenblum, R. Yim, M.X. Goemans, and V. Tarokh, Worst-Case Delay Bounds for Packetizing Time-Varying Fluid Schedules for a Single Server in a Packet-Switched Network, Proceedings of the 38th Annual Conference on Information Sciences and Systems (CISS), Princeton, NJ, 1553-1559, 2004.

• C. Caramanis, M. Rosenblum, M.X. Goemans, and V. Tarokh, Scheduling Algorithms for Providing Flexible, Rate-Based, Quality of Service Guarantees for Packet-Switching in Banyan Networks, Proceedings of the 38th Annual Conference on Information Sciences and Systems (CISS), Princeton, NJ, 160-166, 2004.

• B. Dean and M.X. Goemans, Improved Approximation Algorithms for Minimum Space Advertisement Scheduling, ICALP 2003, LNCS 2719, pp 1138--1152. Journal version submitted.

• T. Chow, C.K. Fan, M.X. Goemans and J. Vondrak, Wide Partitions, Latin Tableaux, and Rota's Basis Conjecture, Advances in Applied Mathematics, 31, 334--358, 2003. Reprint.

• M.X. Goemans, M. Queyranne, A.S. Schulz, M. Skutella and Y. Wang, Single Machine Scheduling with Release Dates, SIAM Journal on Discrete Mathematics, 15, 165--192, 2002. Reprint.

• M.X. Goemans and D.P. Williamson, Approximation Algorithms for MAX-3-CUT and Other Problems Via Complex Semidefinite Programming, Journal of Computer and System Sciences (Special Issue for STOC 2001), 68, 442--470, 2004. Preliminary version in Proceedings of 33rd STOC, Crete, 443--452, 2001.

• M.X. Goemans and L. Tuncel, When does the positive semidefiniteness constraint help in lifting procedures, Mathematics of Operations Research, 26, 796-815, 2001.

• Edited Book. M.X. Goemans, K. Jansen, J.D.P. Rolim, L. Trevisan (Eds.), Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and the 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Berkeley, CA, USA, August 18-20, 2001, Lecture Notes in Computer Science, LNCS 2129, 2001.

• M.X. Goemans, Approximate Edge Splitting, SIAM Journal on Discrete Mathematics, 14, 138--141, 2001. Reprint.

• M.X. Goemans and M. Skutella, Cooperative Facility Location Games, Journal of Algorithms, 50, 194--214, 2004. Preliminary version in the proceedings of SODA 2000, 76--85.

• M.X. Goemans and D.P. Williamson, Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler, SIAM Journal on Discrete Mathematics, 13, 281--294, 2000. Reprint.

• M.X. Goemans, J.M. Wein and D.P. Williamson, A 1.47-Approximation Algorithm for a Preemptive Single-Machine Scheduling Problem, Operations Research Letters, 26, 149--154, 2000. Reprint.

• M.X. Goemans and F. Rendl, Combinatorial Optimization, in Handbook of Semidefinite Programming: Theory, Algorithms and Applications, H. Wolkowicz, R. Saigal and L. Vandenberghe, Eds., 2000.

• Y. Dinitz, N. Garg, and M.X. Goemans, On the Single-Source Unsplittable Flow Problem, Combinatorica, 19, 17--41, 1999.

• M.X. Goemans and F. Rendl, Semidefinite Programs and Association Schemes, Computing, 63, 331--340, 1999.

• Survey. M.X. Goemans, Semidefinite Programming and Combinatorial Optimization, Documenta Mathematica, Extra Volume ICM 1998, Vol III, 657--666, 1998.

• J. Kleinberg and M.X. Goemans, The Lovasz Theta Function and a Semidefinite Programming Relaxation of Vertex Cover, SIAM Journal on Discrete Mathematics, 11, 196--204, 1998. Reprint.

• F.A. Chudak, M.X. Goemans, D.S. Hochbaum and D.P. Williamson, A primal--dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs, Operations Research Letters, 22, 111--118, 1998. Reprint.

• H.N. Gabow, M.X. Goemans and D.P. Williamson, An Efficient Approximation Algorithm for the Survivable Network Design Problem, Mathematical Programming, 82, 13--40, 1998.

• M.X. Goemans and J. Kleinberg, An Improved Approximation Ratio for the Minimum Latency Problem, Mathematical Programming, 82, 111--124, 1998. Reprint.

• M. Andrews, M.X. Goemans and Y.L. Zhang, Improved Bounds for On-Line Load Balancing, Algorithmica, 23, 278--301, 1998.

• M.X. Goemans, D. Karger and J. Kleinberg, Randomized Algorithms, in: Annotated Bibliographies in Combinatorial Optimization , M. Dell'Amico, F. Maffioli, S. Martello, Eds., 143--162, 1997.

• M.X. Goemans and D.P. Williamson, Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs, Combinatorica, 17, 1--23, 1997.

• Survey. M.X. Goemans and D.P. Williamson, The Primal-Dual Method for Approximation Algorithms and its Application to Network Design Problems, in Approximation Algorithms, D. Hochbaum, Ed., 1997.

• Survey. M.X. Goemans, Semidefinite Programming in Combinatorial Optimization, Mathematical Programming, 79, 143--161, 1997.

• M.X. Goemans, Improved Approximation Algorithms for Scheduling with Release Dates, Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 591--598, 1997.

• M.X. Goemans, A Supermodular Relaxation for Scheduling with Release Dates, Fifth Integer Programming and Combinatorial Optimization Conference, LNCS 1084, Vancouver, Canada, 288--300, 1996.

• M.X. Goemans and R. Ravi, The Constrained Minimum Spanning Tree Problem, Fifth Scandinavian Workshop on Algorithm Theory, LNCS 1097, Reykjavik, Iceland, 66-75, 1996.

• M.X. Goemans and L.A. Hall, The Strongest Facets of the Acyclic Subgraph Polytope are Unknown, Fifth Integer Programming and Combinatorial Optimization Conference, LNCS 1084, Vancouver, Canada, 415--429, 1996.

• M.X. Goemans, Worst-case Comparison of Valid Inequalities for the TSP, Mathematical Programming, 69, 335--349, 1995.

• M.X. Goemans and V.S. Ramakrishnan, Minimizing Submodular Functions over Families of Sets, Combinatorica, 15, 499--513, 1995.

• M.X. Goemans, An Approximation Algorithm for Scheduling on Three Dedicated Machines, Discrete Applied Mathematics, 61, 49--59, 1995.

• U. Feige and M.X. Goemans, Approximating 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, Tel Aviv, Israel, 182--189, 1995.

• The MAXCUT paper. M.X. Goemans and D.P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, J. ACM, 42, 1115--1145, 1995. A preliminary version appeared in the Proceedings of the 26th Symposium on the Theory of Computing, Montreal, Canada, 422--431, 1994. Prepint in pdf. This paper received the Fulkerson Prize (see also here) awarded jointly between the American Mathematical Society and the Mathematical Programming Society, and also the SIAM Activity group on Optimization Prize (in May 1999) awarded by the Society for Industrial and Applied Mathematics. Some citations at Google Scholar or at citeseer.

• D. Williamson, M.X. Goemans, M. Mihail and V. Vazirani, A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems, Combinatorica, 15, 435--454, 1995.

• M.X. Goemans and D.P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, 24, 296--317, 1995.

• M.X. Goemans and D.P. Williamson, Approximating minimum-cost graph problems with spanning tree edges, Operations Research Letters, 16, 183--244, 1994. Abstract.

• D.P. Williamson and M.X. Goemans, Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances, ORSA J. Computing, 8, 29--40, 1996. A preliminary version appeared in the Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, VA, 355--364, 1994.

• M.X. Goemans, A. Goldberg, S. Plotkin, D. Shmoys, E. Tardos and D. Williamson, Improved Approximation Algorithms for Network Design Problems, Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, VA, 223--232, 1994.

• M.X. Goemans and D.P. Williamson, New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem, SIAM Journal on Discrete Mathematics, 7, 656--666, 1994.

• M.X. Goemans, Arborescence Polytopes for Series-Parallel Graphs, Discrete Applied Mathematics, 51, 277--289, 1994.

• Z. Furedi, M.X. Goemans and D.J. Kleitman, On the Maximum Number of Triangles in Wheel-Free Graphs, Combinatorics, Probability & Computing, 3, 63-75, 1994.

• M.X. Goemans, The Steiner Tree Polytope and Related Polyhedra, Mathematical Programming, 63, 157--182, 1994.

• M.X. Goemans and D. Bertsimas, Survivable Networks, Linear Programming Relaxations and the Parsimonious Property, Mathematical Programming, 60, 145--166, 1993.

• D. Bienstock, M.X. Goemans, D. Simchi-Levi and D. Williamson, A Note on the Prize Collecting Traveling Salesman Problem, Mathematical Programming, 59, 413--420, 1993.

• M.X. Goemans, A Generalization of Petersen's Theorem, Discrete Mathematics, 115, 277--282, 1993.

• M.X. Goemans and M. Kodialam, A Lower Bound on the Expected Value of an Optimal Assignment, Mathematics of Operations Research, 18, 267--274, 1993.

• M.X. Goemans and Y.-S. Myung, A Catalog of Steiner Tree Formulations, Networks, 23, 19--28, 1993.

• M.X. Goemans and K.T. Talluri, 2-Change for k-connected networks, Operations Research Letters, 10, 113--117, 1991. Abstract.

• M.X. Goemans and D. Bertsimas, Probabilistic Analysis of the Held-Karp Lower Bound for the Euclidean Traveling Salesman Problem, Mathematics of Operations Research, 16, 72--89, 1991.

• M.X. Goemans, Valid Inequalities and Separation for Mixed Integer Constraints with Variable Upper Bounds, Operations Research Letters, 8, 315--322, 1989.

Course notes:

Most of my old course notes (on linear programming, approximation algorithms, network flows, etc.) from Advanced Algorithms (18.415J/6.854J) are available here at the OCW site. The notes are based on scribed notes by students. Additional notes, not given there, cover online algorithms, randomized algorithms, and Karp's partitioning scheme.