Claire Mathieu

Claire Kenyon, Claire Kenyon-Mathieu

2009
94		Claire Mathieu: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009 SIAM 2009
2008
93	EE	Glencora Borradaile, Philip N. Klein, Claire Mathieu: A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. FOCS 2008: 115-124
92	EE	Yossi Azar, Benjamin E. Birnbaum, Anna R. Karlin, Claire Mathieu, C. Thach Nguyen: Improved Approximation Algorithms for Budgeted Allocations. ICALP (1) 2008: 186-197
91	EE	Claire Mathieu, Warren Schudy: Yet another algorithm for dense max cut: go greedy. SODA 2008: 176-182
90	EE	Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, Michael E. Saks: Online multicast with egalitarian cost sharing. SPAA 2008: 70-76
89	EE	Jérémy Barbay, Claire Kenyon: Alternation and redundancy analysis of the intersection problem. ACM Transactions on Algorithms 4(1): (2008)
88	EE	Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young: Incremental Medians via Online Bidding. Algorithmica 50(4): 455-478 (2008)
87	EE	Aparna Das, Claire Mathieu: A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing CoRR abs/0812.1595: (2008)
86	EE	Claire Mathieu, Charalampos Papamanthou: Distortion lower bounds for line embeddings. Inf. Process. Lett. 108(4): 175-178 (2008)
85	EE	Benjamin E. Birnbaum, Claire Mathieu: On-line bipartite matching made simple. SIGACT News 39(1): 80-87 (2008)
84	EE	Irit Katriel, Claire Kenyon-Mathieu, Eli Upfal: Commitment under uncertainty: Two-stage stochastic matching problems. Theor. Comput. Sci. 408(2-3): 213-223 (2008)
2007
83	EE	Matthew Cary, Aparna Das, Benjamin Edelman, Ioannis Giotis, Kurtis Heimerl, Anna R. Karlin, Claire Mathieu, Michael Schwarz: Greedy bidding strategies for keyword auctions. ACM Conference on Electronic Commerce 2007: 262-271
82	EE	Irit Katriel, Claire Kenyon-Mathieu, Eli Upfal: Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems. ICALP 2007: 171-182
81	EE	Glencora Borradaile, Claire Kenyon-Mathieu, Philip N. Klein: A polynomial-time approximation scheme for Steiner tree in planar graphs. SODA 2007: 1285-1294
80	EE	Wenceslas Fernandez de la Vega, Claire Kenyon-Mathieu: Linear programming relaxations of maxcut. SODA 2007: 53-61
79	EE	Claire Kenyon-Mathieu, Warren Schudy: How to rank with few errors. STOC 2007: 95-103
78	EE	Glencora Borradaile, Philip N. Klein, Claire Mathieu: Steiner Tree in Planar Graphs: An O ( n log n ) Approximation Scheme with Singly-Exponential Dependence on Epsilon. WADS 2007: 275-286
2006
77	EE	Claire Kenyon, Meinolf Sellmann: Plan B: Uncertainty/Time Trade-Offs for Linear and Integer Programming. CPAIOR 2006: 126-138
76	EE	Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young: Oblivious Medians Via Online Bidding. LATIN 2006: 311-322
75	EE	Aparna Das, Claire Kenyon: On Hierarchical Diameter-Clustering, and the Supplier Problem. WAOA 2006: 132-145
74	EE	Claire Kenyon-Mathieu, Warren Schudy: How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments. Electronic Colloquium on Computational Complexity (ECCC) 13(144): (2006)
73	EE	Marek Chrobak, Claire Kenyon, Neal E. Young: The reverse greedy algorithm for the metric k-median problem. Inf. Process. Lett. 97(2): 68-72 (2006)
72	EE	János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber: On the Sum-of-Squares algorithm for bin packing. J. ACM 53(1): 1-65 (2006)
71	EE	Marek Chrobak, Claire Kenyon-Mathieu: SIGACT news online algorithms column 10: competitiveness via doubling. SIGACT News 37(4): 115-126 (2006)
2005
70	EE	Marek Chrobak, Claire Kenyon, Neal E. Young: The Reverse Greedy Algorithm for the Metric K-Median Problem. COCOON 2005: 654-660
69	EE	Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, Frank McSherry: On profit-maximizing envy-free pricing. SODA 2005: 1164-1173
68	EE	Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young: Oblivious Medians via Online Bidding CoRR abs/cs/0504103: (2005)
67	EE	Marek Chrobak, Claire Kenyon, Neal E. Young: The reverse greedy algorithm for the metric k-median problem CoRR abs/cs/0504104: (2005)
66	EE	János Csirik, David S. Johnson, Claire Kenyon: On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin Packing CoRR abs/cs/0509031: (2005)
2004
65	EE	José R. Correa, Claire Kenyon: Approximation schemes for multidimensional packing. SODA 2004: 186-195
64	EE	Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon: Approximation schemes for Metric Bisection and partitioning. SODA 2004: 506-515
63	EE	Claire Kenyon: Approximation Schemes for Metric Clustering Problems. STACS 2004: 1-3
62	EE	Claire Kenyon, Yuval Rabani, Alistair Sinclair: Low distortion maps between point sets. STOC 2004: 272-280
61	EE	Claire Kenyon, Samuel Kutin: Sensitivity, block sensitivity, and l-block sensitivity of boolean functions. Inf. Comput. 189(1): 43-53 (2004)
60	EE	Adam L. Buchsbaum, Howard J. Karloff, Claire Kenyon, Nick Reingold, Mikkel Thorup: OPT Versus LOAD in Dynamic Storage Allocation. SIAM J. Comput. 33(3): 632-646 (2004)
2003
59	EE	Jérémy Barbay, Claire Kenyon: Deterministic Algorithm for the t-Threshold Set Problem. ISAAC 2003: 575-584
58	EE	Richard M. Karp, Claire Kenyon: A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding. RANDOM-APPROX 2003: 329-340
57	EE	Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani: Approximation schemes for clustering problems. STOC 2003: 50-58
56	EE	Adam L. Buchsbaum, Howard J. Karloff, Claire Kenyon, Nick Reingold, Mikkel Thorup: OPT versus LOAD in dynamic storage allocation. STOC 2003: 556-564
55	EE	Claire Kenyon, Nicolas Schabanel: The Data Broadcast Problem with Non-Uniform Transmission Times. Algorithmica 35(2): 146-175 (2003)
54	EE	Anna R. Karlin, Claire Kenyon, Dana Randall: Dynamic TCP Acknowledgment and Other Stories about e/(e-1). Algorithmica 36(3): 209-224 (2003)
2002
53	EE	Jérémy Barbay, Claire Kenyon: Adaptive intersection and t-threshold problems. SODA 2002: 390-399
52	EE	Mordecai J. Golin, Claire Kenyon, Neal E. Young: Huffman coding with unequal letter costs. STOC 2002: 785-791
51	EE	Abdel Krim Amoura, Evripidis Bampis, Claire Kenyon, Yannis Manoussakis: Scheduling Independent Multiprocessor Tasks. Algorithmica 32(2): 247-261 (2002)
50	EE	Claire Kenyon, Nicolas Schabanel, Neal E. Young: Polynomial-Time Approximation Scheme for Data Broadcast CoRR cs.DS/0205012: (2002)
49	EE	Mordecai J. Golin, Claire Kenyon, Neal E. Young: Huffman Coding with Unequal Letter Costs CoRR cs.DS/0205048: (2002)
48	EE	János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber: On the Sum-of-Squares Algorithm for Bin Packing CoRR cs.DS/0210013: (2002)
47	EE	Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani: Polynomial Time Approximation Schemes for Metric Min-Sum Clustering Electronic Colloquium on Computational Complexity (ECCC)(025): (2002)
46	EE	Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon: A Polynomial Time Approximation Scheme for Metric MIN-BISECTION Electronic Colloquium on Computational Complexity (ECCC)(041): (2002)
45	EE	Claire Kenyon, Michael Mitzenmacher: Linear waste of best fit bin packing on skewed distributions. Random Struct. Algorithms 20(3): 441-464 (2002)
2001
44		Claire Kenyon, Elchanan Mossel, Yuval Peres: Glauber Dynamics on Trees and Hyperbolic Graphs. FOCS 2001: 568-578
43	EE	János Csirik, David S. Johnson, Claire Kenyon: Better approximation algorithms for bin covering. SODA 2001: 557-566
42	EE	Jérémy Barbay, Claire Kenyon: On the discrete Bak-Sneppen model of self-organized criticality. SODA 2001: 928-933
41	EE	Anna R. Karlin, Claire Kenyon, Dana Randall: Dynamic TCP acknowledgement and other stories about e/(e-1). STOC 2001: 502-509
40	EE	Wenceslas Fernandez de la Vega, Claire Kenyon: A Randomized Approximation Scheme for Metric MAX-CUT. J. Comput. Syst. Sci. 63(4): 531-541 (2001)
2000
39		Claire Kenyon, Michael Mitzenmacher: Linear Waste of Best Fit Bin Packing on Skewed Distributions. FOCS 2000: 582-589
38	EE	Foto N. Afrati, Evripidis Bampis, Aleksei V. Fishkin, Klaus Jansen, Claire Kenyon: Scheduling to Minimize the Average Completion Time of Dedicated Tasks. FSTTCS 2000: 454-464
37	EE	János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber: On the sum-of-squares algorithm for bin packing. STOC 2000: 208-217
36	EE	Claire Kenyon, Nicolas Schabanel, Neal E. Young: Polynomial-time approximation scheme for data broadcast. STOC 2000: 659-666
35	EE	Claire Kenyon, Eric Rémila: A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem. Math. Oper. Res. 25(4): 645-656 (2000)
1999
34	EE	János Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber: A Self Organizing Bin Packing Heuristic. ALENEX 1999: 246-265
33	EE	Foto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein, Maxim Sviridenko: Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. FOCS 1999: 32-44
32		Foto N. Afrati, Evripidis Bampis, Claire Kenyon, Ioannis Milis: Scheduling on a Constant Number of Machines. RANDOM-APPROX 1999: 281-287
31	EE	Claire Kenyon, Nicolas Schabanel: The Data Broadcast Problem with Non-Uniform Transmission Rimes. SODA 1999: 547-556
30	EE	Afonso Ferreira, Claire Kenyon, Andrew Rau-Chaplin, Stéphane Ubéda: d-Dimensional Range Search on Multicomputers. Algorithmica 24(3-4): 195-208 (1999)
29		Richard M. Karp, Claire Kenyon, Orli Waarts: Error-resilient DNA computation. Random Struct. Algorithms 15(3-4): 450-466 (1999)
1998
28	EE	Wenceslas Fernandez de la Vega, Claire Kenyon: A Randomized Approximation Scheme for Metric MAX-CUT. FOCS 1998: 468-471
27		Claire Kenyon, Hélène Paugam-Moisy: Multilayer Neural Networks and Polyhedral Dichotomies. Ann. Math. Artif. Intell. 24(1-4): 115-128 (1998)
26		Claire Kenyon, Yuval Rabani, Alistair Sinclair: Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing. J. Algorithms 27(2): 218-235 (1998)
1997
25		Abdel Krim Amoura, Evripidis Bampis, Claire Kenyon, Yannis Manoussakis: Scheduling Independent Multiprocessor Tasks. ESA 1997: 1-12
24	EE	Afonso Ferreira, Claire Kenyon, Andrew Rau-Chaplin, Stéphane Ubéda: d-Dimensional Range Search on Multicomputers. IPPS 1997: 616-620
23		Guy Louchard, Claire Kenyon, René Schott: Data Structures' Maxima. SIAM J. Comput. 26(4): 1006-1042 (1997)
1996
22		Claire Kenyon, Eric Rémila: Approximate Strip Packing. FOCS 1996: 31-36
21	EE	G. Brightwell, Claire Kenyon, Hélène Paugam-Moisy: Multilayer Neural Networks: One or Two Hidden Layers? NIPS 1996: 148-154
20		Claire Kenyon, Yuval Rabani, Alistair Sinclair: Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing (Preliminary Version). SODA 1996: 351-358
19		Claire Kenyon: Best-Fit Bin-Packing with Random Order. SODA 1996: 359-364
18		Richard M. Karp, Claire Kenyon, Orli Waarts: Error-Resilient DNA Computation. SODA 1996: 458-467
17	EE	Claire Kenyon, Eric Rémila: Perfect matchings in the triangular lattice. Discrete Mathematics 152(1-3): 191-210 (1996)
1994
16		Micah Adler, Peter Gemmell, Mor Harchol-Balter, Richard M. Karp, Claire Kenyon: Selection in the Presence of Noise: The Design of Playoff Systems. SODA 1994: 564-572
15		Claire Kenyon, Valerie King: On Boolean Decision Trees with Faulty Nodes. Random Struct. Algorithms 5(3): 453-464 (1994)
1993
14	EE	Claire Kenyon, Dana Randall, Alistair Sinclair: Matchings in lattice graphs. STOC 1993: 738-746
13		Pierre Fraigniaud, Claire Kenyon, Andrzej Pelc: Finding a Target Subnetwork in Sparse Networks with Random Faults. Inf. Process. Lett. 48(6): 297-303 (1993)
12		Wayne Goddard, Claire Kenyon, Valerie King, Leonard J. Schulman: Optimal Randomized Algorithms for Local Sorting and Set-Maxima. SIAM J. Comput. 22(2): 272-283 (1993)
1992
11		Claire Kenyon, Richard Kenyon: Tiling a Polygon with Rectangles FOCS 1992: 610-619
10		Claire Kenyon, Valerie King: On Boolean Decision Trees with Faulty Nodes. ISTCS 1992: 24-31
9		Claire Kenyon, Richard Kenyon: How to Take Short Cuts. Discrete & Computational Geometry 8: 251-264 (1992)
1991
8		Guy Louchard, Claire Kenyon, René Schott: Data Structures Maxima. FCT 1991: 339-349
7	EE	Claire Kenyon, Richard Kenyon: How to Take Short Cuts. Symposium on Computational Geometry 1991: 250-255
6		Claire Kenyon, Jeffrey Scott Vitter: Maximum Queue Size and Hashing with Lazy Deletion. Algorithmica 6(4): 597-619 (1991)
5		Claire Kenyon-Mathieu, Jeffrey Scott Vitter: The Maximum Size of Dynamic Data Structures. SIAM J. Comput. 20(5): 807-823 (1991)
1990
4		Claire Kenyon, Andrew Chi-Chih Yao: On Evaluating Boolean Functions with Unreliable Tests. Int. J. Found. Comput. Sci. 1(1): 1-10 (1990)
1989
3		Claire Kenyon-Mathieu, Jeffrey Scott Vitter: General Methods for the Analysis of the Maximum Size of Dynamic Data Structures (Extended Abstract). ICALP 1989: 473-487
2		Claire Kenyon-Mathieu, Valerie King: Verifying Partial Orders STOC 1989: 367-374
1987
1		Claire Mathieu: Some Problems in Computational Geometry. Algorithmica 2: 131-134 (1987)

Coauthor Index

1	Micah Adler	[16]
2	Foto N. Afrati	[32] [33] [38]
3	Abdel Krim Amoura	[25] [51]
4	Yossi Azar	[92]
5	Evripidis Bampis	[25] [32] [33] [38] [51]
6	Jérémy Barbay	[42] [53] [59] [89]
7	Benjamin E. Birnbaum	[85] [92]
8	Glencora Borradaile	[78] [81] [93]
9	G. Brightwell	[21]
10	Adam L. Buchsbaum	[56] [60]
11	Matthew Cary	[83]
12	Moses Charikar	[90]
13	Chandra Chekuri	[33]
14	Marek Chrobak	[67] [68] [70] [71] [73] [76] [88]
15	José R. Correa	[65]
16	János Csirik	[34] [37] [43] [48] [66] [72]
17	Aparna Das	[75] [83] [87]
18	Benjamin Edelman	[83]
19	Afonso Ferreira	[24] [30]
20	Aleksei V. Fishkin	[38]
21	Pierre Fraigniaud	[13]
22	Peter Gemmell	[16]
23	Ioannis Giotis	[83]
24	Wayne Goddard	[12]
25	Mordecai J. Golin	[49] [52]
26	Venkatesan Guruswami	[69]
27	Mor Harchol-Balter	[16]
28	Jason D. Hartline	[69]
29	Kurtis Heimerl	[83]
30	Klaus Jansen	[38]
31	David S. Johnson	[34] [37] [43] [48] [66] [72]
32	David R. Karger	[33]
33	Anna R. Karlin	[41] [54] [69] [83] [92]
34	Howard J. Karloff	[56] [60] [90]
35	Richard M. Karp	[16] [18] [29] [58]
36	Marek Karpinski	[46] [47] [57] [64]
37	Irit Katriel	[82] [84]
38	David Kempe	[69]
39	Richard Kenyon	[7] [9] [11]
40	Sanjeev Khanna	[33]
41	Valerie King	[2] [10] [12] [15]
42	Philip N. Klein	[78] [81] [93]
43	Samuel Kutin	[61]
44	Guy Louchard	[8] [23]
45	Yannis Manoussakis	[25] [51]
46	Frank McSherry	[69]
47	Ioannis Milis	[32] [33]
48	Michael Mitzenmacher	[39] [45]
49	Elchanan Mossel	[44]
50	Joseph Naor (Seffi Naor)	[90]
51	C. Thach Nguyen	[92]
52	John Noga	[68] [76] [88]
53	James B. Orlin	[37] [48] [72]
54	Charalampos Papamanthou	[86]
55	Hélène Paugam-Moisy	[21] [27]
56	Andrzej Pelc	[13]
57	Yuval Peres	[44]
58	Maurice Queyranne	[33]
59	Yuval Rabani	[20] [26] [47] [57] [62]
60	Dana Randall	[14] [41] [54]
61	Andrew Rau-Chaplin	[24] [30]
62	Nick Reingold	[56] [60]
63	Eric Rémila	[17] [22] [35]
64	Michael E. Saks	[90]
65	Nicolas Schabanel	[31] [36] [50] [55]
66	René Schott	[8] [23]
67	Warren Schudy	[74] [79] [91]
68	Leonard J. Schulman	[12]
69	Michael Schwarz	[83]
70	Meinolf Sellmann	[77]
71	Peter W. Shor	[34] [37] [48] [72]
72	Alistair Sinclair	[14] [20] [26] [62]
73	Martin Skutella	[33]
74	Clifford Stein	[33]
75	Maxim Sviridenko	[33]
76	Mikkel Thorup	[56] [60]
77	Stéphane Ubéda	[24] [30]
78	Eli Upfal	[82] [84]
79	Wenceslas Fernandez de la Vega	[28] [40] [46] [47] [57] [64] [80]
80	Jeffrey Scott Vitter	[3] [5] [6]
81	Orli Waarts	[18] [29]
82	Richard R. Weber	[34] [37] [48] [72]
83	Andrew Chi-Chih Yao	[4]
84	Neal E. Young	[36] [49] [50] [52] [67] [68] [70] [73] [76] [88]

Colors in the list of coauthors