Michel Goemans

Publications

Most of my research has been supported in part by NSF, through contracts CCF-0829878, CCF-0515221, 0098018-CCR, 0121495-ITR, 9623859-CCR and 9302476-CCR, and currently through contract CCF-1115849 and also by the ONR under contract N00014-05-1-0148. Any opinions, findings, and conclusions or recommendations expressed in these papers are those of the author(s) and do not necessarily reflect the views of the National Science Foundation or the Office of Naval Research.

This is a partial list and links are missing. Send me email if you'd like a paper that you cannot find.

• M.X. Goemans, N. Olver, T. Rothvoß, R., Zenklusen, Matroids and integrality gaps for hypergraphic steiner tree relaxations, STOC '12 Proceedings of the 44th symposium on Theory of Computing, 2012.
• M.X. Goemans, Smallest compact formulation for the permutahedron, 2009. pdf.
• A. Asadpour, M.X. Goemans, A. Madry, S. Oveis Gharan and A. Saberi, An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem, 21st ACM-SIAm Symposium on Discrete Algorithms, 2010. (Best paper award.) pdf.
• M.X. Goemans, S. Iwata and R. Zenklusen, An Algorithmic Framework for Wireless Information Flow, Forty-Seventh Annual Allerton Conference on Communication, Control, and Computing, 2009. pdf. Journal version (with different results) entitled A flow model based on polylinking system is to appear in Mathematical Programming. pdf
• M.X. Goemans, Combining Approximation Algorithms for the Prize-Collecing TSP, 2009, arXiv:0910.0553v1.
• M.X. Goemans, N.J.A. Harvey, S. Iwata and V. Mirrokni, Approximating Submodular Functions Everywhere, Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms, 2009. pdf

• H.N. Gabow, M.X. Goemans, E. Tardos and D.P Williamson, Approximating the Smallest k-edge Connected Spanning Subgraph by LP Rounding, Networks, 2009. pdf.

  Preliminary version in: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, Vancouver, British Columbia, 2005, pp. 562-571.

• A.A. Benczur and M.X. Goemans, Deformable Polygon Representation and Near-Mincuts, in: Building Bridges: Between Mathematics and Computer Science, M. Groetschel and G.O.H. Katona, Eds., Bolyai Society Mathematical Studies 19, 2008, 103--135. pdf (with incorrect page numbers).

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

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

• 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. pdf.

• 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. pdf.

• 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, Mathematics of Operations Research, 33, pp. 945-964, 2008. pdf.

  Preliminary version in: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, 2004, pp. 208--217.

• 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. pdf.

• J. Correa and M.X. Goemans, Improved Bounds on Nonblocking 3-Stage Clos Networks, SIAM J. Comput, 37, pp. 870--894, 2007. pdf.

  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, Random Structures and Algorithms, Vol. 29, pp. 257--276, 2006. pdf.

  Preliminary version in the Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, 2004, pp. 927--934.

• 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. pdf.

  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.

• 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. pdf

• 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. pdf.

• 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. pdf.

• 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. pdf.

• 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. pdf.

• 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. pdf.

• 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. pdf.

• 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. pdf.

• 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. pdf.

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

• 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. pdf.

• 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. pdf

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

• 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. pdf.

• 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. pdf.

• 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. pdf.

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

• 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. pdf.

• MAXCUT.
  Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), 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. 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.

• 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. pdf.

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

• 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. pdf.

• 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. pdf.

• 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. pdf.

• 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. pdf.

• 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. pdf.

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

• 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.

site info

© 2009 Michel Goemans | Original design by Andreas Viklund