| 2008 | (Almost) optimal coordination mechanisms for unrelated machine scheduling. Yossi Azar, Kamal Jain, Vahab S. Mirrokni |
| 2008 | A constant factor approximation algorithm for Ke Chen |
| 2008 | A deterministic sub-linear time sparse fourier algorithm via non-adaptive compressed sensing methods. Mark A. Iwen |
| 2008 | A fractional model of the border gateway protocol (BGP). Penny E. Haxell, Gordon T. Wilfong |
| 2008 | A local algorithm for finding dense subgraphs. Reid Andersen |
| 2008 | A near-linear time algorithm for computing replacement paths in planar directed graphs. Yuval Emek, David Peleg, Liam Roditty |
| 2008 | A nearly linear time algorithm for the half integral disjoint paths packing. Ken-ichi Kawarabayashi, Bruce A. Reed |
| 2008 | A plant location guide for the unsure. Barbara M. Anthony, Vineet Goyal, Anupam Gupta, Viswanath Nagarajan |
| 2008 | A tight lower bound for parity in noisy communication networks. Chinmoy Dutta, Yashodhan Kanoria, D. Manjunath, Jaikumar Radhakrishnan |
| 2008 | Adaptive local ratio. Julián Mestre |
| 2008 | Algorithms for distributed functional monitoring. Graham Cormode, S. Muthukrishnan, Ke Yi |
| 2008 | Algorithms for the coalitional manipulation problem. Michael Zuckerman, Ariel D. Procaccia, Jeffrey S. Rosenschein |
| 2008 | Almost Euclidean subspaces of l Venkatesan Guruswami, James R. Lee, Alexander A. Razborov |
| 2008 | An algorithm for improving graph partitions. Reid Andersen, Kevin J. Lang |
| 2008 | Analysis of greedy approximations with nonsubmodular potential functions. Ding-Zhu Du, Ronald L. Graham, Panos M. Pardalos, Peng-Jun Wan, Weili Wu, Wenbo Zhao |
| 2008 | Approximating TSP on metrics with bounded global growth. T.-H. Hubert Chan, Anupam Gupta |
| 2008 | Approximating connected facility location problems via random facility sampling and core detouring. Friedrich Eisenbrand, Fabrizio Grandoni, Thomas Rothvoß, Guido Schäfer |
| 2008 | Approximating general metric distances between a pattern and a text. Ely Porat, Klim Efremenko |
| 2008 | Approximating geometric coverage problems. Thomas Erlebach, Erik Jan van Leeuwen |
| 2008 | Approximation algorithms for labeling hierarchical taxonomies. Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy |
| 2008 | Arc-disjoint in-trees in directed graphs. Naoyuki Kamiyama, Naoki Katoh, Atsushi Takizawa |
| 2008 | Ascending auctions for integral (poly)matroids with concave nondecreasing separable values. Sushil Bikhchandani, Sven de Vries, James Schummer, Rakesh V. Vohra |
| 2008 | Auctions for structured procurement. Matthew Cary, Abraham D. Flaxman, Jason D. Hartline, Anna R. Karlin |
| 2008 | Balls and bins with structure: balanced allocations on hypergraphs. Brighten Godfrey |
| 2008 | Better bounds for online load balancing on unrelated machines. Ioannis Caragiannis |
| 2008 | Bounded-leg distance and reachability oracles. Ran Duan, Seth Pettie |
| 2008 | Broadcast scheduling: algorithms and complexity. Jessica Chang, Thomas Erlebach, Renars Gailis, Samir Khuller |
| 2008 | Catalan structures and dynamic programming in Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos |
| 2008 | Charity auctions on social networks. Arpita Ghosh, Mohammad Mahdian |
| 2008 | Clustering for metric and non-metric distance measures. Marcel R. Ackermann, Johannes Blömer, Christian Sohler |
| 2008 | Comparing the strength of query types in property testing: the case of testing Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron |
| 2008 | Competitive queue management for latency sensitive packets. Amos Fiat, Yishay Mansour, Uri Nadav |
| 2008 | Computational advertising. Andrei Z. Broder |
| 2008 | Computing excluded minors. Isolde Adler, Martin Grohe, Stephan Kreutzer |
| 2008 | Computing large matchings fast. Ignaz Rutter, Alexander Wolff |
| 2008 | Concatenated codes can achieve list-decoding capacity. Venkatesan Guruswami, Atri Rudra |
| 2008 | Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm. Kenneth L. Clarkson |
| 2008 | Cutting cycles of rods in space: hardness and approximation. Boris Aronov, Mark de Berg, Chris Gray, Elena Mumford |
| 2008 | Declaring independence via the sketching of sketches. Piotr Indyk, Andrew McGregor |
| 2008 | Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. Xiaomin Chen, János Pach, Mario Szegedy, Gábor Tardos |
| 2008 | Designing networks with good equilibria. Ho-Lin Chen, Tim Roughgarden, Gregory Valiant |
| 2008 | Deterministic random walks on regular trees. Joshua N. Cooper, Benjamin Doerr, Tobias Friedrich, Joel Spencer |
| 2008 | Dimension augmentation and combinatorial criteria for efficient error-resistant DNA self-assembly. Ho-Lin Chen, Ashish Goel, Chris Luhrs |
| 2008 | Distributed broadcast in unknown radio networks. Gianluca De Marco |
| 2008 | Distribution-sensitive point location in convex subdivisions. Sébastien Collette, Vida Dujmovic, John Iacono, Stefan Langerman, Pat Morin |
| 2008 | Dynamic optimality for skip lists and B-trees. Prosenjit Bose, Karim Douïeb, Stefan Langerman |
| 2008 | Earth mover distance over high-dimensional spaces. Alexandr Andoni, Piotr Indyk, Robert Krauthgamer |
| 2008 | Efficient reductions among lattice problems. Daniele Micciancio |
| 2008 | Embedding metric spaces in their intrinsic dimension. Ittai Abraham, Yair Bartal, Ofer Neiman |
| 2008 | Empty-ellipse graphs. Olivier Devillers, Jeff Erickson, Xavier Goaoc |
| 2008 | Estimators and tail bounds for dimension reduction in Ping Li |
| 2008 | Exact and efficient 2D-arrangements of arbitrary algebraic curves. Arno Eigenwillig, Michael Kerber |
| 2008 | Explicit constructions for compressed sensing of sparse signals. Piotr Indyk |
| 2008 | Fast algorithms for finding proper strategies in game trees. Peter Bro Miltersen, Troels Bjerre Sørensen |
| 2008 | Fast and reliable reconstruction of phylogenetic trees with very short edges. Ilan Gronau, Shlomo Moran, Sagi Snir |
| 2008 | Fast approximation of the permanent for very dense problems. Mark Huber, Jenny Law |
| 2008 | Fast asynchronous byzantine agreement and leader election with full information. Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, Vishal Sanwalani |
| 2008 | Fast dimension reduction using Rademacher series on dual BCH codes. Nir Ailon, Edo Liberty |
| 2008 | Fast edge splitting and Edmonds' arborescence construction for unweighted graphs. Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi |
| 2008 | Fast load balancing via bounded best response. Baruch Awerbuch, Yossi Azar, Rohit Khandekar |
| 2008 | Finding an optimal tree searching strategy in linear time. Shay Mozes, Krzysztof Onak, Oren Weimann |
| 2008 | Finding one tight cycle. Sergio Cabello, Matt DeVos, Jeff Erickson, Bojan Mohar |
| 2008 | Fully dynamic algorithm for graph spanners with poly-logarithmic update time. Surender Baswana, Soumojit Sarkar |
| 2008 | Fully polynomial time approximation schemes for stochastic dynamic programs. Nir Halman, Diego Klabjan, Chung-Lun Li, James B. Orlin, David Simchi-Levi |
| 2008 | Geodesic Delaunay triangulation and witness complex in the plane. Jie Gao, Leonidas J. Guibas, Steve Oudot, Yue Wang |
| 2008 | Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension. Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote |
| 2008 | Graph algorithms for biological systems analysis. Bonnie Berger, Rohit Singh, Jinbo Xu |
| 2008 | Graph balancing: a special case of scheduling unrelated parallel machines. Tomás Ebenlendr, Marek Krcál, Jirí Sgall |
| 2008 | Greedy drawings of triangulations. Raghavan Dhandapani |
| 2008 | Holographic algorithms with unsymmetric signatures. Jin-Yi Cai, Pinyan Lu |
| 2008 | Improved algorithmic versions of the Lovász Local Lemma. Aravind Srinivasan |
| 2008 | Improved algorithms for fully dynamic geometric spanners and geometric routing. Lee-Ad Gottlieb, Liam Roditty |
| 2008 | Improved algorithms for orienteering and related problems. Chandra Chekuri, Nitish Korula, Martin Pál |
| 2008 | Improved distance sensitivity oracles via random sampling. Aaron Bernstein, David R. Karger |
| 2008 | Improved string reconstruction over insertion-deletion channels. Krishnamurthy Viswanathan, Ram Swaminathan |
| 2008 | In-place 2-d nearest neighbor search. Timothy M. Chan, Eric Y. Chen |
| 2008 | Incentive compatible regression learning. Ofer Dekel, Felix A. Fischer, Ariel D. Procaccia |
| 2008 | Iterated rounding algorithms for the smallest Harold N. Gabow, Suzanne Gallagher |
| 2008 | L(2, 1)-labelling of graphs. Frédéric Havet, Bruce A. Reed, Jean-Sébastien Sereni |
| 2008 | Linked decompositions of networks and the power of choice in Polya urns. Henry C. Lin, Christos Amanatidis, Martha Sideri, Richard M. Karp, Christos H. Papadimitriou |
| 2008 | Lower-bounded facility location. Zoya Svitkina |
| 2008 | Maintaining deforming surface meshes. Siu-Wing Cheng, Tamal K. Dey |
| 2008 | Matroid intersection, pointer chasing, and Young's seminormal representation of Nicholas J. A. Harvey |
| 2008 | Maximum overhang. Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick |
| 2008 | Metric clustering via consistent labeling. Robert Krauthgamer, Tim Roughgarden |
| 2008 | Minimizing average latency in oblivious routing. Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Räcke, Jaikumar Radhakrishnan |
| 2008 | Minimum weight convex Steiner partitions. Adrian Dumitrescu, Csaba D. Tóth |
| 2008 | Noisy sorting without resampling. Mark Braverman, Elchanan Mossel |
| 2008 | Non-clairvoyant scheduling with precedence constraints. Julien Robert, Nicolas Schabanel |
| 2008 | Nondecreasing paths in a weighted graph or: how to optimally read a train schedule. Virginia Vassilevska |
| 2008 | On allocations that maximize fairness. Uriel Feige |
| 2008 | On clustering to minimize the sum of radii. Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, Kasturi R. Varadarajan |
| 2008 | On distance to monotonicity and longest increasing subsequence of a data stream. Funda Ergün, Hossein Jowhari |
| 2008 | On distributing symmetric streaming computations. Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Clifford Stein, Zoya Svitkina |
| 2008 | On properties of random dissections and triangulations. Nicla Bernasconi, Konstantinos Panagiotou, Angelika Steger |
| 2008 | On stars and Steiner stars. Adrian Dumitrescu, Csaba D. Tóth |
| 2008 | On the approximability of influence in social networks. Ning Chen |
| 2008 | On the bichromatic Timothy M. Chan |
| 2008 | On the connectivity of dynamic random geometric graphs. Josep Díaz, Dieter Mitsche, Xavier Pérez-Giménez |
| 2008 | On the value of coordination in network design. Susanne Albers |
| 2008 | Online budgeted matching in random input models with applications to Adwords. Gagan Goel, Aranyak Mehta |
| 2008 | Online make-to-order joint replenishment model: primal dual competitive algorithms. Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, Maxim Sviridenko |
| 2008 | Optimal universal graphs with deterministic embedding. Noga Alon, Michael R. Capalbo |
| 2008 | PageRank and the random surfer model. Prasad Chebolu, Páll Melsted |
| 2008 | Parallel monotonicity reconstruction. Michael E. Saks, C. Seshadhri |
| 2008 | Price based protocols for fair resource allocation: convergence time analysis and extension to Leontief utilities. Ashish Goel, Hamid Nazerzadeh |
| 2008 | Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008 Shang-Hua Teng |
| 2008 | Product growth and mixing in finite groups. László Babai, Nikolay Nikolov, László Pyber |
| 2008 | Provably good multicore cache performance for divide-and-conquer algorithms. Guy E. Blelloch, Rezaul Alam Chowdhury, Phillip B. Gibbons, Vijaya Ramachandran, Shimin Chen, Michael Kozuch |
| 2008 | Quasirandom rumor spreading. Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald |
| 2008 | Ranged hash functions and the price of churn. James Aspnes, Muli Safra, Yitong Yin |
| 2008 | Rapid mixing of Gibbs sampling on graphs that are sparse on average. Elchanan Mossel, Allan Sly |
| 2008 | Real-time indexing over fixed finite alphabets. Amihood Amir, Igor Nor |
| 2008 | Recognizing partial cubes in quadratic time. David Eppstein |
| 2008 | Robust cost colorings. Takuro Fukunaga, Magnús M. Halldórsson, Hiroshi Nagamochi |
| 2008 | SPREAD: an adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems. Mario Mense, Christian Scheideler |
| 2008 | Sampling algorithms and coresets for ℓ Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, Michael W. Mahoney |
| 2008 | Sampling stable marriages: why spouse-swapping won't work. Nayantara Bhatnagar, Sam Greenberg, Dana Randall |
| 2008 | Set connectivity problems in undirected graphs and the directed Steiner network problem. Chandra Chekuri, Guy Even, Anupam Gupta, Danny Segev |
| 2008 | Shuffling cards, adding numbers, and symmetric functions. Persi Diaconis |
| 2008 | Space-efficient dynamic orthogonal point location, segment intersection, and range reporting. Guy E. Blelloch |
| 2008 | Splay trees, Davenport-Schinzel sequences, and the deque conjecture. Seth Pettie |
| 2008 | Stochastic analyses for online combinatorial optimization problems. Naveen Garg, Anupam Gupta, Stefano Leonardi, Piotr Sankowski |
| 2008 | Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization. S. Thomas McCormick, Satoru Fujishige |
| 2008 | Succinct approximate convex pareto curves. Ilias Diakonikolas, Mihalis Yannakakis |
| 2008 | The UGC hardness threshold of the ℓ Guy Kindler, Assaf Naor, Gideon Schechtman |
| 2008 | The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond. Alex Fabrikant, Christos H. Papadimitriou |
| 2008 | The effect of induced subgraphs on quasi-randomness. Asaf Shapira, Raphael Yuster |
| 2008 | The hiring problem and Lake Wobegon strategies. Andrei Z. Broder, Adam Kirsch, Ravi Kumar, Michael Mitzenmacher, Eli Upfal, Sergei Vassilvitskii |
| 2008 | The power of memory in randomized broadcasting. Robert Elsässer, Thomas Sauerwald |
| 2008 | Tight lower bounds for selection in randomly ordered streams. Amit Chakrabarti, T. S. Jayram, Mihai Patrascu |
| 2008 | Trace reconstruction with constant deletion probability and related results. Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, Udi Wieder |
| 2008 | Two-phase greedy algorithms for some classes of combinatorial linear programs. Ulrich Faigle, Britta Peis |
| 2008 | Ultra-low-dimensional embeddings for doubling metrics. T.-H. Hubert Chan, Anupam Gupta, Kunal Talwar |
| 2008 | Unconditionally reliable message transmission in directed networks. Bhavani Shankar, Prasant Gopal, Kannan Srinathan, C. Pandu Rangan |
| 2008 | Universality of random graphs. Domingos Dellamonica Jr., Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski |
| 2008 | Weak ε-nets and interval chains. Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky |
| 2008 | Why simple hash functions work: exploiting the entropy in a data stream. Michael Mitzenmacher, Salil P. Vadhan |
| 2008 | Yet another algorithm for dense max cut: go greedy. Claire Mathieu, Warren Schudy |