| 2005 | A categorization theorem on suffix arrays with applications to space efficient text indexes. Meng He, J. Ian Munro, S. Srinivasa Rao |
| 2005 | A constant approximation algorithm for the one-warehouse multi-retailer problem. Retsef Levi, Robin Roundy, David B. Shmoys |
| 2005 | A constant-factor approximation algorithm for optimal terrain guarding. Boaz Ben-Moshe, Matthew J. Katz, Joseph S. B. Mitchell |
| 2005 | A group-strategyproof mechanism for Steiner forests. Jochen Könemann, Stefano Leonardi, Guido Schäfer |
| 2005 | A multiple-choice secretary algorithm with applications to online auctions. Robert D. Kleinberg |
| 2005 | A new look at survey propagation and its generalizations. Elitza N. Maneva, Elchanan Mossel, Martin J. Wainwright |
| 2005 | A spectral heuristic for bisecting random graphs. Amin Coja-Oghlan |
| 2005 | A tight threshold for metric Ramsey phenomena. Moses Charikar, Adriana Karagiozova |
| 2005 | Adaptivity and approximation for stochastic packing problems. Brian C. Dean, Michel X. Goemans, Jan Vondrák |
| 2005 | Adversarial deletion in a scale free random graph process. Abraham Flaxman, Alan M. Frieze, Juan Vera |
| 2005 | Algorithms for combining rooted triplets into a galled phylogenetic network. Jesper Jansson, Nguyen Bao Nguyen, Wing-Kin Sung |
| 2005 | All maximal independent sets and dynamic dominance for sparse graphs. David Eppstein |
| 2005 | An O(VE) algorithm for ear decompositions of matching-covered graphs. Marcelo Henriques de Carvalho, Joseph Cheriyan |
| 2005 | An asymptotic approximation scheme for multigraph edge coloring. Peter Sanders, David Steurer |
| 2005 | An improved approximation algorithm for virtual private network design. Friedrich Eisenbrand, Fabrizio Grandoni |
| 2005 | An optimal Bloom filter replacement. Anna Pagh, Rasmus Pagh, S. Srinivasa Rao |
| 2005 | An optimal dynamic interval stabbing-max data structure? Pankaj K. Agarwal, Lars Arge, Ke Yi |
| 2005 | An optimal online algorithm for packet scheduling with agreeable deadlines. Fei Li, Jay Sethuraman, Clifford Stein |
| 2005 | Analyzing and characterizing small-world graphs. Van Nguyen, Charles U. Martel |
| 2005 | Approximating connectivity augmentation problems. Zeev Nutov |
| 2005 | Approximating k-median with non-uniform capacities. Julia Chuzhoy, Yuval Rabani |
| 2005 | Approximating the average response time in broadcast scheduling. Nikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor |
| 2005 | Approximating the smallest Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson |
| 2005 | Approximating vertex cover on dense graphs. Tomokazu Imamura, Kazuo Iwama |
| 2005 | Approximation algorithms for cycle packing problems. Michael Krivelevich, Zeev Nutov, Raphael Yuster |
| 2005 | Approximation algorithms for low-distortion embeddings into low-dimensional spaces. Mihai Badoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, Anastasios Sidiropoulos |
| 2005 | Approximation hardness of optimization problems in intersection graphs of Miroslav Chlebík, Janka Chlebíková |
| 2005 | Bidimensionality: new connections between FPT algorithms and PTASs. Erik D. Demaine, Mohammad Taghi Hajiaghayi |
| 2005 | Can the TPRI structure help us to solve the algebraic eigenproblem? Victor Y. Pan |
| 2005 | Coins make quantum walks faster. Andris Ambainis, Julia Kempe, Alexander Rivosh |
| 2005 | Collecting correlated information from a sensor network. Micah Adler |
| 2005 | Collusion-resistant mechanisms for single-parameter agents. Andrew V. Goldberg, Jason D. Hartline |
| 2005 | Complete partitions of graphs. Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian |
| 2005 | Computing equilibria in multi-player games. Christos H. Papadimitriou, Tim Roughgarden |
| 2005 | Computing minimal triangulations in time O(n Pinar Heggernes, Jan Arne Telle, Yngve Villanger |
| 2005 | Computing the shortest path: Andrew V. Goldberg, Chris Harrelson |
| 2005 | Conformance testing in the presence of multiple faults. Viraj Kumar, Mahesh Viswanathan |
| 2005 | Controlled perturbation for Delaunay triangulations. Stefan Funke, Christian Klein, Kurt Mehlhorn, Susanne Schmitt |
| 2005 | Coupling with the stationary distribution and improved sampling for colorings and independent sets. Thomas P. Hayes, Eric Vigoda |
| 2005 | Delaunay triangulations approximate anchor hulls. Tamal K. Dey, Joachim Giesen, Samrat Goswami |
| 2005 | Deterministic network coding by matrix completion. Nicholas J. A. Harvey, David R. Karger, Kazuo Murota |
| 2005 | Dictionaries using variable-length keys and data, with applications. Daniel K. Blandford, Guy E. Blelloch |
| 2005 | Dissections and trees, with applications to optimal mesh encoding and to random sampling. Éric Fusy, Dominique Poulalhon, Gilles Schaeffer |
| 2005 | Distributed approaches to triangulation and embedding. Aleksandrs Slivkins |
| 2005 | Distributed online call control on general networks. Harald Räcke, Adi Rosén |
| 2005 | Distributions of points in the unit-square and large Hanno Lefmann |
| 2005 | Dominator tree verification and vertex-disjoint paths. Loukas Georgiadis, Robert Endre Tarjan |
| 2005 | Dotted interval graphs and high throughput genotyping. Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Y. Pinter, Zohar Yakhini |
| 2005 | Dynamic dictionary matching and compressed suffix trees. Ho-Leung Chan, Wing-Kai Hon, Tak Wah Lam, Kunihiko Sadakane |
| 2005 | Efficient hashing with lookups in two memory accesses. Rina Panigrahy |
| 2005 | Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. Shuchi Chawla, Anupam Gupta, Harald Räcke |
| 2005 | External-memory exact and approximate all-pairs shortest-paths in undirected graphs. Rezaul Alam Chowdhury, Vijaya Ramachandran |
| 2005 | Fast convergence of selfish rerouting. Eyal Even-Dar, Yishay Mansour |
| 2005 | Finding large cycles in Hamiltonian graphs. Tomás Feder, Rajeev Motwani |
| 2005 | Finding the shortest bottleneck edge in a parametric minimum spanning tree. Timothy M. Chan |
| 2005 | Girth restrictions for the 5-flow conjecture. Martin Kochol |
| 2005 | Graph distances in the streaming model: the value of space. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang |
| 2005 | Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality. Erik D. Demaine, Mohammad Taghi Hajiaghayi |
| 2005 | Greedy optimal homotopy and homology generators. Jeff Erickson, Kim Whittlesey |
| 2005 | How fast is the k-means method? Sariel Har-Peled, Bardia Sadri |
| 2005 | Improved approximation for universal facility location. Naveen Garg, Rohit Khandekar, Vinayaka Pandit |
| 2005 | Improved range-summable random variable construction algorithms. A. Robert Calderbank, Anna C. Gilbert, Kirill Levchenko, S. Muthukrishnan, Martin Strauss |
| 2005 | Improved recommendation systems. Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, Mark R. Tuttle |
| 2005 | Improved schedule for radio broadcast. Michael Elkin, Guy Kortsarz |
| 2005 | Inoculation strategies for victims of viruses and the sum-of-squares partition problem. James Aspnes, Kevin L. Chang, Aleksandr Yampolskiy |
| 2005 | Isomorphism and embedding problems for infinite limits of scale-free graphs. Robert D. Kleinberg, Jon M. Kleinberg |
| 2005 | Job shop scheduling with unit processing times. Nikhil Bansal, Tracy Kimbrel, Maxim Sviridenko |
| 2005 | LP decoding achieves capacity. Jon Feldman, Clifford Stein |
| 2005 | Limitations of cross-monotonic cost sharing schemes. Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni |
| 2005 | Linear equations, arithmetic progressions and hypergraph property testing. Noga Alon, Asaf Shapira |
| 2005 | Loop quantum gravity. John C. Baez |
| 2005 | Lower bound for sparse Euclidean spanners. Pankaj K. Agarwal, Yusu Wang, Peng Yin |
| 2005 | Lower bounds for external algebraic decision trees. Jeff Erickson |
| 2005 | Lower bounds on the size of selection and rank indexes. Peter Bro Miltersen |
| 2005 | Manifold reconstruction from point samples. Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos |
| 2005 | Market equilibria for homothetic, quasi-concave utilities and economies of scale in production. Kamal Jain, Vijay V. Vazirani, Yinyu Ye |
| 2005 | Marriage, honesty, and stability. Nicole Immorlica, Mohammad Mahdian |
| 2005 | Matrix rounding with low error in small submatrices. Benjamin Doerr |
| 2005 | Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. Venkatesan Guruswami, Alexander Vardy |
| 2005 | Multicoloring unit disk graphs on triangular lattice points. Yuichiro Miyamoto, Tomomi Matsui |
| 2005 | Multidimensional balanced allocations. Andrei Z. Broder, Michael Mitzenmacher |
| 2005 | Multiple-source shortest paths in planar graphs. Philip N. Klein |
| 2005 | Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group. László Babai, Thomas P. Hayes |
| 2005 | Near-optimal online auctions. Avrim Blum, Jason D. Hartline |
| 2005 | Network coding: does the model need tuning? April Rasala Lehman, Eric Lehman |
| 2005 | Network design for information networks. Ara Hayrapetyan, Chaitanya Swamy, Éva Tardos |
| 2005 | New constructions of (alpha, beta)-spanners and purely additive spanners. Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie |
| 2005 | Oblivious routing on node-capacitated and directed graphs. Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke |
| 2005 | On approximating the depth and related problems. Boris Aronov, Sariel Har-Peled |
| 2005 | On distance scales, embeddings, and efficient relaxations of the cut cone. James R. Lee |
| 2005 | On geometric permutations induced by lines transversal through a fixed point. Boris Aronov, Shakhar Smorodinsky |
| 2005 | On hierarchical routing in doubling metrics. Hubert Tsz-Hong Chan, Anupam Gupta, Bruce M. Maggs, Shuheng Zhou |
| 2005 | On levels in arrangements of surfaces in three dimensions. Timothy M. Chan |
| 2005 | On profit-maximizing envy-free pricing. Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, Frank McSherry |
| 2005 | On the approximability of some network design problems. Julia Chuzhoy, Anupam Gupta, Joseph Naor, Amitabh Sinha |
| 2005 | On the polynomial time computation of equilibria for certain exchange economies. Bruno Codenotti, Sriram V. Pemmaraju, Kasturi R. Varadarajan |
| 2005 | On the random 2-stage minimum spanning tree. Abraham D. Flaxman, Alan M. Frieze, Michael Krivelevich |
| 2005 | On the spread of viruses on the internet. Noam Berger, Christian Borgs, Jennifer T. Chayes, Amin Saberi |
| 2005 | Online ascending auctions for gradually expiring items. Ron Lavi, Noam Nisan |
| 2005 | Online client-server load balancing without global information. Baruch Awerbuch, Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton |
| 2005 | Online conflict-free coloring for intervals. Amos Fiat, Meital Levy, Jirí Matousek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, Emo Welzl |
| 2005 | Online convex optimization in the bandit setting: gradient descent without a gradient. Abraham Flaxman, Adam Tauman Kalai, H. Brendan McMahan |
| 2005 | Online topological ordering. Irit Katriel, Hans L. Bodlaender |
| 2005 | Optimal random number generation from a biased coin. Sung-Il Pae, Michael C. Loui |
| 2005 | Optimizing markov models with applications to triangular connectivity coding. Stefan Gumhold |
| 2005 | Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. Noga Alon, Mihai Badoiu, Erik D. Demaine, Martin Farach-Colton, Mohammad Taghi Hajiaghayi, Anastasios Sidiropoulos |
| 2005 | Partial covering of hypergraphs. Özgür Sümer |
| 2005 | Pianos are not flat: rigid motion planning in three dimensions. Vladlen Koltun |
| 2005 | Popular matchings. David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn |
| 2005 | Primal-dual approach for directed vertex connectivity augmentation and generalizations. László A. Végh, András A. Benczúr |
| 2005 | Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005 |
| 2005 | Provably good moving least squares. Ravi Krishna Kolluri |
| 2005 | Quantum algorithms for the triangle problem. Frédéric Magniez, Miklos Santha, Mario Szegedy |
| 2005 | Random planar graphs with Stefanie Gerke, Colin McDiarmid, Angelika Steger, Andreas Weißl |
| 2005 | Ray shooting amid balls, farthest point from a line, and range emptiness searching. Micha Sharir, Hayim Shaul |
| 2005 | Rigorous analysis of heuristics for NP-hard problems. Uriel Feige |
| 2005 | Rounds vs queries trade-off in noisy computation. Navin Goyal, Michael E. Saks |
| 2005 | Sampling regular graphs and a peer-to-peer network. Colin Cooper, Martin E. Dyer, Catherine S. Greenhill |
| 2005 | Self-adjusting top trees. Robert Endre Tarjan, Renato Fonseca F. Werneck |
| 2005 | Selfish routing with atomic players. Tim Roughgarden |
| 2005 | Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy. Luca Becchetti, Jochen Könemann, Stefano Leonardi, Martin Pál |
| 2005 | Space-time tradeoffs for approximate spherical range counting. Sunil Arya, Theocharis Malamatos, David M. Mount |
| 2005 | Sparse source-wise and pair-wise distance preservers. Don Coppersmith, Michael Elkin |
| 2005 | Strictly convex drawings of planar graphs. Günter Rote |
| 2005 | Substring compression problems. Graham Cormode, S. Muthukrishnan |
| 2005 | Testing hierarchical systems. Damon Mosk-Aoyama, Mihalis Yannakakis |
| 2005 | The bin-covering technique for thresholding random geometric graph properties. S. Muthukrishnan, Gopal Pandurangan |
| 2005 | The complexity of low-distortion embeddings between point sets. Christos H. Papadimitriou, Shmuel Safra |
| 2005 | The cover time of two classes of random graphs. Colin Cooper, Alan M. Frieze |
| 2005 | The expected value of random minimal length spanning tree of a complete graph. David Gamarnik |
| 2005 | The hidden subgroup problem and permutation group theory. Julia Kempe, Aner Shalev |
| 2005 | The influence of search engines on preferential attachment. Soumen Chakrabarti, Alan M. Frieze, Juan Vera |
| 2005 | The interface between computational and combinatorial geometry. Micha Sharir |
| 2005 | The relative worst order ratio applied to paging. Joan Boyar, Lene M. Favrholdt, Kim S. Larsen |
| 2005 | Theory of semidefinite programming for sensor network localization. Anthony Man-Cho So, Yinyu Ye |
| 2005 | Towards a complete characterization of tries. GaHyun Park, Wojciech Szpankowski |
| 2005 | Two algorithms for general list matrix partitions. Tomás Feder, Pavol Hell, Daniel Král, Jirí Sgall |
| 2005 | Unknotting is in AM cup co-AM. Masao Hara, Seiichi Tani, Makoto Yamamoto |