| 2000 | A (2 + epsilon)-approximation scheme for minimum domination on circle graphs. Mirela Damian-Iordache, Sriram V. Pemmaraju |
| 2000 | A 2+epsilon approximation algorithm for the Sanjeev Arora, George Karakostas |
| 2000 | A PTAS for the multiple knapsack problem. Chandra Chekuri, Sanjeev Khanna |
| 2000 | A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry. Ting Chen, Ming-Yang Kao, Matthew Tepel, John Rush, George M. Church |
| 2000 | A fast algorithm to generate unlabeled necklaces. Frank Ruskey, Joe Sawada |
| 2000 | A faster method for sampling independent sets. Mark Huber |
| 2000 | A lower bound for DLL algorithms for Pavel Pudlák, Russell Impagliazzo |
| 2000 | A new bound for the Carathéodory rank of the bases of a matroid. José Coelho de Pina, José Soares |
| 2000 | A point-placement strategy for conforming Delaunay tetrahedralization. Michael Murphy, David M. Mount, Carl W. Gable |
| 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 | A tree-edit-distance algorithm for comparing simple, closed shapes. Philip N. Klein, Srikanta Tirthapura, Daniel Sharvit, Benjamin B. Kimia |
| 2000 | Accurate approximations for Asian options. Donald Aingworth, Rajeev Motwani, Jeffrey D. Oldham |
| 2000 | Adaptive set intersections, unions, and differences. Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro |
| 2000 | Algorithmic strategies in combinatorial chemistry. Deborah Goldman, Sorin Istrail, Giuseppe Lancia, Antonio Piccolboni, Brian Walenz |
| 2000 | Algorithms for minimum volume enclosing simplex in R Yunhong Zhou, Subhash Suri |
| 2000 | Algorithms for optimizing production DNA sequencing. Éva Czabarka, Goran Konjevod, Madhav V. Marathe, Allon G. Percus, David C. Torney |
| 2000 | An algebraic method to compute a shortest path of local flips between two tilings. Eric Rémila |
| 2000 | An approximation algorithm for finding a long path in Hamiltonian graphs. Sundar Vishwanathan |
| 2000 | An approximation algorithm for the covering Steiner problem. Goran Konjevod, R. Ravi |
| 2000 | An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract). Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum, Michael Mitzenmacher |
| 2000 | An optimal algorithm for hyperplane depth in the plane. Stefan Langerman, William L. Steiger |
| 2000 | Applying extra-resource analysis to load balancing. Mark Brehob, Eric Torng, Patchrawat Uthaisombut |
| 2000 | Approximate congruence in nearly linear time. Piotr Indyk, Suresh Venkatasubramanian |
| 2000 | Approximating the maximum quadratic assignment problem. Esther M. Arkin, Refael Hassin |
| 2000 | Approximation algorithms for data placement on parallel disks. Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, An Zhu |
| 2000 | Approximation algorithms for layered manufacturing. Pankaj K. Agarwal, Pavan K. Desikan |
| 2000 | Approximation algorithms for projective clustering. Pankaj K. Agarwal, Cecilia Magdalena Procopiuc |
| 2000 | Balancing Steiner trees and shortest path trees online. Ashish Goel, Kamesh Munagala |
| 2000 | Caching in networks (extended abstract). Friedhelm Meyer auf der Heide, Berthold Vöcking, Matthias Westermann |
| 2000 | Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma. Artur Czumaj, Christian Scheideler |
| 2000 | Coloring powers of planar graphs. Geir Agnarsson, Magnús M. Halldórsson |
| 2000 | Communication complexity of document exchange. Graham Cormode, Mike Paterson, Süleyman Cenk Sahinalp, Uzi Vishkin |
| 2000 | Commuting with delay prone buses. Mayur Datar, Abhiram G. Ranade |
| 2000 | Competitive tree-structured dictionaries. Michael T. Goodrich |
| 2000 | Computing contour trees in all dimensions. Hamish A. Carr, Jack Snoeyink, Ulrike Axen |
| 2000 | Computing the arrangement of curve segments: divide-and-conquer algorithms via sampling. Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos |
| 2000 | Computing the quartet distance between evolutionary trees. David Bryant, John Tsang, Paul E. Kearney, Ming Li |
| 2000 | Construction of visual secret sharing schemes with almost optimal contrast. Christian Kuhlmann, Hans Ulrich Simon |
| 2000 | Cooperative facility location games. Michel X. Goemans, Martin Skutella |
| 2000 | Cutting planes and the traveling salesman problem (abstract only). David L. Applegate, Robert E. Bixby, Vasek Chvátal, William J. Cook |
| 2000 | Deterministic broadcasting in unknown radio networks. Bogdan S. Chlebus, Leszek Gasieniec, Alan Gibbons, Andrzej Pelc, Wojciech Rytter |
| 2000 | Digraph minors and algorithms (abstract only). Robin Thomas |
| 2000 | Dimensionality reduction techniques for proximity problems. Piotr Indyk |
| 2000 | Directed network design with orientation constraints. Sanjeev Khanna, Joseph Naor, F. Bruce Shepherd |
| 2000 | Edge-disjoint paths in expander graphs. Alan M. Frieze |
| 2000 | Efficient bundle sorting. Yossi Matias, Eran Segal, Jeffrey Scott Vitter |
| 2000 | Efficient dynamic traitor tracing. Omer Berkman, Michal Parnas, Jirí Sgall |
| 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 | Escaping a grid by edge-disjoint paths. Wun-Tat Chan, Francis Y. L. Chin, Hing-Fung Ting |
| 2000 | Estimating DNA sequence entropy. J. Kevin Lanctôt, Ming Li, En-Hui Yang |
| 2000 | Evaluating the cylindricity of a nominally cylindrical point set. Olivier Devillers, Franco P. Preparata |
| 2000 | Even strongly universal hashing is pretty fast. Mikkel Thorup |
| 2000 | Exact and approximation algorithms for minimum-width cylindrical shells. Pankaj K. Agarwal, Boris Aronov, Micha Sharir |
| 2000 | Expected-case complexity of approximate nearest neighbor searching. Sunil Arya, Ho-Yam Addy Fu |
| 2000 | Fast concurrent access to parallel disks. Peter Sanders, Sebastian Egner, Jan H. M. Korst |
| 2000 | Fast practical solution of sorting by reversals. Alberto Caprara, Giuseppe Lancia, See-Kiong Ng |
| 2000 | Fast randomized algorithms for computing minimum {3, 4, 5, 6}-way cuts. Matthew S. Levine |
| 2000 | Faster algorithms for string matching with Amihood Amir, Moshe Lewenstein, Ely Porat |
| 2000 | Faster deterministic dictionaries. Rasmus Pagh |
| 2000 | Finding minimal triangulations of convex 3-polytopes is NP-hard. Alexander Below, Jesús A. De Loera, Jürgen Richter-Gebert |
| 2000 | Finding the closest lattice vector when it's unusually close. Philip N. Klein |
| 2000 | Finite-resolution hidden surface removal. Jeff Erickson |
| 2000 | Forcing relations for AND/OR precedence constraints. Rolf H. Möhring, Martin Skutella, Frederik Stork |
| 2000 | Generating adversaries for request-answer games. Todd Gormley, Nick Reingold, Eric Torng, Jeffery R. Westbrook |
| 2000 | Hamiltonicity and colorings of arrangement graphs. Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu |
| 2000 | Height in a digital search tree and the longest phrase of the Lempel-Ziv scheme. Charles Knessl, Wojciech Szpankowski |
| 2000 | Improved Steiner tree approximation in graphs. Gabriel Robins, Alexander Zelikovsky |
| 2000 | Improved approximation algorithms for MAX SAT. Takao Asano, David P. Williamson |
| 2000 | Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. Eran Halperin |
| 2000 | Improved bandwidth approximation for trees. Anupam Gupta |
| 2000 | Improved bounds on the sample complexity of learning. Yi Li, Philip M. Long, Aravind Srinivasan |
| 2000 | Improved classification via connectivity information. Andrei Z. Broder, Robert Krauthgamer, Michael Mitzenmacher |
| 2000 | Inplace run-length 2d compressed search. Amihood Amir, Gad M. Landau, Dina Sokol |
| 2000 | Instability of FIFO in session-oriented networks. Matthew Andrews |
| 2000 | Locally lifting the curse of dimensionality for nearest neighbor search (extended abstract). Peter N. Yianilos |
| 2000 | Maintaining hierarchical graph views. Adam L. Buchsbaum, Jeffery R. Westbrook |
| 2000 | Min-Wise versus linear independence (extended abstract). Andrei Z. Broder, Uriel Feige |
| 2000 | Minimizing maximum response time in scheduling broadcasts. Yair Bartal, S. Muthukrishnan |
| 2000 | Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks. S. Thomas McCormick, Akiyoshi Shioura |
| 2000 | Movement minimization in conveyor flow shop processing. Wolfgang Espelage, Egon Wanke |
| 2000 | Nearly optimal computations with structured matrices. Victor Y. Pan |
| 2000 | New and improved algorithms for minsum shop scheduling. Maurice Queyranne, Maxim Sviridenko |
| 2000 | Off-line admission control for general scheduling problems. Cynthia A. Phillips, R. N. Uma, Joel Wein |
| 2000 | On Heilbronn's problem in higher dimension. Hanno Lefmann |
| 2000 | On deciding stability of scheduling policies in queueing systems. David Gamarnik |
| 2000 | On external memory graph traversal. Adam L. Buchsbaum, Michael H. Goldwasser, Suresh Venkatasubramanian, Jeffery R. Westbrook |
| 2000 | On incremental rendering of silhouette maps of polyhedral scene. Alon Efrat, Leonidas J. Guibas, Olaf A. Hall-Holt, Li Zhang |
| 2000 | On local search and placement of meters in networks. Samir Khuller, Randeep Bhatia, Robert Pless |
| 2000 | On permutations with limited independence. Toshiya Itoh, Yoshinori Takei, Jun Tarui |
| 2000 | On the complexity of bicoloring clique hypergraphs of graphs (extended abstract). Jan Kratochvíl, Zsolt Tuza |
| 2000 | On the red-blue set cover problem. Robert D. Carr, Srinivas Doddi, Goran Konjevod, Madhav V. Marathe |
| 2000 | On the shared substring alignment problem. Gad M. Landau, Michal Ziv-Ukelson |
| 2000 | On the temporal HZY compression scheme. Z. Cohen, Yossi Matias, S. Muthukrishnan, Süleyman Cenk Sahinalp, Jacob Ziv |
| 2000 | Optimizing the sum of linear fractional functions and applications. Danny Z. Chen, Ovidiu Daescu, Yang Dai, Naoki Katoh, Xiaodong Wu, Jinhui Xu |
| 2000 | Orthogonal graph drawing with constraints. Markus Eiglsperger, Ulrich Fößmeier, Michael Kaufmann |
| 2000 | Pattern discovery on character sets and real-valued data: linear bound on irredundant motifs and an efficient polynomial time algorithm. Laxmi Parida, Isidore Rigoutsos, Aris Floratos, Daniel E. Platt, Yuan Gao |
| 2000 | Pattern matching in dynamic texts. Stephen Alstrup, Gerth Stølting Brodal, Theis Rauhe |
| 2000 | Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9-11, 2000, San Francisco, CA, USA. David B. Shmoys |
| 2000 | Random three-dimensional tilings of Aztec octahedra and tetrahedra: an extension of domino tilings. Dana Randall, Gary D. Yngve |
| 2000 | Randomized greedy hot-potato routing. Costas Busch, Maurice Herlihy, Roger Wattenhofer |
| 2000 | Real scaled matching. Amihood Amir, Ayelet Butman, Moshe Lewenstein |
| 2000 | Recognizing dart-free perfect graphs. Vasek Chvátal, Jean Fonlupt, L. Sun, Abdelhamid Zemirline |
| 2000 | Restructuring ordered binary trees. William S. Evans, David G. Kirkpatrick |
| 2000 | Scheduling a pipelined operator graph. Petra Schuurman, Gerhard J. Woeginger |
| 2000 | Scheduling to minimize average stretch without migration. Luca Becchetti, Stefano Leonardi, S. Muthukrishnan |
| 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 | Sharing one secret vs. sharing many secrets: tight bounds on the average improvement ratio. Giovanni Di Crescenzo |
| 2000 | Strengthening integrality gaps for capacitated network design and covering problems. Robert D. Carr, Lisa Fleischer, Vitus J. Leung, Cynthia A. Phillips |
| 2000 | Strictly non-blocking WDM cross-connects. April Rasala, Gordon T. Wilfong |
| 2000 | Strong bias of group generators: an obstacle to the "product replacement algorithm". László Babai, Igor Pak |
| 2000 | Sweeping simple polygons with a chain of guards. Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, David C. Lin, Joseph S. B. Mitchell, T. M. Murali |
| 2000 | TSP-based curve reconstruction in polynomial time. Ernst Althaus, Kurt Mehlhorn |
| 2000 | Testing and spot-checking of data streams (extended abstract). Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan |
| 2000 | The complexity of counting graph homomorphisms (extended abstract). Martin E. Dyer, Catherine S. Greenhill |
| 2000 | The effects of temporary sessions on network performance. Matthew Andrews, Lisa Zhang |
| 2000 | The interlace polynomial: a new graph polynomial. Richard Arratia, Béla Bollobás, Gregory B. Sorkin |
| 2000 | The prize collecting Steiner tree problem: theory and practice. David S. Johnson, Maria Minkoff, Steven Phillips |
| 2000 | The rectilinear Steiner arborescence problem is NP-complete. Weiping Shi, Chen Su |
| 2000 | The whole genome assembly of Drosophila. Gene Myers |
| 2000 | Towards a 4/3 approximation for the asymmetric traveling salesman problem. Robert D. Carr, Santosh S. Vempala, Jacques Mandler |
| 2000 | Towards a theory of cache-efficient algorithms. Sandeep Sen, Siddhartha Chatterjee |
| 2000 | Typical random 3-SAT formulae and the satisfiability threshold. Olivier Dubois, Yacine Boufkhad, Jacques Mandler |
| 2000 | Watermarking maps: hiding information in structured data. Sanjeev Khanna, Francis Zane |
| 2000 | Weakly chordal graph algorithms via handles. Ryan Hayward, Jeremy P. Spinrad, R. Sritharan |
| 2000 | Word encoding tree connectivity works. Stephen Alstrup, Jens P. Secher, Mikkel Thorup |
| 2000 | epsilon-Approximate linear programs: new bounds and computation. Daniel Bienstock |