| 2002 | (Incremental) priority algorithms. Allan Borodin, Morten N. Nielsen, Charles Rackoff |
| 2002 | 0/1 optimization and 0/1 primal separation are equivalent. Friedrich Eisenbrand, Giovanni Rinaldi, Paolo Ventura |
| 2002 | A comparison of labeling schemes for ancestor queries. Haim Kaplan, Tova Milo, Ronen Shabo |
| 2002 | A fully combinatorial algorithm for submodular function minimization. Satoru Iwata |
| 2002 | A locality-preserving cache-oblivious dynamic dictionary. Michael A. Bender, Ziyang Duan, John Iacono, Jing Wu |
| 2002 | A new algorithm for protein folding in the HP model. Alantha Newman |
| 2002 | A note on random 2-SAT with prescribed literal degrees. Colin Cooper, Alan M. Frieze, Gregory B. Sorkin |
| 2002 | A randomized online algorithm for bandwidth utilization. Sanjeev Arora, Bo Brinkman |
| 2002 | A sub-quadratic sequence alignment algorithm for unrestricted cost matrices. Maxime Crochemore, Gad M. Landau, Michal Ziv-Ukelson |
| 2002 | Adaptive intersection and t-threshold problems. Jérémy Barbay, Claire Kenyon |
| 2002 | Algorithms for quantified Boolean formulas. Ryan Williams |
| 2002 | An 8/13-approximation algorithm for the asymmetric maximum TSP. Markus Bläser |
| 2002 | An algorithm for counting maximum weighted independent sets and its applications. Vilhelm Dahllöf, Peter Jonsson |
| 2002 | An approximation algorithm for the group Steiner problem. Guy Even, Guy Kortsarz |
| 2002 | An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph. Harold N. Gabow |
| 2002 | An optimal (expected time) algorithm for minimizing lab costs in DNA sequencing. David Hart |
| 2002 | An optimal algorithm for checking regularity (extended abstract). Yoshiharu Kohayakawa, Vojtech Rödl, Lubos Thoma |
| 2002 | Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems. Béla Csaba, Marek Karpinski, Piotr Krysta |
| 2002 | Approximate distance oracles for geometric graphs. Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel H. M. Smid |
| 2002 | Approximating k-cuts via network strength. R. Ravi, Amitabh Sinha II |
| 2002 | Approximating minimum quartet inconsistency (abstract). Gianluca Della Vedova, Tao Jiang, Jing Li, Jianjun Wen |
| 2002 | Approximating minimum unsatisfiability of linear equations. Piotr Berman, Marek Karpinski |
| 2002 | Approximation algorithms for grammar-based compression. Eric Lehman, Abhi Shelat |
| 2002 | Balls and bins models with feedback. Eleni Drinea, Alan M. Frieze, Michael Mitzenmacher |
| 2002 | Binary space partitions for line segments with a limited number of directions. Csaba D. Tóth |
| 2002 | Broadcast scheduling: when fairness is fine. Jeff Edmonds, Kirk Pruhs |
| 2002 | Cache oblivious search trees via binary trees of small height. Gerth Stølting Brodal, Rolf Fagerberg, Riko Jacob |
| 2002 | Caching with expiration times. Parikshit Gopalan, Howard J. Karloff, Aranyak Mehta, Milena Mihail, Nisheeth K. Vishnoi |
| 2002 | Capacitated vertex covering with applications. Sudipto Guha, Refael Hassin, Samir Khuller, Einat Or |
| 2002 | Censorship resistant peer-to-peer content addressable networks. Amos Fiat, Jared Saia |
| 2002 | Center and diameter problems in plane triangulations and quadrangulations. Victor Chepoi, Feodor F. Dragan, Yann Vaxès |
| 2002 | Closest-point problems simplified on the RAM. Timothy M. Chan |
| 2002 | Competitive on-line switching policies. Amotz Bar-Noy, Ari Freund, Shimon Landa, Joseph Naor |
| 2002 | Computer assisted proof of optimal approximability results. Uri Zwick |
| 2002 | Computing shortest paths with comparisons and additions. Seth Pettie, Vijaya Ramachandran |
| 2002 | Computing the writhing number of a polygonal knot. Pankaj K. Agarwal, Herbert Edelsbrunner, Yusu Wang |
| 2002 | Construction of probe interval models. Ross M. McConnell, Jeremy P. Spinrad |
| 2002 | Covering shapes by ellipses. Alon Efrat, Frank Hoffmann, Christian Knauer, Klaus Kriegel, Günter Rote, Carola Wenk |
| 2002 | Delaunay triangulation programs on surface data. Sunghee Choi, Nina Amenta |
| 2002 | Dense point sets have sparse Delaunay triangulations: or "... but not too nasty". Jeff Erickson |
| 2002 | Derandomized dimensionality reduction with applications. Lars Engebretsen, Piotr Indyk, Ryan O'Donnell |
| 2002 | Edge dominating and hypomatchable sets. Ojas Parekh |
| 2002 | Efficient algorithms for document retrieval problems. S. Muthukrishnan |
| 2002 | Efficient pattern-matching with don't cares. Adam Kalai |
| 2002 | Efficient proper 2-coloring of almost disjoint hypergraphs. József Beck, Sachin Lodha |
| 2002 | Erratum: an approximation algorithm for minimum-cost vertex-connectivity problems. R. Ravi, David P. Williamson |
| 2002 | Existence theorems, lower bounds and algorithms for scheduling to meet two objectives. April Rasala, Clifford Stein, Eric Torng, Patchrawat Uthaisombut |
| 2002 | Expansion of product replacement graphs. Alexander Gamburd, Igor Pak |
| 2002 | Experimental analysis of simple, distributed vertex coloring algorithms. Irene Finocchi, Alessandro Panconesi, Riccardo Silvestri |
| 2002 | Explicit constructions of selectors and related combinatorial structures, with applications. Piotr Indyk |
| 2002 | Faster approximation schemes for fractional multicommodity flow problems. George Karakostas |
| 2002 | Flows over time with load-dependent transit times. Ekkehard Köhler, Martin Skutella |
| 2002 | Frugal path mechanisms. Aaron Archer, Éva Tardos |
| 2002 | Generalized clustering. Sudipto Guha, Kamesh Munagala |
| 2002 | Generating random factored numbers, easily. Adam Kalai |
| 2002 | Guessing secrets efficiently via list decoding. Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan |
| 2002 | Guessing secrets with inner product questions. Fan R. K. Chung, Ronald L. Graham, Linyuan Lu |
| 2002 | Hardware-assisted computation of depth contours. Shankar Krishnan, Nabil H. Mustafa, Suresh Venkatasubramanian |
| 2002 | Harmonic broadcasting is optimal. Lars Engebretsen, Madhu Sudan |
| 2002 | How to cut a cake almost fairly. Sven Oliver Krumke, Maarten Lipmann, Willem de Paepe, Diana Poensgen, Jörg Rambau, Leen Stougie, Gerhard J. Woeginger |
| 2002 | How unfair is optimal routing? Tim Roughgarden |
| 2002 | I/O-optimal algorithms for planar graphs using separators. Anil Maheshwari, Norbert Zeh |
| 2002 | Improved algorithms for stretch scheduling. Michael A. Bender, S. Muthukrishnan, Rajmohan Rajaraman |
| 2002 | Improved algorithms for the data placement problem. Sudipto Guha, Kamesh Munagala |
| 2002 | Improved bounds for the unsplittable flow problem. Petr Kolman, Christian Scheideler |
| 2002 | Improved labeling scheme for ancestor queries. Stephen Alstrup, Theis Rauhe |
| 2002 | Improving table compression with combinatorial optimization. Adam L. Buchsbaum, Glenn S. Fowler, Raffaele Giancarlo |
| 2002 | Incentive-compatible online auctions for digital goods. Ziv Bar-Yossef, Kirsten Hildrum, Felix Wu |
| 2002 | Is the internet fractal? Cédric Adjih, Leonidas Georgiadis, Philippe Jacquet, Wojciech Szpankowski |
| 2002 | Jenga. Uri Zwick |
| 2002 | Labeling schemes for flow and connectivity. Michal Katz, Nir A. Katz, Amos Korman, David Peleg |
| 2002 | Layout area of the hypercube (extended abstract). Shimon Even, Roni Kupershtok |
| 2002 | Light spanners and approximate TSP in weighted graphs with forbidden minors. Michelangelo Grigni, Papa A. Sissokho |
| 2002 | Linear-size approximate voronoi diagrams. Sunil Arya, Theocharis Malamatos |
| 2002 | Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits. Hsueh-I Lu |
| 2002 | MAX CUT in cubic graphs. Eran Halperin, Dror Livnat, Uri Zwick |
| 2002 | Maintaining stream statistics over sliding windows (extended abstract). Mayur Datar, Aristides Gionis, Piotr Indyk, Rajeev Motwani |
| 2002 | Matrix rounding under the Lp-discrepancy measure and its application to digital halftoning. Tetsuo Asano, Naoki Katoh, Koji Obokata, Takeshi Tokuyama |
| 2002 | Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms. Seth Pettie, Vijaya Ramachandran |
| 2002 | Mixing time and long paths in graphs. Igor Pak |
| 2002 | Motorcycle graphs and straight skeletons. Siu-Wing Cheng, Antoine Vigneron |
| 2002 | NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow. Thomas Erlebach, Alexander Hall |
| 2002 | New bounds for multi-dimensional packing. Steven S. Seiden, Rob van Stee |
| 2002 | On adaptive deterministic gossiping in ad hoc radio networks. Leszek Gasieniec, Andrzej Lingas |
| 2002 | On directed Steiner trees. Leonid Zosin, Samir Khuller |
| 2002 | On semidefinite programming relaxations for graph coloring and vertex cover. Moses Charikar |
| 2002 | On the overlay of envelopes in four dimensions. Vladlen Koltun, Micha Sharir |
| 2002 | On-line algorithms for the dynamic traveling repair problem. Sandy Irani, Xiangwen Lu, Amelia Regan |
| 2002 | On-line scheduling of a single machine to minimize total weighted completion time. Edward J. Anderson, Chris N. Potts |
| 2002 | Online algorithms for market clearing. Avrim Blum, Tuomas Sandholm, Martin Zinkevich |
| 2002 | Optimal time-space trade-offs for non-comparison-based sorting. Rasmus Pagh, Jakob Pagter |
| 2002 | Oracles for distances avoiding a link-failure. Camil Demetrescu, Mikkel Thorup |
| 2002 | Polynomial time recognition of P4-structure. Ryan B. Hayward, Stefan Hougardy, Bruce A. Reed |
| 2002 | Preprocessing an undirected planar network to enable fast approximate distance queries. Philip N. Klein |
| 2002 | Pricing multicasting in more practical network models. Micah Adler, Dan Rubenstein |
| 2002 | Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA. David Eppstein |
| 2002 | Pseudo-line arrangements: duality, algorithms, and applications. Pankaj K. Agarwal, Micha Sharir |
| 2002 | Quality meshing with weighted Delaunay refinement. Siu-Wing Cheng, Tamal K. Dey |
| 2002 | Reachability and distance queries via 2-hop labels. Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick |
| 2002 | Reductions in streaming algorithms, with an application to counting triangles in graphs. Ziv Bar-Yossef, Ravi Kumar, D. Sivakumar |
| 2002 | Roundtrip spanners and roundtrip routing in directed graphs. Liam Roditty, Mikkel Thorup, Uri Zwick |
| 2002 | Sampling from a moving window over streaming data. Brian Babcock, Mayur Datar, Rajeev Motwani |
| 2002 | Scheduling protocols for switches with large envelopes. Matthew Andrews, Lisa Zhang |
| 2002 | Scheduling split intervals. Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, Irina Shapira |
| 2002 | Semi-online maintenance of geometric optima and measures. Timothy M. Chan |
| 2002 | Separable attributes: a technique for solving the sub matrices character count problem. Amihood Amir, Kenneth Ward Church, Emanuel Dar |
| 2002 | Shape dimension and approximation from samples. Tamal K. Dey, Joachim Giesen, Samrat Goswami, Wulue Zhao |
| 2002 | Simple approximation algorithm for nonoverlapping local alignments. Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan |
| 2002 | Slice and dice: a simple, improved approximate tiling recipe. Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan |
| 2002 | Smooth-surface reconstruction in near-linear time. Stefan Funke, Edgar A. Ramos |
| 2002 | Smoothed analysis of the perceptron algorithm for linear programming. Avrim Blum, John Dunagan |
| 2002 | Static optimality and dynamic search-optimality in lists and trees. Avrim Blum, Shuchi Chawla, Adam Kalai |
| 2002 | Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao |
| 2002 | Succinct representations of lcp information and improvements in the compressed suffix arrays. Kunihiko Sadakane |
| 2002 | Symmetric drawings of triconnected planar graphs. Seok-Hee Hong, Brendan D. McKay, Peter Eades |
| 2002 | Temporary tasks assignment resolved. Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev |
| 2002 | Testing satisfiability. Noga Alon, Asaf Shapira |
| 2002 | The diameter of a long range percolation graph. Don Coppersmith, David Gamarnik, Maxim Sviridenko |
| 2002 | The freeze-tag problem: how to wake up a swarm of robots. Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell, Martin Skutella |
| 2002 | The mathematics of playing golf. Giovanni Rinaldi, Ulrich Voigt, Gerhard J. Woeginger |
| 2002 | The string edit distance matching problem with moves. Graham Cormode, S. Muthukrishnan |
| 2002 | The wake up and report problem is time-equivalent to the firing squad synchronization problem. Darin Goldstein, Nick Meyer |
| 2002 | Throughput maximization of real-time scheduling with batching. Amotz Bar-Noy, Sudipto Guha, Yoav Katz, Joseph Naor, Baruch Schieber, Hadas Shachnai |
| 2002 | Tight bounds for worst-case equilibria. Artur Czumaj, Berthold Vöcking |
| 2002 | Tiling groups for Wang tiles. Cristopher Moore, Ivan Rapaport, Eric Rémila |
| 2002 | Tree exploration with little memory. Krzysztof Diks, Pierre Fraigniaud, Evangelos Kranakis, Andrzej Pelc |
| 2002 | Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees. Rahul Shah, Martin Farach-Colton |
| 2002 | Union-find with deletions. Haim Kaplan, Nira Shafrir, Robert Endre Tarjan |
| 2002 | Web caching with request reordering. Tomás Feder, Rajeev Motwani, Rina Panigrahy, An Zhu |
| 2002 | Windows scheduling problems for broadcast systems. Amotz Bar-Noy, Richard E. Ladner |