| 2000 | An approximation algorithm for the covering Steiner problem. | Goran Konjevod, R. Ravi |
| 2000 | Height in a digital search tree and the longest phrase of the Lempel-Ziv scheme. | Charles Knessl, Wojciech Szpankowski |
| 2000 | A tree-edit-distance algorithm for comparing simple, closed shapes. | Philip N. Klein, Srikanta Tirthapura, Daniel Sharvit, Benjamin B. Kimia |
| 2000 | Finding the closest lattice vector when it's unusually close. | Philip N. Klein |
| 2000 | On local search and placement of meters in networks. | Samir Khuller, Randeep Bhatia, Robert Pless |
| 2000 | Watermarking maps: hiding information in structured data. | Sanjeev Khanna, Francis Zane |
| 2000 | Directed network design with orientation constraints. | Sanjeev Khanna, Joseph Naor, F. Bruce Shepherd |
| 2000 | The prize collecting Steiner tree problem: theory and practice. | David S. Johnson, Maria Minkoff, Steven Phillips |
| 2000 | On permutations with limited independence. | Toshiya Itoh, Yoshinori Takei, Jun Tarui |
| 2000 | Approximate congruence in nearly linear time. | Piotr Indyk, Suresh Venkatasubramanian |
| 2000 | Dimensionality reduction techniques for proximity problems. | Piotr Indyk |
| 2000 | A faster method for sampling independent sets. | Mark Huber |
| 2000 | Caching in networks (extended abstract). | Friedhelm Meyer auf der Heide, Berthold Vcking, Matthias Westermann |
| 2000 | Weakly chordal graph algorithms via handles. | Ryan Hayward, Jeremy P. Spinrad, R. Sritharan |
| 2000 | Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. | Eran Halperin |
| 2000 | Improved bandwidth approximation for trees. | Anupam Gupta |
| 2000 | Generating adversaries for request-answer games. | Todd Gormley, Nick Reingold, Eric Torng, Jeffery R. Westbrook |
| 2000 | Competitive tree-structured dictionaries. | Michael T. Goodrich |
| 2000 | Approximation algorithms for data placement on parallel disks. | Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, An Zhu |
| 2000 | Algorithmic strategies in combinatorial chemistry. | Deborah Goldman, Sorin Istrail, Giuseppe Lancia, Antonio Piccolboni, Brian Walenz |
| 2000 | Cooperative facility location games. | Michel X. Goemans, Martin Skutella |
| 2000 | Balancing Steiner trees and shortest path trees online. | Ashish Goel, Kamesh Munagala |
| 2000 | On deciding stability of scheduling policies in queueing systems. | David Gamarnik |
| 2000 | Edge-disjoint paths in expander graphs. | Alan M. Frieze |
| 2000 | Hamiltonicity and colorings of arrangement graphs. | Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu |