| 2006 | 8/7-approximation algorithm for (1, 2)-TSP. Piotr Berman, Marek Karpinski |
| 2006 | A computational study of external-memory BFS algorithms. Deepak Ajwani, Roman Dementiev, Ulrich Meyer |
| 2006 | A deterministic subexponential algorithm for solving parity games. Marcin Jurdzinski, Mike Paterson, Uri Zwick |
| 2006 | A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. Timothy M. Chan |
| 2006 | A general approach for incremental approximation and hierarchical clustering. Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson |
| 2006 | A near-tight approximation lower bound and algorithm for the kidnapped robot problem. Sven Koenig, Apurva Mudgal, Craig A. Tovey |
| 2006 | A new approach to proving upper bounds for MAX-2-SAT. Arist Kojevnikov, Alexander S. Kulikov |
| 2006 | A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. Vadim V. Lozin, Martin Milanic |
| 2006 | A robust maximum completion time measure for scheduling. Moses Charikar, Samir Khuller |
| 2006 | A semidefinite programming approach to tensegrity theory and realizability of graphs. Anthony Man-Cho So, Yinyu Ye |
| 2006 | A simple GAP-canceling algorithm for the generalized maximum flow problem. Mateo Restrepo, David P. Williamson |
| 2006 | A tight upper bound on the probabilistic embedding of series-parallel graphs. Yuval Emek, David Peleg |
| 2006 | Accelerating simulated annealing for the permanent and combinatorial counting problems. Ivona Bezáková, Daniel Stefankovic, Vijay V. Vazirani, Eric Vigoda |
| 2006 | All-pairs shortest paths for unweighted undirected graphs in Timothy M. Chan |
| 2006 | An Glencora Borradaile, Philip N. Klein |
| 2006 | An algorithmic Friedman--Pippenger theorem on tree embeddings and applications to routing. Domingos Dellamonica Jr., Yoshiharu Kohayakawa |
| 2006 | An asymptotic approximation algorithm for 3D-strip packing. Klaus Jansen, Roberto Solis-Oba |
| 2006 | An improved approximation algorithm for combinatorial auctions with submodular bidders. Shahar Dobzinski, Michael Schapira |
| 2006 | Analysis of incomplete data and an intrinsic-dimension Helly theorem. Jie Gao, Michael Langberg, Leonard J. Schulman |
| 2006 | Analyzing BitTorrent and related peer-to-peer networks. David Arthur, Rina Panigrahy |
| 2006 | Anisotropic surface meshing. Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, Rephael Wenger |
| 2006 | Anytime algorithms for multi-armed bandit problems. Robert D. Kleinberg |
| 2006 | Approximating the Daniel Golovin, Viswanath Nagarajan, Mohit Singh |
| 2006 | Approximating unique games. Anupam Gupta, Kunal Talwar |
| 2006 | Approximation algorithms for wavelet transform coding of data streams. Sudipto Guha, Boulos Harb |
| 2006 | Asymmetric balanced allocation with simple hash functions. Philipp Woelfel |
| 2006 | Balanced allocation on graphs. Krishnaram Kenthapadi, Rina Panigrahy |
| 2006 | Bottleneck links, variable demand, and the tragedy of the commons. Richard Cole, Yevgeniy Dodis, Tim Roughgarden |
| 2006 | Cache-oblivious dynamic programming. Rezaul Alam Chowdhury, Vijaya Ramachandran |
| 2006 | Cache-oblivious string dictionaries. Gerth Stølting Brodal, Rolf Fagerberg |
| 2006 | Cake cutting really is not a piece of cake. Jeff Edmonds, Kirk Pruhs |
| 2006 | Certifying large branch-width. Sang-il Oum, Paul D. Seymour |
| 2006 | Combination can be hard: approximability of the unique coverage problem. Erik D. Demaine, Mohammad Taghi Hajiaghayi, Uriel Feige, Mohammad R. Salavatipour |
| 2006 | Computing sequential equilibria for two-player games. Peter Bro Miltersen, Troels Bjerre Sørensen |
| 2006 | Computing steiner minimum trees in Hamming metric. Ernst Althaus, Rouven Naujoks |
| 2006 | Confronting hardness using a hybrid approach. Virginia Vassilevska, Ryan Williams, Shan Leung Maverick Woo |
| 2006 | Constraint solving via fractional edge covers. Martin Grohe, Dániel Marx |
| 2006 | Correlation clustering with a fixed number of clusters. Ioannis Giotis, Venkatesan Guruswami |
| 2006 | Counting without sampling: new algorithms for enumeration problems using statistical physics. Antar Bandyopadhyay, David Gamarnik |
| 2006 | Critical chromatic number and the complexity of perfect packings in graphs. Daniela Kühn, Deryk Osthus |
| 2006 | DAG-width: connectivity measure for directed graphs. Jan Obdrzálek |
| 2006 | Design of data structures for mergeable trees. Loukas Georgiadis, Robert Endre Tarjan, Renato Fonseca F. Werneck |
| 2006 | Deterministic boundary recognition and topology extraction for large sensor networks. Alexander Kröller, Sándor P. Fekete, Dennis Pfisterer, Stefan Fischer |
| 2006 | Directed metrics and directed graph partitioning problems. Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2006 | Distributed selfish load balancing. Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul W. Goldberg, Zengjian Hu, Russell A. Martin |
| 2006 | Efficient algorithms for substring near neighbor problem. Alexandr Andoni, Piotr Indyk |
| 2006 | Efficient construction of unit circular-arc models. Min Chih Lin, Jayme Luiz Szwarcfiter |
| 2006 | Entropy based nearest neighbor search in high dimensions. Rina Panigrahy |
| 2006 | Equilibria for economies with production: constant-returns technologies and production planning constraints. Kamal Jain, Kasturi R. Varadarajan |
| 2006 | Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling. Ho-Leung Chan, Tak Wah Lam, Kin-Shing Liu |
| 2006 | FPTAS for mixed-integer polynomial optimization with a fixed number of variables. Jesús A. De Loera, Raymond Hemmecke, Matthias Köppe, Robert Weismantel |
| 2006 | Facility location with hierarchical facility costs. Zoya Svitkina, Éva Tardos |
| 2006 | Finding large sticks and potatoes in polygons. Olaf A. Hall-Holt, Matthew J. Katz, Piyush Kumar, Joseph S. B. Mitchell, Arik Sityon |
| 2006 | Finding nucleolus of flow game. Xiaotie Deng, Qizhi Fang, Xiaoxun Sun |
| 2006 | Four point conditions and exponential neighborhoods for symmetric TSP. Vladimir G. Deineko, Bettina Klinz, Gerhard J. Woeginger |
| 2006 | Generating all vertices of a polyhedron is hard. Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, Vladimir Gurvich |
| 2006 | Implicit dictionaries with Gianni Franceschini, J. Ian Munro |
| 2006 | Improved approximation algorithms for broadcast scheduling. Nikhil Bansal, Don Coppersmith, Maxim Sviridenko |
| 2006 | Improved embeddings of graph metrics into random trees. Kedar Dhamdhere, Anupam Gupta, Harald Räcke |
| 2006 | Improved lower and upper bounds for universal TSP in planar metrics. Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton |
| 2006 | Improved lower bounds for embeddings into Robert Krauthgamer, Yuval Rabani |
| 2006 | Knapsack auctions. Gagan Aggarwal, Jason D. Hartline |
| 2006 | Leontief economies encode nonzero sum two-player games. Bruno Codenotti, Amin Saberi, Kasturi R. Varadarajan, Yinyu Ye |
| 2006 | Linear programming and unique sink orientations. Bernd Gärtner, Ingo Schurr |
| 2006 | Local versus global properties of metric spaces. Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh S. Vempala |
| 2006 | Lower bounds for asymmetric communication channels and distributed source coding. Micah Adler, Erik D. Demaine, Nicholas J. A. Harvey, Mihai Patrascu |
| 2006 | Maintaining significant stream statistics over sliding windows. Lap-Kei Lee, H. F. Ting |
| 2006 | Many distances in planar graphs. Sergio Cabello |
| 2006 | Matrix approximation and projective clustering via volume sampling. Amit Deshpande, Luis Rademacher, Santosh S. Vempala, Grant Wang |
| 2006 | Max-tolerance graphs as intersection graphs: cliques, cycles, and recognition. Michael Kaufmann, Jan Kratochvíl, Katharina Anna Lehmann, Amarendran Ramaswami Subramanian |
| 2006 | Measure and conquer: a simple O(2 Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch |
| 2006 | Metric cotype. Manor Mendel, Assaf Naor |
| 2006 | Morphing orthogonal planar graph drawings. Anna Lubiw, Mark Petrick, Michael J. Spriggs |
| 2006 | New lower bounds for oblivious routing in undirected graphs. Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton, Harald Räcke |
| 2006 | Oblivious network design. Anupam Gupta, Mohammad Taghi Hajiaghayi, Harald Räcke |
| 2006 | Oblivious string embeddings and edit distance approximations. Tugkan Batu, Funda Ergün, Süleyman Cenk Sahinalp |
| 2006 | On Ke Chen |
| 2006 | On nash equilibria for a network creation game. Susanne Albers, Stefan Eilts, Eyal Even-Dar, Yishay Mansour, Liam Roditty |
| 2006 | On the capacity of information networks. Micah Adler, Nicholas J. A. Harvey, Kamal Jain, Robert D. Kleinberg, April Rasala Lehman |
| 2006 | On the chromatic number of some geometric hypergraphs. Shakhar Smorodinsky |
| 2006 | On the competitive ratio of evaluating priced functions. Ferdinando Cicalese, Eduardo Sany Laber |
| 2006 | On the diameter of Eulerian orientations of graphs. László Babai |
| 2006 | On the number of crossing-free matchings, (cycles, and partitions). Micha Sharir, Emo Welzl |
| 2006 | On the number of plane graphs. Oswin Aichholzer, Thomas Hackl, Birgit Vogtenhuber, Clemens Huemer, Ferran Hurtado, Hannes Krasser |
| 2006 | On the tandem duplication-random loss model of genome rearrangement. Kamalika Chaudhuri, Kevin C. Chen, Radu Mihaescu, Satish Rao |
| 2006 | Ordering by weighted number of wins gives a good ranking for weighted tournaments. Don Coppersmith, Lisa Fleischer, Atri Rudra |
| 2006 | Overhang. Mike Paterson, Uri Zwick |
| 2006 | Pattern matching with address errors: rearrangement distances. Amihood Amir, Yonatan Aumann, Gary Benson, Avivit Levy, Ohad Lipsky, Ely Porat, Steven Skiena, Uzi Vishne |
| 2006 | Predicting the "unpredictable". Rakesh V. Vohra |
| 2006 | Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006 |
| 2006 | Quantum verification of matrix products. Harry Buhrman, Robert Spalek |
| 2006 | Query-efficient algorithms for polynomial interpolation over composites. Parikshit Gopalan |
| 2006 | Random graphs. Alan M. Frieze |
| 2006 | Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting. Haim Kaplan, Micha Sharir |
| 2006 | Randomized online algorithms for minimum metric bipartite matching. Adam Meyerson, Akash Nanavati, Laura J. Poplawski |
| 2006 | Rank/select operations on large alphabets: a tool for text indexing. Alexander Golynski, J. Ian Munro, S. Srinivasa Rao |
| 2006 | Reducing tile complexity for self-assembly through temperature programming. Ming-Yang Kao, Robert T. Schweller |
| 2006 | Relating singular values and discrepancy of weighted directed graphs. Steven Butler |
| 2006 | Revenue maximization when bidders have budgets. Zoë Abrams |
| 2006 | Robbing the bandit: less regret in online geometric optimization against an adaptive adversary. Varsha Dani, Thomas P. Hayes |
| 2006 | Robust shape fitting via peeling and grating coresets. Pankaj K. Agarwal, Sariel Har-Peled, Hai Yu |
| 2006 | Sampling algorithms for Petros Drineas, Michael W. Mahoney, S. Muthukrishnan |
| 2006 | Sampling binary contingency tables with a greedy start. Ivona Bezáková, Nayantara Bhatnagar, Eric Vigoda |
| 2006 | Scalable leader election. Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee |
| 2006 | Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management. Philippe Baptiste |
| 2006 | Self-improving algorithms. Nir Ailon, Bernard Chazelle, Seshadhri Comandur, Ding Liu |
| 2006 | Simpler algorithm for estimating frequency moments of data streams. Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, Chandan Saha |
| 2006 | Simultaneous diagonal flips in plane triangulations. Prosenjit Bose, Jurek Czyzowicz, Zhicheng Gao, Pat Morin, David R. Wood |
| 2006 | Single-minded unlimited supply pricing on sparse instances. Patrick Briest, Piotr Krysta |
| 2006 | Single-value combinatorial auctions and implementation in undominated strategies. Moshe Babaioff, Ron Lavi, Elan Pavlov |
| 2006 | Slow mixing of glauber dynamics via topological obstructions. Dana Randall |
| 2006 | Small hop-diameter sparse spanners for doubling metrics. T.-H. Hubert Chan, Anupam Gupta |
| 2006 | Solving random satisfiable 3CNF formulas in expected polynomial time. Michael Krivelevich, Dan Vilenchik |
| 2006 | Spanners and emulators with sublinear distance errors. Mikkel Thorup, Uri Zwick |
| 2006 | Squeezing succinct data structures into entropy bounds. Kunihiko Sadakane, Roberto Grossi |
| 2006 | Streaming and sublinear approximation of entropy and information distances. Sudipto Guha, Andrew McGregor, Suresh Venkatasubramanian |
| 2006 | Subgraph characterization of Red/Blue-Split Graph and König Egerváry Graphs. Ephraim Korach, Thành Nguyen, Britta Peis |
| 2006 | Superiority and complexity of the spaced seeds. Ming Li, Bin Ma, Louxin Zhang |
| 2006 | Testing graph isomorphism. Eldar Fischer, Arie Matsliah |
| 2006 | Testing triangle-freeness in general graphs. Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron |
| 2006 | The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity. Wolfgang W. Bein, Mordecai J. Golin, Lawrence L. Larmore, Yan Zhang |
| 2006 | The complexity of matrix completion. Nicholas J. A. Harvey, David R. Karger, Sergey Yekhanin |
| 2006 | The complexity of quantitative concurrent parity games. Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger |
| 2006 | The hunting of the bump: on maximizing statistical discrepancy. Deepak Agarwal, Jeff M. Phillips, Suresh Venkatasubramanian |
| 2006 | The price of being near-sighted. Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer |
| 2006 | The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema. Mohammad Taghi Hajiaghayi, Kamal Jain |
| 2006 | The rainbow skip graph: a fault-tolerant constant-degree distributed data structure. Michael T. Goodrich, Michael J. Nelson, Jonathan Z. Sun |
| 2006 | The space complexity of pass-efficient algorithms for clustering. Kevin L. Chang, Ravi Kannan |
| 2006 | Tight approximation algorithms for maximum general assignment problems. Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko |
| 2006 | Tightening non-simple paths and cycles on surfaces. Éric Colin de Verdière, Jeff Erickson |
| 2006 | Trading off space for passes in graph streaming problems. Camil Demetrescu, Irene Finocchi, Andrea Ribichini |
| 2006 | Trees and Markov convexity. James R. Lee, Assaf Naor, Yuval Peres |
| 2006 | Upper degree-constrained partial orientations. Harold N. Gabow |
| 2006 | Vertical ray shooting and computing depth orders for fat objects. Mark de Berg, Chris Gray |
| 2006 | Weighted isotonic regression under the Stanislav Angelov, Boulos Harb, Sampath Kannan, Li-San Wang |