Claire Kenyon's online publications

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, to appear.
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, to appear.
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, to appear.
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, Journal version to appear in 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 submitted to JACM.
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, to appear. 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. ( Postcript file)
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. ( Postcript file)
Approximate Strip-Packing , Claire Kenyon and Eric Remila, Thirty-Seventh Annual Symposium on Foundations of Computer Science (FOCS), 31-36, 1996. To appear in Mathematics of Operations Research.( Postcript )
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.
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. To appear in 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.