| * | 2009 |
|---|
| 80 | EE | Michel X. Goemans,
Nicholas J. A. Harvey,
Satoru Iwata,
Vahab S. Mirrokni:
Approximating submodular functions everywhere.
SODA 2009: 535-544 |
| 79 | EE | 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) |
| 78 | EE | Michel X. Goemans:
Combining Approximation Algorithms for the Prize-Collecting TSP
CoRR abs/0910.0553: (2009) |
| 77 | EE | 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) |
| 2008 |
|---|
| 76 | EE | 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) |
| 2007 |
|---|
| 75 | EE | José R. Correa,
Michel X. Goemans:
Improved Bounds on Nonblocking 3-Stage Clos Networks.
SIAM J. Comput. 37(3): 870-894 (2007) |
| 2006 |
|---|
| 74 | EE | 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 |
| 73 | EE | Michel X. Goemans:
Minimum Bounded Degree Spanning Trees.
FOCS 2006: 273-282 |
| 72 | EE | Brian C. Dean,
Michel X. Goemans,
Nicole Immorlica:
The Unsplittable Stable Marriage Problem.
IFIP TCS 2006: 65-75 |
| 71 | EE | Michel X. Goemans,
Jan Vondrák:
Stochastic Covering and Adaptivity.
LATIN 2006: 532-543 |
| 70 | EE | Lisa Fleischer,
Michel X. Goemans,
Vahab S. Mirrokni,
Maxim Sviridenko:
Tight approximation algorithms for maximum general assignment problems.
SODA 2006: 611-620 |
| 69 | EE | 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) |
| 68 | EE | 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) |
| 67 | EE | 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) |
| 66 | EE | Michel X. Goemans,
Jan Vondrák:
Covering minimum spanning trees of random subgraphs.
Random Struct. Algorithms 29(3): 257-276 (2006) |
| 2005 |
|---|
| 65 | EE | Michel X. Goemans,
Vahab S. Mirrokni,
Adrian Vetta:
Sink Equilibria and Convergence.
FOCS 2005: 142-154 |
| 64 | EE | Brian C. Dean,
Michel X. Goemans,
Jan Vondrák:
Adaptivity and approximation for stochastic packing problems.
SODA 2005: 395-404 |
| 63 | EE | 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 |
| 2004 |
|---|
| 62 | EE | Moses Charikar,
Michel X. Goemans,
Howard J. Karloff:
On the Integrality Ratio for Asymmetric TSP.
FOCS 2004: 101-107 |
| 61 | EE | Brian C. Dean,
Michel X. Goemans,
Jan Vondrák:
Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity.
FOCS 2004: 208-217 |
| 60 | EE | Michael Rosenblum,
Michel X. Goemans,
Vahid Tarokh:
Universal Bounds on Buffer Size for Packetizing Fluid Policies in Input Queued, Crossbar Switches.
INFOCOM 2004 |
| 59 | EE | 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 |
| 58 | EE | Jean-François Macq,
Michel X. Goemans:
Trade-offs on the location of the core node in a network.
SODA 2004: 597-604 |
| 57 | EE | Michel X. Goemans,
Jan Vondrák:
Covering minimum spanning trees of random subgraphs.
SODA 2004: 934-941 |
| 56 | EE | José R. Correa,
Michel X. Goemans:
An approximate König's theorem for edge-coloring weighted bipartite graphs.
STOC 2004: 398-406 |
| 55 | EE | Michel X. Goemans,
Martin Skutella:
Cooperative facility location games.
J. Algorithms 50(2): 194-214 (2004) |
| 54 | EE | Michel X. Goemans,
David P. Williamson:
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming.
J. Comput. Syst. Sci. 68(2): 442-470 (2004) |
| 53 | EE | 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) |
| 2003 |
|---|
| 52 | EE | Brian C. Dean,
Michel X. Goemans:
Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling.
ICALP 2003: 1138-1152 |
| 2002 |
|---|
| 51 | EE | 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) |
| 2001 |
|---|
| 50 | | Michel X. Goemans,
Klaus Jansen,
José D. P. Rolim,
Luca Trevisan:
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
Springer 2001 |
| 49 | EE | Michel X. Goemans:
Using Complex Semidefinite Programming for Approximating MAX E2-LIN3.
RANDOM-APPROX 2001: 1 |
| 48 | EE | Michel X. Goemans,
David P. Williamson:
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming.
STOC 2001: 443-452 |
| 47 | EE | Michel X. Goemans,
Levent Tunçel:
When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
Math. Oper. Res. 26(4): 796-815 (2001) |
| 46 | EE | Michel X. Goemans:
Approximate Edge Splitting.
SIAM J. Discrete Math. 14(1): 138-141 (2001) |
| 2000 |
|---|
| 45 | EE | Michel X. Goemans,
Martin Skutella:
Cooperative facility location games.
SODA 2000: 76-85 |
| 44 | EE | 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) |
| 43 | EE | 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) |
| 1999 |
|---|
| 42 | EE | Michel X. Goemans,
David P. Williamson:
Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler.
SODA 1999: 366-375 |
| 41 | EE | Matthew Andrews,
Michel X. Goemans,
Lisa Zhang:
Improved Bounds for On-Line Load Balancing.
Algorithmica 23(4): 278-301 (1999) |
| 40 | EE | Yefim Dinitz,
Naveen Garg,
Michel X. Goemans:
On the Single-Source Unsplittable Flow Problem.
Combinatorica 19(1): 17-41 (1999) |
| 39 | EE | Michel X. Goemans,
Franz Rendl:
Semidefinite Programs and Association Schemes.
Computing 63(4): 331-340 (1999) |
| 1998 |
|---|
| 38 | EE | Yefim Dinitz,
Naveen Garg,
Michel X. Goemans:
On the Single-Source Unsplittable Flow Problem.
FOCS 1998: 290-299 |
| 37 | EE | Michel X. Goemans,
David P. Williamson:
Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs.
Combinatorica 18(1): 37-59 (1998) |
| 36 | | Michel X. Goemans,
Jon M. Kleinberg:
An improved approximation ratio for the minimum latency problem.
Math. Program. 82: 111-124 (1998) |
| 35 | | 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) |
| 34 | EE | 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) |
| 33 | EE | 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) |
| 1997 |
|---|
| 32 | | Michel X. Goemans:
Improved Approximation Algorithms for Scheduling with Release Dates.
SODA 1997: 591-598 |
| 31 | | Michel X. Goemans:
Semidefinite programming in combinatorial optimization.
Math. Program. 79: 143-161 (1997) |
| 1996 |
|---|
| 30 | | Matthew Andrews,
Michel X. Goemans,
Lisa Zhang:
Improved Bounds for On-line Load Balancing.
COCOON 1996: 1-10 |
| 29 | EE | Michel X. Goemans,
David P. Williamson:
Primal-Dual Approximation Algorithms for Feedback Problems.
IPCO 1996: 147-161 |
| 28 | EE | Michel X. Goemans:
A Supermodular Relaxation for Scheduling with Release Dates.
IPCO 1996: 288-300 |
| 27 | EE | Michel X. Goemans,
Leslie A. Hall:
The Strongest Facets of the Acyclic Subgraph Polytope Are Unknown.
IPCO 1996: 415-429 |
| 26 | | Michel X. Goemans,
Jon M. Kleinberg:
An Improved Approximation Ratio for the Minimum Latency Problem.
SODA 1996: 152-158 |
| 25 | EE | R. Ravi,
Michel X. Goemans:
The Constrained Minimum Spanning Tree Problem (Extended Abstract).
SWAT 1996: 66-75 |
| 24 | EE | 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) |
| 1995 |
|---|
| 23 | | 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 |
| 22 | | 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) |
| 21 | | Michel X. Goemans,
V. S. Ramakrishnan:
Minimizing Submodular Functions over Families of Sets.
Combinatorica 15(4): 499-513 (1995) |
| 20 | EE | Michel X. Goemans:
An Approximation Algorithm for Scheduling on Three Dedicated Machines.
Discrete Applied Mathematics 61(1): 49-59 (1995) |
| 19 | EE | 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) |
| 18 | | Michel X. Goemans:
Worst-case comparison of valid inequalities for the TSP.
Math. Program. 69: 335-349 (1995) |
| 17 | | Michel X. Goemans,
David P. Williamson:
A General Approximation Technique for Constrained Forest Problems.
SIAM J. Comput. 24(2): 296-317 (1995) |
| 1994 |
|---|
| 16 | | 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 |
| 15 | | David P. Williamson,
Michel X. Goemans:
Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances.
SODA 1994: 355-364 |
| 14 | EE | Michel X. Goemans,
David P. Williamson:
.879-approximation algorithms for MAX CUT and MAX 2SAT.
STOC 1994: 422-431 |
| 13 | | 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) |
| 12 | EE | Michel X. Goemans:
Arborescence Polytopes for Series-parallel Graphs.
Discrete Applied Mathematics 51(3): 277-289 (1994) |
| 11 | | Michel X. Goemans:
The Steiner tree polytope and related polyhedra.
Math. Program. 63: 157-182 (1994) |
| 10 | EE | 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) |
| 1993 |
|---|
| 9 | | Michel X. Goemans,
David P. Williamson:
A new \frac34-approximation algorithm for MAX SAT.
IPCO 1993: 313-321 |
| 8 | | Harold N. Gabow,
Michel X. Goemans,
David P. Williamson:
An efficient approximation algorithm for the survivable network design problem.
IPCO 1993: 57-74 |
| 7 | EE | 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 |
| 6 | EE | Michel X. Goemans:
A generalization of Petersen's theorem.
Discrete Mathematics 115(1-3): 277-282 (1993) |
| 5 | | 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) |
| 4 | | Michel X. Goemans,
Dimitris Bertsimas:
Survivable networks, linear programming relaxations and the parsimonious property.
Math. Program. 60: 145-166 (1993) |
| 1992 |
|---|
| 3 | | Michel X. Goemans:
Polyhedral Description of Trees and Arborescences.
IPCO 1992: 1-14 |
| 2 | EE | Michel X. Goemans,
David P. Williamson:
A General Approximation Technique for Constrained Forest Problems.
SODA 1992: 307-316 |
| 1990 |
|---|
| 1 | | Michel X. Goemans,
Dimitris Bertsimas:
On the Parsimonious Property of Connectivity Problems.
SODA 1990: 388-396 |
