| 2001 | Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract). | Daniel Kobler, Udi Rotics |
| 2001 | Shape matching using edit-distance: an implementation. | Philip N. Klein, Thomas B. Sebastian, Benjamin B. Kimia |
| 2001 | Loss-bounded analysis for differentiated services. | Alexander Kesselman, Yishay Mansour |
| 2001 | Learning Markov networks: maximum bounded tree-width graphs. | David R. Karger, Nathan Srebro |
| 2001 | Static and kinetic geometric spanners with applications. | Menelaos I. Karavelas, Leonidas J. Guibas |
| 2001 | Faster kinetic heaps and their use in broadcast scheduling. | Haim Kaplan, Robert Endre Tarjan, Kostas Tsioutsiouliklis |
| 2001 | Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining. | Katherine St. John, Tandy J. Warnow, Bernard M. E. Moret, Lisa Vawter |
| 2001 | A polynomial time recognition algorithm for probe interval graphs. | Julie L. Johnson, Jeremy P. Spinrad |
| 2001 | Adversarial models in evolutionary game dynamics. | Gabriel Istrate, Madhav V. Marathe, S. S. Ravi |
| 2001 | Alternatives to splay trees with O(log n) worst-case access times. | John Iacono |
| 2001 | Optimal planar point location. | John Iacono |
| 2001 | Geometric permutations of high dimensional spheres. | Yingping Huang, Jinhui Xu, Danny Z. Chen |
| 2001 | Simplified kinetic connectivity for rectangles and hypercubes. | John Hershberger, Subhash Suri |
| 2001 | Online point location in planar arrangements and its applications. | Sariel Har-Peled, Micha Sharir |
| 2001 | Improved fast integer sorting in linear space. | Yijie Han |
| 2001 | Combinatorial approximation algorithms for the maximum directed cut problem. | Eran Halperin, Uri Zwick |
| 2001 | Coloring k-colorable graphs using smaller palettes. | Eran Halperin, Ram Nathaniel, Uri Zwick |
| 2001 | On algorithms for efficient data migration. | Joseph Hall, Jason D. Hartline, Anna R. Karlin, Jared Saia, John Wilkes |
| 2001 | Inserting an edge into a planar graph. | Carsten Gutwenger, Petra Mutzel, Ren Weiskircher |
| 2001 | Steiner points in tree metrics don't (really) help. | Anupam Gupta |
| 2001 | Improved algorithms for fault tolerant facility location. | Sudipto Guha, Adam Meyerson, Kamesh Munagala |
| 2001 | Competitive auctions and digital goods. | Andrew V. Goldberg, Jason D. Hartline, Andrew Wright |
| 2001 | Distributed admission control, scheduling, and routing with stale information. | Ashish Goel, Adam Meyerson, Serge A. Plotkin |
| 2001 | Approximate majorization and fair online load balancing. | Ashish Goel, Adam Meyerson, Serge A. Plotkin |
| 2001 | Reductions among high dimensional proximity problems. | Ashish Goel, Piotr Indyk, Kasturi R. Varadarajan |