| 2000 | Towards a 4/3 approximation for the asymmetric traveling salesman problem. | Robert D. Carr, Santosh S. Vempala, Jacques Mandler |
| 2000 | Computing contour trees in all dimensions. | Hamish A. Carr, Jack Snoeyink, Ulrike Axen |
| 2000 | Strengthening integrality gaps for capacitated network design and covering problems. | Robert D. Carr, Lisa Fleischer, Vitus J. Leung, Cynthia A. Phillips |
| 2000 | On the red-blue set cover problem. | Robert D. Carr, Srinivas Doddi, Goran Konjevod, Madhav V. Marathe |
| 2000 | Fast practical solution of sorting by reversals. | Alberto Caprara, Giuseppe Lancia, See-Kiong Ng |
| 2000 | Randomized greedy hot-potato routing. | Costas Busch, Maurice Herlihy, Roger Wattenhofer |
| 2000 | Maintaining hierarchical graph views. | Adam L. Buchsbaum, Jeffery R. Westbrook |
| 2000 | On external memory graph traversal. | Adam L. Buchsbaum, Michael H. Goldwasser, Suresh Venkatasubramanian, Jeffery R. Westbrook |
| 2000 | Engineering the compression of massive tables: an experimental approach. | Adam L. Buchsbaum, Donald F. Caldwell, Kenneth Ward Church, Glenn S. Fowler, S. Muthukrishnan |
| 2000 | Computing the quartet distance between evolutionary trees. | David Bryant, John Tsang, Paul E. Kearney, Ming Li |
| 2000 | Selective mapping: a discrete optimization approach to selecting a population subset for use in a high-density genetic mapping project. | Daniel G. Brown, Todd J. Vision, Steven D. Tanksley |
| 2000 | Improved classification via connectivity information. | Andrei Z. Broder, Robert Krauthgamer, Michael Mitzenmacher |
| 2000 | Min-Wise versus linear independence (extended abstract). | Andrei Z. Broder, Uriel Feige |
| 2000 | Applying extra-resource analysis to load balancing. | Mark Brehob, Eric Torng, Patchrawat Uthaisombut |
| 2000 | epsilon-Approximate linear programs: new bounds and computation. | Daniel Bienstock |
| 2000 | A practical algorithm for recovering the best supported edges of an evolutionary tree (extended abstract). | Vincent Berry, David Bryant, Tao Jiang, Paul E. Kearney, Ming Li, Todd Wareham, Haoyong Zhang |
| 2000 | Efficient dynamic traitor tracing. | Omer Berkman, Michal Parnas, Jir Sgall |
| 2000 | Finding minimal triangulations of convex 3-polytopes is NP-hard. | Alexander Below, Jess A. De Loera, Jrgen Richter-Gebert |
| 2000 | Scheduling to minimize average stretch without migration. | Luca Becchetti, Stefano Leonardi, S. Muthukrishnan |
| 2000 | Minimizing maximum response time in scheduling broadcasts. | Yair Bartal, S. Muthukrishnan |
| 2000 | Strong bias of group generators: an obstacle to the "product replacement algorithm". | Lszl Babai, Igor Pak |
| 2000 | Improved approximation algorithms for MAX SAT. | Takao Asano, David P. Williamson |
| 2000 | Expected-case complexity of approximate nearest neighbor searching. | Sunil Arya, Ho-Yam Addy Fu |
| 2000 | The interlace polynomial: a new graph polynomial. | Richard Arratia, Bla Bollobs, Gregory B. Sorkin |
| 2000 | A 2+epsilon approximation algorithm for the | Sanjeev Arora, George Karakostas |