Claire Mathieu's online publications

An O(n log n) approximation scheme with singly exponential dependence on epsilon. Glencora Borradaile, Philip N. Klein, and Claire Mathieu. Submitted.
Greedy Bidding Strategies for Keyword Auctions. Matthew Cary, Aparna Das, Ben Edelman, Ioannis Giotis, Kurtis Heimerl, Anna Karlin, Claire Mathieu, and Michael Schwarz. Eighth ACM Conference on Electronic Commerce (EC), June 2007, to appear.
Online multicast with egalitarian cost sharing. Moses Charikar, Howard Karloff, Claire Mathieu, Joseph (Seffi) Naor, and Michael Saks. Twentieth annual ACM symposium on Parallelism in algorithms and architectures (SPAA), 2008.
Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems. Irit Katriel, Claire Kenyon-Mathieu and Eli Upfal, submitted.
Competitiveness via doubling. Marek Chrobak and Claire Kenyon-Mathieu. ACM Sigact News, December 2006.
How to rank with few errors. Claire Kenyon-Mathieu and Warren Schudy, ACM STOC 2007, to appear. ECCC.
Linear Programming Relaxations of Maxcut. Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu. ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2007.
A Polynomial-Time Approximation Scheme for Steiner Tree in Planar Graphs. Glencora Borradaile, Claire Kenyon-Mathieu and Philip Klein. ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2007.
On hierarchical diameter-clustering, and the supplier problems. Aparna Das and Claire Kenyon. Proceedings of WAOA'06, Fourth Workshop on Approximation and Online Algorithms, September 2006, Zurich, Switzerland, Lecture Notes in Computer Science, Springer.
Alternation and Redundancy analysis of the Intersection Problem, Jeremy Barbay and Claire Kenyon, 2006, ACM Transactions on Algorithms, to appear.
Uncertainity/Time Trade-Offs for Linear and Integer Programming. Claire Kenyon and Meinolf Sellmann Proceedings the Third International Conference on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR), Springer LNCS 3990, pp. 126-138, 2006.
Online Medians via Online Bribery. Marek Chrobak, Claire Kenyon, John Noga, and Neal E. Young. Proceedings of LATIN'06, March 2006, LNCS 3887, 311--322.
The reverse greedy algorithm for the metric k-median problem, M. Chrobak, N. Young, C. Kenyon, 11th International Computing and Combinatorics Conference (COCOON'05). IPL 2, 68-72, Jan 2006.
On Profit-Maximizing Envy-Free Pricing, Venkat Guruswami, Jason Hartline, Anna Karlin, David Kempe, Claire Kenyon, and Frank McSherry, SODA 2005.
Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes, N. Bansal, J.R. Correa, C. Kenyon and M. Sviridenko, Mathematics of Operations Research, 31, 1, Feb 2006, 31--49.
Approximation Schemes for Multidimensional Packing, J.R. Correa and C. Kenyon, Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 179--188.
A Gambling Game and its Application to the Analysis of Adaptive Randomized Rounding, R. Karp and C. Kenyon, Proc. RANDOM 2003.
Low Distortion Maps Between Point Sets, Claire Kenyon, Yuval Rabani, and Alistair Sinclair, Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing (STOC), 2004.
OPT Versus LOAD in Dynamic Storage Allocation, Adam L. Bushbaum, Howard Karloff, Claire Kenyon, Nick Reingold, and Mikkel Thorup, SIAM Journal on Computing, 33(3):632-646, 2004.
Approximation Schemes for Clustering Problems, W. Fernandez de la Vega, Marek Karpinski, Claire Kenyon and Yuval Rabani, STOC'03.
Approximation Schemes for Metric Minimum Bisection and Partitioning, W. Fernandez de la Vega, Marek Karpinski and Claire Kenyon, SODA'04.
Sensitivity, block sensitivity, and l-block sensitivity of boolean functions,Claire Kenyon and Samuel Kutin, Information and Computation, 189, 1, Feb 2004, 43--53.
Glauber Dynamics on Trees and Hyperbolic Graphs, Claire Kenyon, Elchanan Mossel and Yuval Peres, Forty-Second Annual Symposium on Foundations of Computer Science (FOCS), 2001.
Huffman Coding with Unequal Letter Costs, Mordecai J. Golin, Claire Kenyon and Neal E. Young, Proceedings of the {\em Thirty-Fourth Annual ACM Symposium on Theory of Computing (STOC)}, 2002.
Adaptive Intersection and t-Threshold Problems, Jeremy Barbay and Claire Kenyon, Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002. Final version to appear in ACM Transactions on Algorithms, 2006.
Dynamic TCP acknowledgement and other stories about e/(e-1), Anna R. Karlin and Claire Kenyon and Dana Randall, Thirty-Third Annual ACM Symposium on Theory of Computing (STOC), 2001. Algorithmica.
On the discrete Bak-Sneppen model of self-organized criticality, Jérémy Barbay and Claire Kenyon, Twelth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 928-933, 2001.
Better Approximation Algorithms for Bin Covering, J. Csirik, D. S. Johnson, and C. Kenyon. Twelth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2001.
Linear Waste of Best-Fit Bin Packing on Skewed Distributions, Claire Kenyon and Michael Mitzenmacher, Random Structures and Algorithms. A preliminary version appeared in the Forty-First Annual Symposium on Foundations of Computer Science (FOCS), 582-589, 2000.
On the Sum-of-Squares Algorithm for Bin Packing, J. Csirik, D. S. Johnson, C. Kenyon, J. B. Orlin, P. W. Shor, and R. R. Weber. Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), 208-217, 2000. Journal version in JACM, 53(1), 1-65, 2006.
Polynomial-Time Approximation Scheme for Data Broadcast, Claire Kenyon, Nicolas Schabanel et Neal E. Young. Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), 659-666, 2000.
Approximation Schemes for Scheduling to Minimize Average Weighted Completion Time with Release Dates, C. Chekuri, D. Karger, S. Khanna, M. Skutella, C. Stein, F. Afrati, E. Bampis, C. Kenyon and I. Milis, Fortieth Annual Symposium on Foundations of Computer Science (FOCS), 32-44, 1999.
The Data Broadcast Problem with Non-Uniform Transmission Times, Claire Kenyon and Nicolas Schabanel, submitted. A preliminary verison appeared in the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 547-556, 1999.
A self-organizing bin packing heuristic, Janos Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, and Richard Weber, Workshop on Algorithm Engineering and Experimentation (ALENEX), 1999. LNCS 1619, 246-265.
A Randomized Approximation Scheme for Metric MAX-CUT, W. Fernandez de la Vega and Claire Kenyon. Thirty-Ninth Annual IEEE Symposium on Foundations of Computer Science (FOCS), 468-471, 1998. JCSS. Peng Sun and Xin Chen, PhD students at the Operations Research Center at MIT, have found the following remarks and minor mistakes.
Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing , Claire Kenyon, Yuval Rabani and Alistair Sinclair, Journal of Algorithms, Vol. 27, No. 2, 218-235, 1998. A preliminary version appeared in the proceedings of the Seventh Annual ACM-SIAM Symposium On Discrete Algorithms (SODA), 351-358, 1996.
Approximating the Number of Monomer-Dimer Coverings of a Lattice , Claire Kenyon, Dana Randall and Alistair Sinclair, Journal of Statistical Physics 83, 1996, 637-659. A preliminary version appeared in the proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory Of Computing (STOC), 738-746, 1993.
On boolean decision trees with faulty nodes , Claire Kenyon and Valerie King, Random Structures and Algorithms, 5, 3, 453-464, 1994. Copyright 1994 © by Wiley & Sons.
Approximate Strip-Packing , Claire Kenyon and Eric Remila, Thirty-Seventh Annual Symposium on Foundations of Computer Science (FOCS), 31-36, 1996. Mathematics of Operations Research.
Tiling a polygon with rectangles , Claire Kenyon and Richard Kenyon, Thirty-Third Annual Symposium on Foundations of Computer Science (FOCS), Pittsburgh, PA, 610-619, 1992 (beware that figures are missing from file).
How to play random tournaments , Micah Adler, Peter Gemmel, Mor Harchol, Richard Karp and Claire Kenyon, Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1994.
Multilayer neural networks: one or two hidden layers? , G. Brightwell, C. Kenyon and H. Paugam-Moisy, NIPS '96.
Error Resilient DNA Computation, Richard Karp, Claire Kenyon and Orli Waarts, Seventh Annual ACM-SIAM Symposium On Discrete Algorithms (SODA), 458-467, 1996.
Best-Fit Bin-Packing with Random Order, Claire Kenyon, Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 359-364, 1996.
Scheduling Multiprocessor Tasks on Dedicated Processors, A.K. Amoura, E.Bampis, C.Kenyon and Y. Manoussakis, European Symposium on Algorithms (ESA), 1-10, 1997. Algorithmica.
Broadcasting on trees and the Ising model. . Will Evans, Claire Kenyon, Yuval Peres and Leonard Schulman. Annals of applied probability, Vol 10, No. 2, May 2000, 410-433.