Publications
Most of my research has been supported in part by NSF, through contracts CCF0829878, CCF0515221, 0098018CCR, 0121495ITR, 9623859CCR and 9302476CCR, and currently through contract CCF1115849 and also by the ONR under contract N000140510148. 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 ACMSIAm Symposium on Discrete Algorithms, 2010. (Best paper award.) pdf.
 M.X. Goemans, S. Iwata and R. Zenklusen, An Algorithmic Framework for Wireless Information Flow, FortySeventh 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 PrizeCollecing 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 ACMSIAM Symposium on Discrete Algorithms,
2009. pdf

H.N. Gabow, M.X. Goemans, E. Tardos and D.P Williamson, Approximating
the Smallest kedge Connected Spanning Subgraph by LP
Rounding, Networks, 2009. pdf.
Preliminary version in: Proceedings of the 16th ACMSIAM Symposium on Discrete Algorithms, Vancouver, British Columbia, 2005, pp. 562571.
 A.A. Benczur and M.X. Goemans, Deformable Polygon
Representation and NearMincuts, in: Building Bridges: Between
Mathematics and Computer Science, M. Groetschel and G.O.H. Katona,
Eds., Bolyai Society Mathematical Studies 19, 2008, 103135. pdf (with
incorrect page numbers).
 M.X. Goemans, Minimum
BoundedDegree Spanning Trees, Proceedings of the 47th
Annual IEEE Symposium on Foundations of Computer Science, 2006, 273282. pdf
 M.X. Goemans and J. Vondrak, Stochastic Covering and
Adaptivity, Proceedings of LATIN 2006, 2006, 532543.
pdf.
 L. Fleischer, M.X. Goemans, V.S. Mirrokni and M. Sviridenko,
Tight
Approximation Algorithms for Maximum General Assignment
Problems,, Proceedings of the 17th ACMSIAM Symposium on
Discrete Algorithms, Miami, Florida, 2006, pp 611620. 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. 142154. pdf.

B. Dean, M.X. Goemans and J. Vondrak, Adaptivity and
Approximation for Stochastic Packing Problems, Proceedings of
the 16th ACMSIAM Symposium on Discrete Algorithms, Vancouver, British
Columbia, 2005, pp. 395404.

B. Dean, M.X. Goemans and J. Vondrak, Approximating the
Stochastic Knapsack Problem: The Benefit of Adaptivity,
Mathematics of Operations Research, 33, pp. 945964, 2008. pdf.
Preliminary version in: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, 2004, pp. 208217.

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

J. Correa and M.X. Goemans, Improved
Bounds on Nonblocking 3Stage Clos Networks, SIAM
J. Comput, 37, pp. 870894, 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. 398406.
 M.X. Goemans and J. Vondrak, Covering Minimum Spanning
Trees of Random Subgraphs, Random Structures and Algorithms,
Vol. 29, pp. 257276, 2006. pdf.
Preliminary version in the Proceedings of the 15th ACMSIAM Symposium on Discrete Algorithms, New Orleans, LA, 2004, pp. 927934.
 M.X. Goemans, L. Li, V.S. Mirrokni and M. Thottan, Market
Sharing Games Applied to Content Distribution in AdHoc
Networks, Fifth ACM International Symposium on Mobile Ad Hoc
Networking and Computing (MOBIHOC), Tokyo, Japan, 2004,
pp. 5566. Journal version (with same title) in IEEE Journal on
Selected Areas in Communication, Vol. 24, pp. 10201033, 2006.
 J.F. Macq and M.X. Goemans, Tradeoffs on the Location of the
Core Node in a Network, Networks, 44, 2004,
pp. 179186. pdf.
Preliminary version in the Proceedings of the 15th ACMSIAM Symposium on Discrete Algorithms, New Orleans, LA, 2004, pp. 590597.
 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. 11271135.
 M. Rosenblum, R. Yim, M.X. Goemans, and V. Tarokh, WorstCase Delay
Bounds for Packetizing TimeVarying Fluid Schedules for a Single
Server in a PacketSwitched Network, Proceedings of the
38th Annual Conference on Information Sciences and Systems (CISS), Princeton,
NJ, 15531559, 2004.
 C. Caramanis, M. Rosenblum, M.X. Goemans, and V. Tarokh, Scheduling
Algorithms for Providing Flexible, RateBased, Quality of Service
Guarantees for PacketSwitching in Banyan Networks, Proceedings of the
38th Annual Conference on Information Sciences and Systems (CISS), Princeton,
NJ, 160166, 2004.

B. Dean and M.X. Goemans, Improved Approximation Algorithms for
Minimum Space Advertisement Scheduling, ICALP 2003, LNCS 2719, pp
11381152.
 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, 334358, 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, 165192, 2002. pdf.
 M.X. Goemans and D.P. Williamson,
Approximation Algorithms for MAX3CUT and Other Problems Via
Complex Semidefinite Programming, Journal of Computer and
System Sciences (Special Issue for STOC 2001), 68, 442470, 2004.
Preliminary version in Proceedings of 33rd STOC, Crete, 443452, 2001.
 M.X. Goemans and L. Tuncel, When does the
positive semidefiniteness constraint help in lifting
procedures, Mathematics of Operations Research, 26,
796815, 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 1820, 2001, Lecture Notes in Computer
Science, LNCS 2129, 2001.
 M.X. Goemans, Approximate Edge
Splitting, SIAM Journal on Discrete
Mathematics, 14, 138141, 2001. pdf.
 M.X. Goemans and M. Skutella, Cooperative
Facility Location Games, Journal of Algorithms, 50,
194214, 2004. Preliminary version in the proceedings of SODA 2000,
7685.
 M.X. Goemans and D.P. Williamson, TwoDimensional
Gantt Charts and a Scheduling Algorithm of Lawler,
SIAM Journal on Discrete Mathematics, 13, 281294, 2000.
pdf.
 M.X. Goemans, J.M. Wein and D.P. Williamson, A
1.47Approximation Algorithm for a Preemptive SingleMachine
Scheduling Problem, Operations Research Letters, 26, 149154,
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
SingleSource Unsplittable Flow Problem, Combinatorica,
19, 1741, 1999.
 M.X. Goemans and F. Rendl, Semidefinite
Programs and Association Schemes, Computing, 63, 331340,
1999.
 Survey. M.X. Goemans, Semidefinite
Programming and Combinatorial Optimization,
Documenta Mathematica, Extra Volume ICM 1998, Vol III, 657666, 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, 196204, 1998. pdf.

F.A. Chudak, M.X. Goemans, D.S. Hochbaum and D.P. Williamson, A
primaldual interpretation of two 2approximation algorithms for the
feedback vertex set problem in undirected graphs, Operations
Research Letters, 22, 111118, 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, 1340, 1998.
pdf.
 M.X. Goemans and J. Kleinberg, An Improved Approximation
Ratio for the Minimum Latency Problem, Mathematical
Programming, 82, 111124, 1998.
pdf.
 M. Andrews, M.X. Goemans and Y.L. Zhang, Improved Bounds
for OnLine Load Balancing, Algorithmica, 23, 278301, 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.,
143162, 1997.
 M.X. Goemans and D.P. Williamson, PrimalDual Approximation Algorithms for Feedback Problems in Planar Graphs, Combinatorica, 17, 123, 1997. pdf.
 Survey. M.X. Goemans and D.P. Williamson, The
PrimalDual 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, 143161, 1997. doi
 M.X. Goemans, Improved Approximation Algorithms for Scheduling with
Release Dates, Eighth Annual ACMSIAM Symposium
on Discrete Algorithms, New Orleans, 591598, 1997.
 M.X. Goemans, A Supermodular Relaxation for Scheduling with
Release Dates, Fifth Integer Programming and Combinatorial
Optimization Conference, LNCS 1084, Vancouver,
Canada, 288300, 1996. pdf.

M.X. Goemans and R. Ravi, The Constrained Minimum Spanning Tree
Problem, Fifth Scandinavian Workshop on Algorithm Theory, LNCS
1097, Reykjavik, Iceland, 6675, 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, 415429, 1996. pdf.
 M.X. Goemans, Worstcase
Comparison of Valid Inequalities for the TSP, Mathematical
Programming, 69, 335349, 1995. pdf.
 M.X. Goemans and V.S. Ramakrishnan, Minimizing
Submodular Functions over Families of Sets, Combinatorica,
15, 499513, 1995.
 M.X. Goemans, An Approximation Algorithm for Scheduling on
Three Dedicated Machines, Discrete
Applied Mathematics, 61, 4959, 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, 182189, 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, 11151145, 1995.
A preliminary version appeared in the Proceedings of the 26th Symposium on the Theory of Computing, Montreal, Canada, 422431, 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
PrimalDual Approximation Algorithm for Generalized Steiner Network
Problems, Combinatorica, 15, 435454, 1995.
 M.X. Goemans and D.P. Williamson, A
General Approximation Technique for Constrained Forest
Problems, SIAM Journal on Computing, 24,
296317, 1995. pdf.
 M.X. Goemans and D.P. Williamson, Approximating minimumcost
graph problems with spanning tree edges, Operations Research
Letters, 16, 183244, 1994.
 D.P. Williamson and M.X. Goemans, Computational Experience
with an Approximation Algorithm on LargeScale Euclidean Matching
Instances, ORSA J. Computing, 8, 2940, 1996. A preliminary
version appeared in the Proceedings of the Fifth Annual ACMSIAM
Symposium on Discrete Algorithms, Arlington, VA, 355364, 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 ACMSIAM Symposium on Discrete
Algorithms, Arlington, VA, 223232, 1994.
 M.X. Goemans and D.P. Williamson, New 3/4Approximation
Algorithms for the Maximum Satisfiability Problem, SIAM Journal
on Discrete Mathematics, 7, 656666, 1994. pdf.
 M.X. Goemans, Arborescence Polytopes for SeriesParallel
Graphs, Discrete
Applied Mathematics, 51, 277289, 1994.
 Z. Furedi, M.X. Goemans and D.J. Kleitman, On the Maximum Number of Triangles in
WheelFree Graphs, Combinatorics, Probability & Computing,
3, 6375, 1994.
 M.X. Goemans, The Steiner Tree Polytope and Related
Polyhedra, Mathematical Programming, 63, 157182, 1994. pdf.
 M.X. Goemans and D. Bertsimas, Survivable Networks, Linear
Programming Relaxations and the Parsimonious Property,
Mathematical Programming, 60, 145166, 1993.
 D. Bienstock, M.X. Goemans, D. SimchiLevi and D. Williamson, A Note on the Prize Collecting Traveling Salesman Problem,
Mathematical Programming, 59, 413420, 1993. pdf.
 M.X. Goemans, A Generalization of Petersen's
Theorem, Discrete Mathematics, 115, 277282, 1993.
 M.X. Goemans and M. Kodialam, A Lower Bound on the Expected Value of an Optimal Assignment, Mathematics of
Operations Research, 18, 267274, 1993.
 M.X. Goemans and Y.S. Myung, A Catalog of Steiner Tree
Formulations, Networks, 23, 1928, 1993. pdf.
 M.X. Goemans and K.T. Talluri, 2Change for kconnected
networks, Operations Research Letters, 10, 113117, 1991.
 M.X. Goemans and D. Bertsimas, Probabilistic Analysis of
the HeldKarp Lower Bound for the Euclidean Traveling Salesman
Problem, Mathematics of Operations Research, 16, 7289,
1991.
 M.X. Goemans, Valid Inequalities and Separation for Mixed
Integer Constraints with Variable Upper Bounds, Operations
Research Letters, 8, 315322, 1989.
site info
© 2009 Michel Goemans  Original design by Andreas Viklund