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.