Michel X. Goemans

	2012
85		Michel X. Goemans, Neil Olver, Thomas Rothvoß, Rico Zenklusen: Matroids and integrality gaps for hypergraphic steiner tree relaxations. STOC 2012: 1161-1176
	2011
84		Michel X. Goemans, Neil Olver, Thomas Rothvoß, Rico Zenklusen: Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations CoRR abs/1111.7280: (2011)
	2010
83		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
82		Michel X. Goemans, José A. Soto: Symmetric Submodular Function Minimization Under Hereditary Family Constraints CoRR abs/1007.2140: (2010)
	2009
81		Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, Vahab S. Mirrokni: Approximating submodular functions everywhere. SODA 2009: 535-544
80		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)
79		Michel X. Goemans: Combining Approximation Algorithms for the Prize-Collecting TSP CoRR abs/0910.0553: (2009)
78		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
77		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
76		José R. Correa, Michel X. Goemans: Improved Bounds on Nonblocking 3-Stage Clos Networks. SIAM J. Comput. 37(3): 870-894 (2007)
	2006
75		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
74		Michel X. Goemans: Minimum Bounded Degree Spanning Trees. FOCS 2006: 273-282
73		Brian C. Dean, Michel X. Goemans, Nicole Immorlica: The Unsplittable Stable Marriage Problem. IFIP TCS 2006: 65-75
72		Michel X. Goemans, Jan Vondrák: Stochastic Covering and Adaptivity. LATIN 2006: 532-543
71		Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko: Tight approximation algorithms for maximum general assignment problems. SODA 2006: 611-620
70		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)
69		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)
68		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)
67		Michel X. Goemans, Jan Vondrák: Covering minimum spanning trees of random subgraphs. Random Struct. Algorithms 29(3): 257-276 (2006)
	2005
66		Michel X. Goemans, Vahab S. Mirrokni, Adrian Vetta: Sink Equilibria and Convergence. FOCS 2005: 142-154
65		Brian C. Dean, Michel X. Goemans, Jan Vondrák: Adaptivity and approximation for stochastic packing problems. SODA 2005: 395-404
64		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
63		Moses Charikar, Michel X. Goemans, Howard J. Karloff: On the Integrality Ratio for Asymmetric TSP. FOCS 2004: 101-107
62		Brian C. Dean, Michel X. Goemans, Jan Vondrák: Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity. FOCS 2004: 208-217
61		Michael Rosenblum, Michel X. Goemans, Vahid Tarokh: Universal Bounds on Buffer Size for Packetizing Fluid Policies in Input Queued, Crossbar Switches. INFOCOM 2004
60		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
59		Jean-François Macq, Michel X. Goemans: Trade-offs on the location of the core node in a network. SODA 2004: 597-604
58		Michel X. Goemans, Jan Vondrák: Covering minimum spanning trees of random subgraphs. SODA 2004: 934-941
57		José R. Correa, Michel X. Goemans: An approximate König's theorem for edge-coloring weighted bipartite graphs. STOC 2004: 398-406
56		Michel X. Goemans, Martin Skutella: Cooperative facility location games. J. Algorithms 50(2): 194-214 (2004)
55		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)
54		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
53		Lawrence L. Larmore, Michel X. Goemans: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA ACM 2003
52		Brian C. Dean, Michel X. Goemans: Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling. ICALP 2003: 1138-1152
	2002
51		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		Michel X. Goemans: Using Complex Semidefinite Programming for Approximating MAX E2-LIN3. RANDOM-APPROX 2001: 1
48		Michel X. Goemans, David P. Williamson: Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. STOC 2001: 443-452
47		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		Michel X. Goemans: Approximate Edge Splitting. SIAM J. Discrete Math. 14(1): 138-141 (2001)
	2000
45		Michel X. Goemans, Martin Skutella: Cooperative facility location games. SODA 2000: 76-85
44		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		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		Michel X. Goemans, David P. Williamson: Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. SODA 1999: 366-375
41		Matthew Andrews, Michel X. Goemans, Lisa Zhang: Improved Bounds for On-Line Load Balancing. Algorithmica 23(4): 278-301 (1999)
40		Yefim Dinitz, Naveen Garg, Michel X. Goemans: On the Single-Source Unsplittable Flow Problem. Combinatorica 19(1): 17-41 (1999)
39		Michel X. Goemans, Franz Rendl: Semidefinite Programs and Association Schemes. Computing 63(4): 331-340 (1999)
	1998
38		Yefim Dinitz, Naveen Garg, Michel X. Goemans: On the Single-Source Unsplittable Flow Problem. FOCS 1998: 290-299
37		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		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		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		Michel X. Goemans, David P. Williamson: Primal-Dual Approximation Algorithms for Feedback Problems. IPCO 1996: 147-161
28		Michel X. Goemans: A Supermodular Relaxation for Scheduling with Release Dates. IPCO 1996: 288-300
27		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		R. Ravi, Michel X. Goemans: The Constrained Minimum Spanning Tree Problem (Extended Abstract). SWAT 1996: 66-75
24		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		Michel X. Goemans: An Approximation Algorithm for Scheduling on Three Dedicated Machines. Discrete Applied Mathematics 61(1): 49-59 (1995)
19		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		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		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		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		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		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		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

Coauthor Index

1	Matthew Andrews	[30] [41]
2	Arash Asadpour	[83]
3	Dimitris Bertsimas	[1] [4]
4	Daniel Bienstock	[5]
5	Constantine Caramanis	[69]
6	Moses Charikar	[63] [68]
7	Fabián A. Chudak	[34]
8	José R. Correa	[57] [76]
9	Brian C. Dean	[52] [62] [65] [73] [75] [77]
10	Yefim Dinitz	[38] [40]
11	Uriel Feige	[23]
12	Lisa Fleischer	[71]
13	Zoltán Füredi	[13]
14	Harold N. Gabow	[8] [35] [64] [78]
15	Naveen Garg	[38] [40]
16	Shayan Oveis Gharan	[83]
17	Andrew V. Goldberg	[16]
18	Leslie A. Hall	[27]
19	Nicholas J. A. Harvey	[80] [81]
20	Dorit S. Hochbaum	[34]
21	Nicole Immorlica	[73] [75]
22	Satoru Iwata	[81]
23	Kamal Jain	[80]
24	Klaus Jansen	[50]
25	Howard J. Karloff	[63] [68]
26	Jon M. Kleinberg	[26] [33] [36]
27	Daniel J. Kleitman	[13]
28	Lawrence L. Larmore	[53]
29	Erran L. Li (Li Li, Li (Erran) Li, Li Erran Li)	[60]
30	Li Li	[70]
31	Jean-François Macq	[54] [59]
32	Aleksander Madry	[83]
33	Milena Mihail	[7] [22]
34	Vahab S. Mirrokni (Seyed Vahab Mirrokni)	[60] [66] [70] [71] [81]
35	Neil Olver	[84] [85]
36	Serge A. Plotkin	[16]
37	Maurice Queyranne	[51]
38	V. S. Ramakrishnan	[21]
39	R. Ravi	[25]
40	Franz Rendl	[39]
41	José D. P. Rolim	[50]
42	Michael Rosenblum	[61] [69]
43	Thomas Rothvoß	[84] [85]
44	Amin Saberi	[83]
45	Andreas S. Schulz	[51]
46	David B. Shmoys	[16]
47	David Simchi-Levi	[5]
48	Mohit Singh	[80]
49	Martin Skutella	[45] [51] [56]
50	José A. Soto	[82]
51	Maxim Sviridenko	[71]
52	Éva Tardos	[16] [64] [78]
53	Vahid Tarokh	[61] [69]
54	Marina Thottan	[60] [70]
55	Luca Trevisan	[50]
56	Levent Tunçel	[47]
57	Vijay V. Vazirani	[7] [22]
58	Adrian Vetta	[66]
59	Jan Vondrák	[58] [62] [65] [67] [72] [77]
60	Yaoguang Wang	[51]
61	Joel Wein	[44]
62	David P. Williamson	[2] [5] [7] [8] [9] [10] [14] [15] [16] [17] [19] [22] [24] [29] [34] [35] [37] [42] [43] [44] [48] [55] [64] [78]
63	Rico Zenklusen	[84] [85]
64	Lisa Zhang	[30] [41]

Colors in the list of coauthors

Last update Wed May 30 22:34:44 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page