dblp.uni-trier.dewww.uni-trier.de

Claire Mathieu Vis

Claire Kenyon, Claire Kenyon-Mathieu

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
98 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
97EEClaire Mathieu, Alistair Sinclair: Sherali-adams relaxations of the matching polytope. STOC 2009: 293-302
96EEGlencora Borradaile, Philip N. Klein, Claire Mathieu: An O(n log n) approximation scheme for Steiner tree in planar graphs. ACM Transactions on Algorithms 5(3): (2009)
95EEAparna Das, Claire Mathieu, Daniel Ricketts: Maximizing profit using recommender systems CoRR abs/0908.3633: (2009)
2008
94EEGlencora Borradaile, Philip N. Klein, Claire Mathieu: A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. FOCS 2008: 115-124
93EEYossi Azar, Benjamin E. Birnbaum, Anna R. Karlin, Claire Mathieu, C. Thach Nguyen: Improved Approximation Algorithms for Budgeted Allocations. ICALP (1) 2008: 186-197
92EEClaire Mathieu, Warren Schudy: Yet another algorithm for dense max cut: go greedy. SODA 2008: 176-182
91EEMoses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, Michael E. Saks: Online multicast with egalitarian cost sharing. SPAA 2008: 70-76
90EEJérémy Barbay, Claire Kenyon: Alternation and redundancy analysis of the intersection problem. ACM Transactions on Algorithms 4(1): (2008)
89EEMarek Chrobak, Claire Kenyon, John Noga, Neal E. Young: Incremental Medians via Online Bidding. Algorithmica 50(4): 455-478 (2008)
88EEAparna Das, Claire Mathieu: A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing CoRR abs/0812.1595: (2008)
87EEClaire Mathieu, Charalampos Papamanthou: Distortion lower bounds for line embeddings. Inf. Process. Lett. 108(4): 175-178 (2008)
86EEBenjamin E. Birnbaum, Claire Mathieu: On-line bipartite matching made simple. SIGACT News 39(1): 80-87 (2008)
85EEIrit Katriel, Claire Kenyon-Mathieu, Eli Upfal: Commitment under uncertainty: Two-stage stochastic matching problems. Theor. Comput. Sci. 408(2-3): 213-223 (2008)
2007
84EEMatthew 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
83EEIrit Katriel, Claire Kenyon-Mathieu, Eli Upfal: Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems. ICALP 2007: 171-182
82EEGlencora Borradaile, Claire Kenyon-Mathieu, Philip N. Klein: A polynomial-time approximation scheme for Steiner tree in planar graphs. SODA 2007: 1285-1294
81EEWenceslas Fernandez de la Vega, Claire Kenyon-Mathieu: Linear programming relaxations of maxcut. SODA 2007: 53-61
80EEClaire Kenyon-Mathieu, Warren Schudy: How to rank with few errors. STOC 2007: 95-103
79EEGlencora 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
78EEClaire Kenyon, Meinolf Sellmann: Plan B: Uncertainty/Time Trade-Offs for Linear and Integer Programming. CPAIOR 2006: 126-138
77EEMarek Chrobak, Claire Kenyon, John Noga, Neal E. Young: Oblivious Medians Via Online Bidding. LATIN 2006: 311-322
76EEAparna Das, Claire Kenyon: On Hierarchical Diameter-Clustering, and the Supplier Problem. WAOA 2006: 132-145
75EEClaire 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)
74EEMarek Chrobak, Claire Kenyon, Neal E. Young: The reverse greedy algorithm for the metric k-median problem. Inf. Process. Lett. 97(2): 68-72 (2006)
73EEJá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)
72EENikhil Bansal, José R. Correa, Claire Kenyon, Maxim Sviridenko: Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes. Math. Oper. Res. 31(1): 31-49 (2006)
71EEMarek Chrobak, Claire Kenyon-Mathieu: SIGACT news online algorithms column 10: competitiveness via doubling. SIGACT News 37(4): 115-126 (2006)
2005
70EEMarek Chrobak, Claire Kenyon, Neal E. Young: The Reverse Greedy Algorithm for the Metric K-Median Problem. COCOON 2005: 654-660
69EEVenkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, Frank McSherry: On profit-maximizing envy-free pricing. SODA 2005: 1164-1173
68EEMarek Chrobak, Claire Kenyon, John Noga, Neal E. Young: Oblivious Medians via Online Bidding CoRR abs/cs/0504103: (2005)
67EEMarek Chrobak, Claire Kenyon, Neal E. Young: The reverse greedy algorithm for the metric k-median problem CoRR abs/cs/0504104: (2005)
66EEJá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
65EEJosé R. Correa, Claire Kenyon: Approximation schemes for multidimensional packing. SODA 2004: 186-195
64EEWenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon: Approximation schemes for Metric Bisection and partitioning. SODA 2004: 506-515
63EEClaire Kenyon: Approximation Schemes for Metric Clustering Problems. STACS 2004: 1-3
62EEClaire Kenyon, Yuval Rabani, Alistair Sinclair: Low distortion maps between point sets. STOC 2004: 272-280
61EEClaire Kenyon, Samuel Kutin: Sensitivity, block sensitivity, and l-block sensitivity of boolean functions. Inf. Comput. 189(1): 43-53 (2004)
60EEAdam 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
59EEJérémy Barbay, Claire Kenyon: Deterministic Algorithm for the t-Threshold Set Problem. ISAAC 2003: 575-584
58EERichard M. Karp, Claire Kenyon: A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding. RANDOM-APPROX 2003: 329-340
57EEWenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani: Approximation schemes for clustering problems. STOC 2003: 50-58
56EEAdam L. Buchsbaum, Howard J. Karloff, Claire Kenyon, Nick Reingold, Mikkel Thorup: OPT versus LOAD in dynamic storage allocation. STOC 2003: 556-564
55EEClaire Kenyon, Nicolas Schabanel: The Data Broadcast Problem with Non-Uniform Transmission Times. Algorithmica 35(2): 146-175 (2003)
54EEAnna R. Karlin, Claire Kenyon, Dana Randall: Dynamic TCP Acknowledgment and Other Stories about e/(e-1). Algorithmica 36(3): 209-224 (2003)
2002
53EEJérémy Barbay, Claire Kenyon: Adaptive intersection and t-threshold problems. SODA 2002: 390-399
52EEMordecai J. Golin, Claire Kenyon, Neal E. Young: Huffman coding with unequal letter costs. STOC 2002: 785-791
51EEAbdel Krim Amoura, Evripidis Bampis, Claire Kenyon, Yannis Manoussakis: Scheduling Independent Multiprocessor Tasks. Algorithmica 32(2): 247-261 (2002)
50EEClaire Kenyon, Nicolas Schabanel, Neal E. Young: Polynomial-Time Approximation Scheme for Data Broadcast CoRR cs.DS/0205012: (2002)
49EEMordecai J. Golin, Claire Kenyon, Neal E. Young: Huffman Coding with Unequal Letter Costs CoRR cs.DS/0205048: (2002)
48EEJá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)
47EEWenceslas 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)
46EEWenceslas 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)
45EEClaire 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
43EEJános Csirik, David S. Johnson, Claire Kenyon: Better approximation algorithms for bin covering. SODA 2001: 557-566
42EEJérémy Barbay, Claire Kenyon: On the discrete Bak-Sneppen model of self-organized criticality. SODA 2001: 928-933
41EEAnna R. Karlin, Claire Kenyon, Dana Randall: Dynamic TCP acknowledgement and other stories about e/(e-1). STOC 2001: 502-509
40EEWenceslas 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
38EEFoto 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
37EEJá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
36EEClaire Kenyon, Nicolas Schabanel, Neal E. Young: Polynomial-time approximation scheme for data broadcast. STOC 2000: 659-666
35EEClaire Kenyon, Eric Rémila: A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem. Math. Oper. Res. 25(4): 645-656 (2000)
1999
34EEJános Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber: A Self Organizing Bin Packing Heuristic. ALENEX 1999: 246-265
33EEFoto 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
31EEClaire Kenyon, Nicolas Schabanel: The Data Broadcast Problem with Non-Uniform Transmission Rimes. SODA 1999: 547-556
30EEAfonso 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
28EEWenceslas 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
25EEAbdel Krim Amoura, Evripidis Bampis, Claire Kenyon, Yannis Manoussakis: Scheduling Independent Multiprocessor Tasks. ESA 1997: 1-12
24EEAfonso 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
21EEG. 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
17EEClaire 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
14EEClaire 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
10EEClaire 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
7EEClaire 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
3EEClaire 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

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

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)