Claire Mathieu's online publications

Submitted

• Correlation Clustering with Noisy Input, Claire Mathieu and Warren Schudy, submitted.
• A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing, Aparna Das and Claire Mathieu, submitted.
• Indecomposable permutations with a given number of cycles, Robert Cori and Claire Mathieu, submitted.
• Sherali-Adams relaxations of the matching polytope, Claire Mathieu and Alistair Sinclair, to be submitted.

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.