| 2001 | A cell probe lower bound for dynamic nearest-neighbor searching. Stephen Alstrup, Thore Husfeldt, Theis Rauhe |
| 2001 | A deterministic algorithm for the cost-distance problem. Chandra Chekuri, Sanjeev Khanna, Joseph Naor |
| 2001 | A faster implementation of the Goemans-Williamson clustering algorithm. Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat |
| 2001 | A linear lower bound on index size for text retrieval. Erik D. Demaine, Alejandro López-Ortiz |
| 2001 | A new constructive root bound for algebraic expressions. Chen Li, Chee-Keng Yap |
| 2001 | A polynomial time recognition algorithm for probe interval graphs. Julie L. Johnson, Jeremy P. Spinrad |
| 2001 | A probabilistic analysis of a greedy algorithm arising from computational biology. Daniel G. Brown |
| 2001 | A simple entropy-based algorithm for planar point location. Sunil Arya, Theocharis Malamatos, David M. Mount |
| 2001 | Absolute convergence: true trees from short sequences. Tandy J. Warnow, Bernard M. E. Moret, Katherine St. John |
| 2001 | Adversarial models in evolutionary game dynamics. Gabriel Istrate, Madhav V. Marathe, S. S. Ravi |
| 2001 | Algorithms for facility location problems with outliers. Moses Charikar, Samir Khuller, David M. Mount, Giri Narasimhan |
| 2001 | Alternatives to splay trees with O(log n) worst-case access times. John Iacono |
| 2001 | An efficient algorithm for the configuration problem of dominance graphs. Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, Sven Thiel |
| 2001 | An experimental study of an opportunistic index. Paolo Ferragina, Giovanni Manzini |
| 2001 | Approximate majorization and fair online load balancing. Ashish Goel, Adam Meyerson, Serge A. Plotkin |
| 2001 | Approximate subset matching with Don't Cares. Amihood Amir, Ely Porat, Moshe Lewenstein |
| 2001 | Approximately covering by cycles in planar graphs. Dieter Rautenbach, Bruce A. Reed |
| 2001 | Approximating coloring and maximum independent sets in 3-uniform hypergraphs. Michael Krivelevich, Ram Nathaniel, Benny Sudakov |
| 2001 | Approximating the minimum strongly connected subgraph via a matching lower bound. Adrian Vetta |
| 2001 | Approximation algorithms for TSP with neighborhoods in the plane. Adrian Dumitrescu, Joseph S. B. Mitchell |
| 2001 | Approximation algorithms for data placement in arbitrary networks. Ivan D. Baev, Rajmohan Rajaraman |
| 2001 | Approximation algorithms for extensible bin packing. Edward G. Coffman Jr., George S. Lueker |
| 2001 | Approximation algorithms for the 0-extension problem. Gruia Calinescu, Howard J. Karloff, Yuval Rabani |
| 2001 | Approximation algorithms for the metric labeling problem via a new linear programming formulation. Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin |
| 2001 | Approximation for minimum triangulation of convex polyhedra. Francis Y. L. Chin, Stanley P. Y. Fung, Cao An Wang |
| 2001 | Assigning chain-like tasks to a chain-like network. Gerhard J. Woeginger |
| 2001 | Better approximation algorithms for bin covering. János Csirik, David S. Johnson, Claire Kenyon |
| 2001 | Can entropy characterize performance of online algorithms?. Gopal Pandurangan, Eli Upfal |
| 2001 | Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width. Johann A. Makowsky |
| 2001 | Coloring k-colorable graphs using smaller palettes. Eran Halperin, Ram Nathaniel, Uri Zwick |
| 2001 | Combinatorial approximation algorithms for the maximum directed cut problem. Eran Halperin, Uri Zwick |
| 2001 | Compact labeling schemes for ancestor queries. Serge Abiteboul, Haim Kaplan, Tova Milo |
| 2001 | Competitive auctions and digital goods. Andrew V. Goldberg, Jason D. Hartline, Andrew Wright |
| 2001 | Competitive on-line stream merging algorithms for media-on-demand. Amotz Bar-Noy, Richard E. Ladner |
| 2001 | Computing optimal alpha-fat and alpha-small decompositions. Mirela Damian-Iordache, Sriram V. Pemmaraju |
| 2001 | Computing the depth of a flat. Marshall W. Bern |
| 2001 | Constructing pseudo-random permutations with a prescribed structure. Moni Naor, Omer Reingold |
| 2001 | Constructing worst case instances for semidefinite programming based approximation algorithms. Noga Alon, Benny Sudakov, Uri Zwick |
| 2001 | Distance labeling in graphs. Cyril Gavoille, David Peleg, Stephane Perennes, Ran Raz |
| 2001 | Distributed admission control, scheduling, and routing with stale information. Ashish Goel, Adam Meyerson, Serge A. Plotkin |
| 2001 | Distribution sort with randomizing cycle. Jeffrey Scott Vitter, David A. Hutchinson |
| 2001 | Domatic partitions and the Lovász local lemma. Aravind Srinivasan |
| 2001 | Dynamic skin triangulation. Ho-Lun Cheng, Tamal K. Dey, Herbert Edelsbrunner, John Sullivan |
| 2001 | Dynamic string searching. Arne Andersson, Mikkel Thorup |
| 2001 | Efficient oblivious transfer protocols. Moni Naor, Benny Pinkas |
| 2001 | Entropy-preserving cuttings and space-efficient planar point location. Sunil Arya, Theocharis Malamatos, David M. Mount |
| 2001 | Equitable colorings extend Chernoff-Hoeffding bounds. Sriram V. Pemmaraju |
| 2001 | External memory BFS on undirected graphs with bounded degree. Ulrich Meyer |
| 2001 | Fast approximation of centrality. David Eppstein, Joseph Wang |
| 2001 | Fast distributed graph coloring with O(Delta) colors. Gianluca De Marco, Andrzej Pelc |
| 2001 | Fast implementation of depth contours using topological sweep. Kim Miller, Suneeta Ramaswami, Peter J. Rousseeuw, Joan Antoni Sellarès, Diane L. Souvaine, Ileana Streinu, Anja Struyf |
| 2001 | Faster kinetic heaps and their use in broadcast scheduling. Haim Kaplan, Robert Endre Tarjan, Kostas Tsioutsiouliklis |
| 2001 | Finding least common ancestors in directed acyclic graphs. Michael A. Bender, Giridhar Pemmasani, Steven Skiena, Pavel Sumazin |
| 2001 | Game theory, algorithms, and the Internet. Christos H. Papadimitriou |
| 2001 | Generating well-shaped Delaunay meshed in 3D. Xiang-Yang Li, Shang-Hua Teng |
| 2001 | Geometric permutations of high dimensional spheres. Yingping Huang, Jinhui Xu, Danny Z. Chen |
| 2001 | Gossip is synteny: incomplete gossip and an exact algorithm for syntenic distance. David Liben-Nowell |
| 2001 | Guessing secrets. Fan R. K. Chung, Ronald L. Graham, Frank Thomson Leighton |
| 2001 | Hill-climbing finds random planted bisections. Ted Carson, Russell Impagliazzo |
| 2001 | I/O-efficient algorithms for graphs of bounded treewidth. Anil Maheshwari, Norbert Zeh |
| 2001 | IMproved results for route planning in stochastic transportation. Justin A. Boyan, Michael Mitzenmacher |
| 2001 | Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction. David Eppstein |
| 2001 | Improved algorithms for fault tolerant facility location. Sudipto Guha, Adam Meyerson, Kamesh Munagala |
| 2001 | Improved approximation algorithms for rectangle tiling and packing. Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan, Suneeta Ramaswami |
| 2001 | Improved fast integer sorting in linear space. Yijie Han |
| 2001 | Inserting an edge into a planar graph. Carsten Gutwenger, Petra Mutzel, René Weiskircher |
| 2001 | Internet packet filter management and rectangle geometry. David Eppstein, S. Muthukrishnan |
| 2001 | K-pair delay constrained minimum cost routing in undirected networks. Guangting Chen, Guoliang Xue |
| 2001 | Lattice approximation and linear discrepency of totally unimodular matrices. Benjamin Doerr |
| 2001 | Learning Markov networks: maximum bounded tree-width graphs. David R. Karger, Nathan Srebro |
| 2001 | Linear reductions of maximum matching. Therese Biedl |
| 2001 | Loss-bounded analysis for differentiated services. Alexander Kesselman, Yishay Mansour |
| 2001 | Maintaining approximate extent measures of moving points. Pankaj K. Agarwal, Sariel Har-Peled |
| 2001 | Making data structures confluently persistent. Amos Fiat, Haim Kaplan |
| 2001 | Morphing between polylines. Alon Efrat, Sariel Har-Peled, Leonidas J. Guibas, T. M. Murali |
| 2001 | New approaches to covering and packing problems. Aravind Srinivasan |
| 2001 | On algorithms for efficient data migration. Joseph Hall, Jason D. Hartline, Anna R. Karlin, Jared Saia, John Wilkes |
| 2001 | On approximating the achromatic number. Guy Kortsarz, Robert Krauthgamer |
| 2001 | On binary searching with non-uniform costs. Eduardo Sany Laber, Ruy Luiz Milidiú, Artur Alves Pessoa |
| 2001 | On polynomial approximation to the shortest lattice vector length. Ravi Kumar, D. Sivakumar |
| 2001 | On the discrete Bak-Sneppen model of self-organized criticality. Jérémy Barbay, Claire Kenyon |
| 2001 | On the midpath tree conjuncture: a counter-example. Rahul Shah, Martin Farach-Colton |
| 2001 | On universally easy classes for NP-complete problems. Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro |
| 2001 | On validating planar worlds. Vida Dujmovic, Sue Whitesides |
| 2001 | On-line restricted caching. Mark Brehob, Richard J. Enbody, Eric Torng, Stephen Wagner |
| 2001 | Online point location in planar arrangements and its applications. Sariel Har-Peled, Micha Sharir |
| 2001 | Optimal constrained graph exploration. Christian A. Duncan, Stephen G. Kobourov, V. S. Anil Kumar |
| 2001 | Optimal covering tours with turn costs. Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia |
| 2001 | Optimal planar point location. John Iacono |
| 2001 | Orderly spanning trees with applications to graph encoding and graph drawing. Yi-Ting Chiang, Ching-Chi Lin, Hsueh-I Lu |
| 2001 | Overlap matching. Amihood Amir, Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat |
| 2001 | Parallel processor scheduling with delay constraints. Daniel W. Engels, Jon Feldman, David R. Karger, Matthias Ruhl |
| 2001 | Pattern matching for sets of segments. Alon Efrat, Piotr Indyk, Suresh Venkatasubramanian |
| 2001 | Performance guarentee for online deadline scheduling in the presence of overload. Tak Wah Lam, Kar-Keung To |
| 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 | Polygonal path approximation with angle constraints. Danny Z. Chen, Ovidiu Daescu, John Hershberger, Peter M. Kogge, Jack Snoeyink |
| 2001 | Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract). Daniel Kobler, Udi Rotics |
| 2001 | Polynomial-time approximation schemes for geometric graphs. Thomas Erlebach, Klaus Jansen, Eike Seidel |
| 2001 | Practical approximation algorithms for zero- and bounded-skew trees. Alexander Zelikovsky, Ion I. Mandoiu |
| 2001 | Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA. S. Rao Kosaraju |
| 2001 | Random lifts of graphs. Alon Amit, Nathan Linial, Jirí Matousek, Eyal Rozenman |
| 2001 | Randomizing combinatorial algorithms for linear programming when the dimension is moderately high. Marco Pellegrini |
| 2001 | Reconciling simplicity and realism in parallel disk models. Peter Sanders |
| 2001 | Reconstructing a collection of curves with corners and endpoints. Stefan Funke, Edgar A. Ramos |
| 2001 | Reductions among high dimensional proximity problems. Ashish Goel, Piotr Indyk, Kasturi R. Varadarajan |
| 2001 | Representing dynamic binary trees succinctly. J. Ian Munro, Venkatesh Raman, Adam J. Storm |
| 2001 | Robust algorithms for restricted domains. Vijay Raghavan, Jeremy P. Spinrad |
| 2001 | Scheduling precedence-constrained jobs with stochastic processing times on parallel machines. Martin Skutella, Marc Uetz |
| 2001 | Selective families, superimposed codes, and broadcasting on unknown radio networks. Andrea E. F. Clementi, Angelo Monti, Riccardo Silvestri |
| 2001 | Shape matching using edit-distance: an implementation. Philip N. Klein, Thomas B. Sebastian, Benjamin B. Kimia |
| 2001 | Shape sensitive geometric permutations. Yunhong Zhou, Subhash Suri |
| 2001 | Simplified kinetic connectivity for rectangles and hypercubes. John Hershberger, Subhash Suri |
| 2001 | Single-source shortest-paths on arbitrary directed graphs in linear average-case time. Ulrich Meyer |
| 2001 | Soft kinetic data structures. Artur Czumaj, Christian Sohler |
| 2001 | Stability preserving transformations: packet routing networks with edge capacities and speeds. Allan Borodin, Rafail Ostrovsky, Yuval Rabani |
| 2001 | Static and kinetic geometric spanners with applications. Menelaos I. Karavelas, Leonidas J. Guibas |
| 2001 | Steiner points in tree metrics don't (really) help. Anupam Gupta |
| 2001 | Sublinear time approximate clustering. Nina Mishra, Daniel Oblinger, Leonard Pitt |
| 2001 | Testing graphs for colorable properties. Eldar Fischer |
| 2001 | The diameter of random massive graphs. Linyuan Lu |
| 2001 | The inverse nearest neighbor problem with astrophysical applications. Richard J. Anderson, Brian Tjaden |
| 2001 | The phase transition in 1-in-k SAT and NAE 3-SAT. Dimitris Achlioptas, Arthur D. Chtcherba, Gabriel Istrate, Cristopher Moore |
| 2001 | The probabilistic relationship between the assignment and asymmetric traveling salesman problems. Alan M. Frieze, Gregory B. Sorkin |
| 2001 | Towards understanding the predictability of stock markets from the perspective of computational complexity. James Aspnes, David F. Fischer, Michael J. Fischer, Ming-Yang Kao, Alok Kumar |
| 2001 | Tree packing and approximating k-cuts. Joseph Naor, Yuval Rabani |
| 2001 | Universal configurations in light-flipping games. Yevgeniy Dodis, Peter Winkler |
| 2001 | Web caching using access statistics. Adam Meyerson, Kamesh Munagala, Serge A. Plotkin |
| 2001 | Which formulae shrink under random restrictions? Hana Chockler, Uri Zwick |
| 2001 | Worst case constant time priority queue. Andrej Brodnik, Svante Carlsson, Johan Karlsson, J. Ian Munro |