Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Claire Mathieu
Claire Kenyon – Claire Kenyon-Mathieu
2010 – today
- 2013
[i21]Glencora Borradaile, Philip N. Klein, Claire Mathieu: A polynomial-time approximation scheme for Euclidean Steiner forest. CoRR abs/1302.7270 (2013)- [i20]
- 2012
- [j38]Robert Cori, Claire Mathieu, John Michael Robson: On the Number of Indecomposable Permutations with a Given Number of Cycles. Electr. J. Comb. 19(1): P49 (2012)
- [j37]Claire Mathieu, Olga Ohrimenko: Lower bounds for randomized algorithms for online chain partitioning. Inf. Process. Lett. 112(17-18): 663-666 (2012)
- [j36]Mordecai J. Golin, Claire Mathieu, Neal E. Young: Huffman Coding with Letter Costs: A Linear-Time Approximation Scheme. SIAM J. Comput. 41(3): 684-713 (2012)
- [c64]Christian Konrad, Frédéric Magniez, Claire Mathieu: Maximum Matching in Semi-streaming with Few Passes. APPROX-RANDOM 2012: 231-242
- [c63]David Eisenstat, Philip N. Klein, Claire Mathieu: An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. SODA 2012: 626-638
- [c62]MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Philip N. Klein, Claire Mathieu: A polynomial-time approximation scheme for planar multiway cut. SODA 2012: 639-655
- [i19]Claire Mathieu, David B. Wilson: The min mean-weight cycle in a random network. CoRR abs/1201.3955 (2012)
- 2011
- [c61]Anna R. Karlin, Claire Mathieu, C. Thach Nguyen: Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack. IPCO 2011: 301-314
- [i18]David Eisenstat, Philip N. Klein, Claire Mathieu: An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. CoRR abs/1110.1320 (2011)
- [i17]Christian Konrad, Frédéric Magniez, Claire Mathieu: Maximum Matching in Semi-Streaming with Few Passes. CoRR abs/1112.0184 (2011)
- [i16]Klaus Jansen, Claire Mathieu, Hadas Shachnai, Neal E. Young: Packing and Scheduling Algorithms for Information and Communication Services (Dagstuhl Seminar 11091). Dagstuhl Reports 1(2): 67-93 (2011)
- 2010
- [j35]
- [c60]Aparna Das, Claire Mathieu: A Quasi-polynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing. SODA 2010: 390-403
- [c59]
- [c58]
- [c57]Frédéric Magniez, Claire Mathieu, Ashwin Nayak: Recognizing well-parenthesized expressions in the streaming model. STOC 2010: 261-270
- [c56]Aparna Das, Claire Mathieu, Shay Mozes: The Train Delivery Problem - Vehicle Routing Meets Bin Packing. WAOA 2010: 94-105
- [c55]
- [i15]Claire Mathieu, Ocan Sankur, Warren Schudy: Online Correlation Clustering. CoRR abs/1001.0920 (2010)
- [i14]Anna R. Karlin, Claire Mathieu, C. Thach Nguyen: Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack. CoRR abs/1007.1283 (2010)
2000 – 2009
- 2009
- [j34]Aparna Das, Claire Kenyon-Mathieu: On Hierarchical Diameter-Clustering and the Supplier Problem. Theory Comput. Syst. 45(3): 497-511 (2009)
- [j33]Claire Kenyon, Yuval Rabani, Alistair Sinclair: Low Distortion Maps Between Point Sets. SIAM J. Comput. 39(4): 1617-1636 (2009)
- [j32]Glencora 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)
- [c54]Claire Mathieu, Alistair Sinclair: Sherali-adams relaxations of the matching polytope. STOC 2009: 293-302
- [e1]Claire Mathieu (Ed.): Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009. SIAM 2009
- [i13]Aparna Das, Claire Mathieu, Daniel Ricketts: Maximizing profit using recommender systems. CoRR abs/0908.3633 (2009)
- [i12]Frédéric Magniez, Claire Mathieu, Ashwin Nayak: Recognizing well-parenthesized expressions in the streaming model. CoRR abs/0911.3291 (2009)
- [i11]Frédéric Magniez, Claire Mathieu, Ashwin Nayak: Recognizing well-parenthesized expressions in the streaming model. Electronic Colloquium on Computational Complexity (ECCC) 16: 119 (2009)
- 2008
- [j31]Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young: Incremental Medians via Online Bidding. Algorithmica 50(4): 455-478 (2008)
- [j30]Claire Mathieu, Charalampos Papamanthou: Distortion lower bounds for line embeddings. Inf. Process. Lett. 108(4): 175-178 (2008)
- [j29]Benjamin E. Birnbaum, Claire Mathieu: On-line bipartite matching made simple. SIGACT News 39(1): 80-87 (2008)
- [j28]Jérémy Barbay, Claire Kenyon: Alternation and redundancy analysis of the intersection problem. ACM Transactions on Algorithms 4(1) (2008)
- [j27]Irit Katriel, Claire Kenyon-Mathieu, Eli Upfal: Commitment under uncertainty: Two-stage stochastic matching problems. Theor. Comput. Sci. 408(2-3): 213-223 (2008)
- [c53]Glencora Borradaile, Philip N. Klein, Claire Mathieu: A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. FOCS 2008: 115-124
- [c52]Yossi Azar, Benjamin E. Birnbaum, Anna R. Karlin, Claire Mathieu, C. Thach Nguyen: Improved Approximation Algorithms for Budgeted Allocations. ICALP (1) 2008: 186-197
- [c51]Claire Mathieu, Warren Schudy: Yet another algorithm for dense max cut: go greedy. SODA 2008: 176-182
- [c50]Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, Michael E. Saks: Online multicast with egalitarian cost sharing. SPAA 2008: 70-76
- [i10]Aparna Das, Claire Mathieu: A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing. CoRR abs/0812.1595 (2008)
- 2007
- [c49]Irit Katriel, Claire Kenyon-Mathieu, Eli Upfal: Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems. ICALP 2007: 171-182
- [c48]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
- [c47]Wenceslas Fernandez de la Vega, Claire Kenyon-Mathieu: Linear programming relaxations of maxcut. SODA 2007: 53-61
- [c46]Glencora Borradaile, Claire Kenyon-Mathieu, Philip N. Klein: A polynomial-time approximation scheme for Steiner tree in planar graphs. SODA 2007: 1285-1294
- [c45]
- [c44]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
- [j26]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)
- [j25]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)
- [j24]Nikhil 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)
- [j23]Marek Chrobak, Claire Kenyon-Mathieu: SIGACT news online algorithms column 10: competitiveness via doubling. SIGACT News 37(4): 115-126 (2006)
- [c43]Claire Kenyon, Meinolf Sellmann: Plan B: Uncertainty/Time Trade-Offs for Linear and Integer Programming. CPAIOR 2006: 126-138
- [c42]Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young: Oblivious Medians Via Online Bidding. LATIN 2006: 311-322
- [c41]Aparna Das, Claire Kenyon: On Hierarchical Diameter-Clustering, and the Supplier Problem. WAOA 2006: 132-145
- [i9]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)
- 2005
- [c40]Marek Chrobak, Claire Kenyon, Neal E. Young: The Reverse Greedy Algorithm for the Metric K-Median Problem. COCOON 2005: 654-660
- [c39]Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, Frank McSherry: On profit-maximizing envy-free pricing. SODA 2005: 1164-1173
- [i8]Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young: Oblivious Medians via Online Bidding. CoRR abs/cs/0504103 (2005)
- [i7]Marek Chrobak, Claire Kenyon, Neal E. Young: The reverse greedy algorithm for the metric k-median problem. CoRR abs/cs/0504104 (2005)
- [i6]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
- [j22]Claire Kenyon, Samuel Kutin: Sensitivity, block sensitivity, and l-block sensitivity of boolean functions. Inf. Comput. 189(1): 43-53 (2004)
- [j21]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)
- [c38]José R. Correa, Claire Kenyon: Approximation schemes for multidimensional packing. SODA 2004: 186-195
- [c37]Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon: Approximation schemes for Metric Bisection and partitioning. SODA 2004: 506-515
- [c36]
- [c35]Claire Kenyon, Yuval Rabani, Alistair Sinclair: Low distortion maps between point sets. STOC 2004: 272-280
- 2003
- [j20]Claire Kenyon, Nicolas Schabanel: The Data Broadcast Problem with Non-Uniform Transmission Times. Algorithmica 35(2): 146-175 (2003)
- [j19]Anna R. Karlin, Claire Kenyon, Dana Randall: Dynamic TCP Acknowledgment and Other Stories about e/(e-1). Algorithmica 36(3): 209-224 (2003)
- [c34]Jérémy Barbay, Claire Kenyon: Deterministic Algorithm for the t-Threshold Set Problem. ISAAC 2003: 575-584
- [c33]Richard M. Karp, Claire Kenyon: A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding. RANDOM-APPROX 2003: 329-340
- [c32]Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani: Approximation schemes for clustering problems. STOC 2003: 50-58
- [c31]Adam L. Buchsbaum, Howard J. Karloff, Claire Kenyon, Nick Reingold, Mikkel Thorup: OPT versus LOAD in dynamic storage allocation. STOC 2003: 556-564
- 2002
- [j18]Abdel Krim Amoura, Evripidis Bampis, Claire Kenyon, Yannis Manoussakis: Scheduling Independent Multiprocessor Tasks. Algorithmica 32(2): 247-261 (2002)
- [j17]Claire Kenyon, Michael Mitzenmacher: Linear waste of best fit bin packing on skewed distributions. Random Struct. Algorithms 20(3): 441-464 (2002)
- [c30]
- [c29]Mordecai J. Golin, Claire Kenyon, Neal E. Young: Huffman coding with unequal letter costs. STOC 2002: 785-791
- [i5]Claire Kenyon, Nicolas Schabanel, Neal E. Young: Polynomial-Time Approximation Scheme for Data Broadcast. CoRR cs.DS/0205012 (2002)
- [i4]Mordecai J. Golin, Claire Kenyon, Neal E. Young: Huffman Coding with Unequal Letter Costs. CoRR cs.DS/0205048 (2002)
- [i3]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)
- [i2]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)
- [i1]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)
- 2001
- [j16]Wenceslas Fernandez de la Vega, Claire Kenyon: A Randomized Approximation Scheme for Metric MAX-CUT. J. Comput. Syst. Sci. 63(4): 531-541 (2001)
- [c28]Claire Kenyon, Elchanan Mossel, Yuval Peres: Glauber Dynamics on Trees and Hyperbolic Graphs. FOCS 2001: 568-578
- [c27]János Csirik, David S. Johnson, Claire Kenyon: Better approximation algorithms for bin covering. SODA 2001: 557-566
- [c26]Jérémy Barbay, Claire Kenyon: On the discrete Bak-Sneppen model of self-organized criticality. SODA 2001: 928-933
- [c25]Anna R. Karlin, Claire Kenyon, Dana Randall: Dynamic TCP acknowledgement and other stories about e/(e-1). STOC 2001: 502-509
- 2000
- [j15]Claire Kenyon, Eric Rémila: A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem. Math. Oper. Res. 25(4): 645-656 (2000)
- [c24]Claire Kenyon, Michael Mitzenmacher: Linear Waste of Best Fit Bin Packing on Skewed Distributions. FOCS 2000: 582-589
- [c23]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
- [c22]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
- [c21]Claire Kenyon, Nicolas Schabanel, Neal E. Young: Polynomial-time approximation scheme for data broadcast. STOC 2000: 659-666
1990 – 1999
- 1999
- [j14]Afonso Ferreira, Claire Kenyon, Andrew Rau-Chaplin, Stéphane Ubéda: d-Dimensional Range Search on Multicomputers. Algorithmica 24(3-4): 195-208 (1999)
- [j13]Richard M. Karp, Claire Kenyon, Orli Waarts: Error-resilient DNA computation. Random Struct. Algorithms 15(3-4): 450-466 (1999)
- [c20]János Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber: A Self Organizing Bin Packing Heuristic. ALENEX 1999: 246-265
- [c19]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
- [c18]Foto N. Afrati, Evripidis Bampis, Claire Kenyon, Ioannis Milis: Scheduling on a Constant Number of Machines. RANDOM-APPROX 1999: 281-287
- [c17]Claire Kenyon, Nicolas Schabanel: The Data Broadcast Problem with Non-Uniform Transmission Rimes. SODA 1999: 547-556
- 1998
- [j12]Claire Kenyon, Hélène Paugam-Moisy: Multilayer Neural Networks and Polyhedral Dichotomies. Ann. Math. Artif. Intell. 24(1-4): 115-128 (1998)
- [j11]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)
- [c16]Wenceslas Fernandez de la Vega, Claire Kenyon: A Randomized Approximation Scheme for Metric MAX-CUT. FOCS 1998: 468-471
- 1997
- [j10]Guy Louchard, Claire Kenyon, René Schott: Data Structures' Maxima. SIAM J. Comput. 26(4): 1006-1042 (1997)
- [c15]Abdel Krim Amoura, Evripidis Bampis, Claire Kenyon, Yannis Manoussakis: Scheduling Independent Multiprocessor Tasks. ESA 1997: 1-12
- [c14]Afonso Ferreira, Claire Kenyon, Andrew Rau-Chaplin, Stéphane Ubéda: d-Dimensional Range Search on Multicomputers. IPPS 1997: 616-620
- 1996
- [j9]Claire Kenyon, Eric Rémila: Perfect matchings in the triangular lattice. Discrete Mathematics 152(1-3): 191-210 (1996)
- [c13]
- [c12]Graham Brightwell, Claire Kenyon, Hélène Paugam-Moisy: Multilayer Neural Networks: One or Two Hidden Layers? NIPS 1996: 148-154
- [c11]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
- [c10]
- [c9]
- 1994
- [j8]Claire Kenyon, Valerie King: On Boolean Decision Trees with Faulty Nodes. Random Struct. Algorithms 5(3): 453-464 (1994)
- [c8]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
- 1993
- [j7]Pierre Fraigniaud, Claire Kenyon, Andrzej Pelc: Finding a Target Subnetwork in Sparse Networks with Random Faults. Inf. Process. Lett. 48(6): 297-303 (1993)
- [j6]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)
- [c7]
- 1992
- [j5]Claire Kenyon, Richard Kenyon: How to Take Short Cuts. Discrete & Computational Geometry 8: 251-264 (1992)
- [c6]
- [c5]
- 1991
- [j4]Claire Kenyon, Jeffrey Scott Vitter: Maximum Queue Size and Hashing with Lazy Deletion. Algorithmica 6(4): 597-619 (1991)
- [j3]Claire Kenyon-Mathieu, Jeffrey Scott Vitter: The Maximum Size of Dynamic Data Structures. SIAM J. Comput. 20(5): 807-823 (1991)
- [c4]Claire Kenyon, Richard Kenyon: How to Take Short Cuts. Symposium on Computational Geometry 1991: 250-255
- [c3]
- 1990
- [j2]Claire Kenyon, Andrew Chi-Chih Yao: On Evaluating Boolean Functions with Unreliable Tests. Int. J. Found. Comput. Sci. 1(1): 1-10 (1990)
1980 – 1989
- 1989
- [c2]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
- [c1]
- 1987
- [j1]
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-13 23:10 CEST by the dblp team