Claire Mathieu's online publications
Submitted
2010
- Online Correlation Clustering, Claire Mathieu, Ocan Sankur and Warren Schudy, STACS 2010.
- Recognizing Well-Parenthesized Expressions
in the Streaming Model, Frederic Magniez, Claire Mathieu and Ashwin Nayak, ACM STOC 2010.
- The train delivery problem -- vehicle routing meets bin packing, Aparna Das, Claire Mathieu and Shay Mozes, WAOA 2010.
- Online Ranking for Tournament Graphs, Claire Mathieu and Adrian Vladu, WAOA 2010.
- Correlation Clustering with Noisy Input, Claire Mathieu and Warren Schudy, ACM SIAM SODA 2010.
- A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing, Aparna Das and Claire Mathieu, ACM SIAM SODA 2010.
2009
2008
-
Distortion Lower Bounds for Line Embeddings,
Claire Mathieu and Charalampos Papamanthou.
Information Processing Letters (IPL), 108, pages 175-178, 2008.
-
A polynomial-time approximation scheme for Euclidean Steiner forest.
Glencora Borradaile, Philip Klein, Claire Mathieu
Forty-Ninth Annual
Symposium on Foundations of Computer Science (FOCS), 2008, Philadelphia, Pennsylvania. (Revised version: fixed a bug from the proceedings version.)
-
Improved Approximation Algorithms for Budgeted Allocations.
Yossi Azar, Benjamin Birnbaum, Anna R. Karlin, Claire Mathieu and C. Thach Nguyen.
Automata, Languages and Programming (ICALP), 35th International
Colloquium, Pages 186-197, 2008.
-
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, pp. 70-76.
-
On-line bipartite matching made simple,
Benjamin Birnbaum and Claire Mathieu,
ACM SIGACT News, Volume 39 , Issue 1 (March 2008), pp. 80-87.
-
Alternation and Redundancy analysis of the Intersection Problem,
Jeremy Barbay and Claire Kenyon,
ACM Transactions on Algorithms (TALG), Volume 4 , Issue 1 (March 2008), 2008.
-
Yet another algorithm for dense max cut: go greedy, Claire Mathieu and Warren Schudy, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), Pages 176-182, 2008.
2007
-
Steiner tree in planar graphs: An O(n log n) approximation scheme with singly-exponential dependence on epsilon. Glencora Borradaile, Philip Klein, Claire Mathieu.
Workshop on Algorithms and Data Structures (WADS), 2007, Halifax, Nova Scotia, pages 275-286.
-
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, Pages: 262 - 271. Full version in: Harvard Business School Working Paper, No. 08-056, January 2008. Journal version is currently in submission to Economic Inquiry.
-
Commitment Under Uncertainty: Two-Stage Stochastic Matching
Problems. Irit Katriel, Claire Kenyon-Mathieu and Eli Upfal, Automata, Languages and Programming, 34th International
Colloquium, ICALP 2007, Pages 171-182.
Journal version in Theoretical Computer Science, in print as of August 2008.
-
How to rank with few errors (long version),
Claire Kenyon-Mathieu and Warren Schudy, short version, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (STOC), 2007, Pages: 95 - 103.
A much nicer, substantially simpler version is coming soon!
-
Linear Programming Relaxations of Maxcut.
Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu.
ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2007, Pages: 53 - 61 .
-
A polynomial-time approximation scheme for Steiner tree in planar graphs
Glencora Borradaile, Claire Kenyon-Mathieu, Philip Klein
SODA 2007, New Orleans, Louisiana, Pages: 1285 - 1294.
2006
-
Competitiveness via doubling. Marek Chrobak and Claire Kenyon-Mathieu.
ACM Sigact News, December 2006.
- 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.
- 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. Journal version:
Incremental Medians via Online Bidding, Marek Chrobak, Claire Kenyon, John Noga and Neal E. Young, Algorithmica, Springer New York, Volume 50, Number 4 / April, 2008, Pages 455-478
- 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.
-
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.
2005 and before
-
On Profit-Maximizing Envy-Free Pricing,
Venkat Guruswami, Jason Hartline, Anna Karlin, David Kempe, Claire Kenyon, and Frank McSherry, SODA 2005.
- 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.