Claire Mathieu's Publications
2008
Katriel, I., Kenyon-Mathieu, C., and Upfal, E. Commitment under uncertainity: Two-stage stochastic matching problems. Theoretical Computer Science 408 (2008), 213-223.
2007
Borradaile, G., Kenyon-Mathieu, C., and Klein, P. A Polynomial-Time Approximation Scheme for Steiner Tree in Planar Graphs. In ACM-SIAM Symposium on Discrete Algorithms (New Orleans, Jan. 2007), ACM-SIAM.
de la Vega, W. F., and Kenyon-Mathieu, C. Linear Programming Relaxations of Maxcut. ACM-SIAM, ACM-SIAM Symposium on Discrete Algorithms.
Katriel, I., Kenyon-Mathieu, C., and Upfal, E. Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems. ICALP 2007, pp. 171-182.
Kenyon-Mathieu, C., and Schudy, W. How to rank with few errors. In ACM STOC 2007 (2007), pp. 95-103.
2006
Chrobak, M., and Kenyon-Mathieu, C. Competitiveness via Doubling. ACM SIGACT News (Dec. 2006). [ pdf ]
Das, A., and Kenyon, C. On hierarchical diameter-clustering, and the supplier problems. In Fourth Workshop on Approximation and Online Algorithms (Zurich, Sept. 2006), Springer Verlag, Lecture Notes in Computer Science. [ pdf ]
Chrobak, M., Kenyon, C., Noga, J., and Young, N. E. Online medians via online bribery. In LATIN 2006: Theoretical Informatics (Valdivia, Chile, Mar. 2006), J. R. Correa, A. Hevia, and M. Kiwi, Eds., pp. 311-322.
Bansal, N., Correa, J. R., Kenyon, C., and Sviridenko, M. Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes. Mathematics of Operations Research 31, 1 (Feb. 2006), 31-49.
Barbay, J., and Kenyon, C. Alternation and Redundancy Analysis of the Intersection Problem. ACM Transactions on Algorithms (2006).
Chroback, M., Kenyon, C., and Young, N. The Reverse Greedy Algorithm for the Metric K-Median Problem. Information Processing Letters, 2 (Jan. 2006), 68-72. [ pdf ]
Csirik, J., Johnson, D. S., Kenyon, C., Orlin, J. B., Shor, P. W., and Weber, R. R. On the Sum-of-Squares Algorithm for Bin Packing. Journal of the ACM 53, 1 (2006), 1-65. [ pdf ]
Kenyon, C., and Sellmann, M. Uncertainty/Time Trade-Offs for Linear and Integer Programming. In Proceedings of the Third International Conference on Integration of AI and OR Techniques (CP-AI-OR) (2006), Springer Verlag, pp. 126-138.
2005
Chrobak, M., Kenyon, C., and Young, N. The Reverse Greedy Algorithm for the Metric K-Median Problem. In COCOON 2005 (2005), pp. 654-660. [ pdf ]
Guruswami, V., Hartline, J., Karlin, A., Kempe, D., Kenyon, C., and McSherry, F. On Profit-Maximizing Envy-Free Pricing. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Descrete Algorithms (SODA) (2005), pp. 1164-1173. [ pdf ]
2004
Kenyon, C., Rabani, Y., and Sinclair, A. Low Distortion Maps Between Point Sets. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing (STOC) (May 2004), pp. 272-280. [ pdf ]
Kenyon, C., and Kutin, S. Sensitivity, block sensitivity and l-block sensitivity of Boolean functions. Information and Computation 189 (Feb. 2004), 43-53. [ pdf ]
Correa, J., and Kenyon, C. Asymptotic Approximation Schemes for Two-Dimensional Packing. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2004), pp. 186-195. [ pdf ]
de la Vega, W. F., Karpinski, M., and Kenyon, C. Approximation Schemes for Metric Bisection and Partitioning. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2004), pp. 506-515. [ pdf ]
2003
Karp, R. M., and Kenyon, C. A Gambling Game and Analysis of Adaptive Randomized Rounding. In Proceedings of the 7th International Workshop on Randimization and Approximation Techniques in Computer Science (RANDOM) (Aug. 2003), S. Arora, K. Jensen, D. Rolim, and A. Sahai, Eds., pp. 329-340. [ pdf ]
Barbay, J., and Kenyon, C. Deterministic Algorithm for the t-Threshold Set Problem. In Proceedings of the 14th Annual International Symposium on Algorithms and Computataion (ISAAC) (2003), T. Ibaraki, N. Katoh, and K. Ono, Eds., pp. 575-584. [ pdf ]
Buchsbaum, A. L., Karloff, H., Kenyon, C., Reingold, N., and Thorup, M. OPT versus LOAD in Dynamic Storage Allocation. SIAM Journal on Computing 33, 3 (2003), 632-646. [ pdf ]
Buchsbaum, A. L., Karloff, H., Kenyon, C., Reingold, N., and Thorup, M. OPT versus LOAD in Dynamic Storage Allocation. In STOC '03: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (2003), ACM Press, pp. 556-564. [ pdf ]
Karlin, A. R., Kenyon, C., and Randall, D. Dynamic TCP Acknowledgement and Other Stories About e/(e-1). Algorithmica 36, 3 (2003), 209-224. [ pdf ]
Barbay, J., and Kenyon, C. Deterministic Algorithm for the t-Threshold Set Problem. In 14th Annual International Symposium on Algorithms and Computation (ISAAC) (2003), Springer Verlag. [ pdf ]
Kenyon, C., and Schabanel, N. The Data Broadcast Problem with Non-Uniform Transmission Times. Algorithmica 35, 2 (2003), 146-175. [ pdf ]
de la Vega, W. F., Karpinski, M., Kenyon, C., and Rabani, Y. Approximation Schemes for Clustering Problems. In Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC) (2003), pp. 50-58. [ pdf ]
2002
Amoura, A. K., Bampis, E., Kenyon, C., and Manoussakis, Y. Scheduling Multiprocessor Tasks on Dedicated Processors. Algorithmica 32, 2 (2002), 247-261. [ pdf ]
Barbay, J., and Kenyon, C. Adaptive Intersection and t-Threshold Problems. In Proceedings of Thirteenth Annul ACM-SIAM Symposium on Discrete Algorithms (SODA) (Jan. 2002), pp. 390-399. [ pdf ]
Golin, M. J., Kenyon, C., and Young, N. E. Huffman Coding with Unequal Letter Costs. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (STOC) (2002), pp. 785-791. [ pdf ]
Kenyon, C., and Mitzenmacher, M. Linear Waste of Best-Fit Bin Packing on Skewed Distributions. Random Structures and Algorithms 20 (2002), 441-464. [ pdf ]
2001
Karlin, A. R., Kenyon, C., and Randall, D. Dynamic TCP Acknowledgement and Other Stories about e/(e-1). In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC) (May 2001). [ pdf ]
Barbay, J., and Kenyon, C. On the Discrete Bak-Sneppen Model of Self-organized Criticality. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2001), pp. 928-933. [ pdf ]
Csirik, J., Johnson, D., and Kenyon, C. Better Approximation Algorithms for Bin Covering. In Proceedings of the Twelth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2001), pp. 557-566. [ pdf ]
Kenyon, C., Mossel, E., and Peres, Y. Glauber Dynamics on Trees and Hyperbolic Graphs. In 42nd IEEE Symposium on Foundations of Computer Science (FOCS '01) (2001), pp. 568-578. [ pdf ]
de la Vega, W. F., and Kenyon, C. A Randomized Approximation Scheme for Metric MAX-CUT. Journal of Computer and System Sciences (JCSS) 63, 4 (2001), 531-541. [ pdf ]
2000
Kenyon, C., and Mitzenmacher, M. Linear Waste of Best Fit Bin Packing on Skewed Distributions. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS) (Redondo Beach, CA, Nov. 2000), pp. 582-589. [ pdf ]
Kenyon, C., and Remila, E. A Near-optimal Solution to a Two-dimensional Cutting Stock Problem. Mathematics of Operations Research 25, 4 (Nov. 2000), 645-656. [ pdf ]
Csirik, J., Johnson, D. S., Kenyon, C., Orlin, J. B., Shor, P. W., and Weber, R. R. On the Sum-of-squares Algorithm for Bin Packing. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC) (May 2000). [ pdf ]
Evans, W., Kenyon, C., Peres, Y., and Schulmann, L. Broadcasting on Trees and the Ising Model. Annals of Applied Probability 10, 2 (May 2000), 410-433. [ pdf ]
Kenyon, C., Schabanel, N., and Young, N. Polynomial-time Approximation Scheme for Data Broadcast. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC) (May 2000), pp. 659-666. [ pdf ]
Afrati, F., Bampis, E., Kenyon, C., and Milis, I. A PTAS for the Average Weighted Completion Time Problem on Unrelated Machines. Journal of Scheduling - Special Issue on Approximation Algorithms 3, 6 (2000), 323-332. [ pdf ]
Afrati, F., Bampis, E., Fishkin, A. V., Jansen, K., and Kenyon, C. Scheduling to Minimize the Average Completion Time of Dedicated Tasks. In Proceedings of the Foundations of Software Technology and Theoretical Computer Science 2000 Conference (2000), pp. 454-464. [ pdf ]
1999
Afrati, F. N., Bampis, E., Chekuri, C., Karger, D. R., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Sartinutella, M., Stein, C., and Sviridenko, M. Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. In Proceedings of the 1999 Symposium on Foundations of Computer Science (FOCS) (plenary session) (New York, NY, Oct. 1999), pp. 32-44. [ pdf ]
Afrati, F. N., Bampis, E., Kenyon, C., and Milis, I. Scheduling on a Constant Number of Machines. In Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques (1999), pp. 281-287. [ pdf ]
Csirik, J., Johnson, D. S., Kenyon, C., Shor, P. W., and Weber, R. A Self-organizing Bin Packing Heuristic. In Proceedings of the Workshop on Algorithm Engineering and Experimentation (ALENEX 99) (1999), pp. 246-265. [ pdf ]
Ferreira, A., Kenyon, C., Rau-Chaplin, A., and Ubeda, S. d-Dimensional Range Search on Multicomputers. Algorithmica 24 (1999), 195-208. [ pdf ]
Karp, R., Kenyon, C., and Waarts, O. Error Resilient DNA Computation. Random Structures and Algorithms 15, 3-4 (1999), 450-466. [ pdf ]
Kenyon, C., and Schabanel, N. The Data Broadcast Problem with Non-Uniform Transmission Times. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (1999), pp. 547-556. [ pdf ]
1998
Kenyon, C., Rabani, Y., and Sinclair, A. Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing. Journal of Algorithms 27, 2 (1998), 218-235. [ pdf ]
Kenyon, C. Complexite Algorithmique. In Dictionnaire d'histoire et de philosophie des sciences. Presses Universitaires de France, 1998.
Kenyon, C., and Paugam-Moisy, H. Multilayer Neural Networks and Polyhedral Dichotomies. Annals of Mathematics and Artificial Intelligence 24 (1998), 115-128. [ pdf ]
de la Vega, W. F., and Kenyon, C. A Randomized Approximation Scheme for Metric MAX-CUT. In Proceedings of the Thirty-Ninth Annual IEEE Symposium on Foundations of Computer Science (FOCS) (1998), pp. 468-471. [ pdf ]
1997
Amoura, A. K., Bampis, E., Kenyon, C., and Manoussakis, Y. Scheduling Independent Multiprocessor Tasks. In Proceedings of the 5th Annual European Symposium (ESA 1997) (1997), Springer, pp. 1-12. [ pdf ]
Bajard, J.-C., Bouge, L., Kenyon, C., Muller, J.-M., and Robert, Y. Exercices d'algorithmique Oraux d'ENS Ouvrage Collectif-Coordination. Passeport pour l'informatique. International Thomson Publishing France, France, 1997.
Ferreira, A., Kenyon, C., Rau-Chaplin, A., and Ubeda, S. d-Dimensional Range Search on Multicomputers. In Proceedings of the 11th International Parallel Processing Symposium (IPPS) (1997), IEEE Computer Society Press, pp. 616-620. [ pdf ]
Louchard, G., Kenyon, C., and Schott, R. Data structures maxima. SIAM Journal on Computing 26, 4 (1997), 1006-1042. [ pdf ]
1996
Chaboud, T., and Kenyon, C. Planar Cayley Graphs with Regular Dual. International Journal of Algebra and Computation 6, 5 (1996), 553-561.
Karp, R. M., Kenyon, C., and Waarts, O. Error-Resilient DNA Computation. In SODA '96: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (1996), Society for Industrial and Applied Mathematics, pp. 458-467. [ pdf ]
Kenyon, C. Algorithmes de Pavages et de Mise en Boite, et Algorithmes avec Donnees Bruitees. PhD thesis, Universite Claude Bernard, 1996.
Kenyon, C., Randall, D., and Sinclair, A. Approximating the Number of Monomer-Dimer Coverings of a Lattice. Journal of Statistical Physics 83 (1996), 637-659. [ pdf ]
Kenyon, C., and Remila, E. Approximate Strip Packing. In Proceedings of the 37th Symposium on Foundations of Computer Science (FOCS) (1996), pp. 31-36. [ pdf ]
Kenyon, C. Best-Fit Bin-Packing with Random Order. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (1996), pp. 359-364. [ pdf ]
Kenyon, C., and Remila, E. Perfect Matchings on the Triangular Lattice. Discrete Mathematics 152 (1996), 191-210.
Kenyon, C., Rabani, Y., and Sinclair, A. Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (Atlanta, GA, 1996), Society for Industrial and Applied Mathematics, pp. 351-358. [ pdf ]
1995
Kenyon, C. Corrige du concours d'entree en Informatique, (Ecole Normale Superieure de Lyon). Revue de Mathematiques Speciales (Feb. 1995).
1994
Adler, M., Gemmel, P., Harchol, M., Karp, R., and Kenyon, C. Selection in the Presence of Noise: The Design of Playoff Systems. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (1994), Society for Industrial and Applied Mathematics, pp. 564-572. [ pdf ]
Dehne, F., Fabri, A., and Kenyon, C. Scalable and Architecture Independent Parallel Geometric Algorithms with High Probability Optimal Time. In Proceedings of the IEEE Symposium on Parallel and Distributed Processing (1994), IEEE, pp. 586-593. [ pdf ]
Kenyon, C., and King, V. On Boolean Decision Trees with Faulty Nodes. Random Structures et Algorithms 5, 3 (1994), 453-464.
1993
Bouge, L., Kenyon, C., Muller, J.-M., and Robert, Y. Exercises d'algorithmique. Ellipses, 1993.
Frigniaud, P., and Kenyon, C. Finding Target Subnetworks in Faulty Networks. Information Processing Letters 48, 6 (1993), 297-303.
Goddard, W., Kenyon, C., King, V., and Schulman, L. Optimal Randomized Algorithms for Local Sorting and Set Maxima. SIAM Journal on Computing 22, 2 (1993), 272-283. [ pdf ]
1992
Kenyon, C., and Kenyon, R. Comment paver des polygones avec des barres (Tiling Polygons with Bars). Comptes-rendu de l'Acadmie des Sciences 316, 12 (1993), 1319-1322.
Kenyon, C., and Kenyon, R. How to Take Short Cuts. Discrete and Computational Geometry 8 (1992), 251-264.
Kenyon, C., and Kenyon, R. Tiling a Polygon with Rectangles. In Proceedings of the 33rd Annual IEEE Symposium Foundamentals of Computer Science (FOCS) (1992), pp. 610-619. [ pdf ]
1988
Kenyon-Mathieu, C., and Vitter, J. S. Maximum queue size and hashing with lazy deletion. 597-619.
1990
Kenyon, C., and Yao, A. C. On Evaluating Boolean Functions with Unreliable Tests. International Journal of Foundations of Computer Science 1, 1 (1990), 1-10.
1989
Kenyon, C., and Lovasz, L. Algorithmic Discrete Mathematics. Tech. rep., Princeton University, 1989.
Kenyon, C., and King, V. Verifying Partial Orders. In Procceedings fo the 21st Annual ACM Symposium on Theory of Computing (STOC) (Seattle, Washington, 1989), ACM Press, pp. 367-374. [ pdf ]
| Page Owner: Claire Mathieu | Last Modified: Mon Oct 5 12:12:15 2009 |