| 2006 | Tight approximation algorithms for maximum general assignment problems. | Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko |
| 2006 | Testing graph isomorphism. | Eldar Fischer, Arie Matsliah |
| 2006 | A tight upper bound on the probabilistic embedding of series-parallel graphs. | Yuval Emek, David Peleg |
| 2006 | Cake cutting really is not a piece of cake. | Jeff Edmonds, Kirk Pruhs |
| 2006 | Sampling algorithms for | Petros Drineas, Michael W. Mahoney, S. Muthukrishnan |
| 2006 | An improved approximation algorithm for combinatorial auctions with submodular bidders. | Shahar Dobzinski, Michael Schapira |
| 2006 | Improved embeddings of graph metrics into random trees. | Kedar Dhamdhere, Anupam Gupta, Harald Rcke |
| 2006 | Matrix approximation and projective clustering via volume sampling. | Amit Deshpande, Luis Rademacher, Santosh S. Vempala, Grant Wang |
| 2006 | Finding nucleolus of flow game. | Xiaotie Deng, Qizhi Fang, Xiaoxun Sun |
| 2006 | Trading off space for passes in graph streaming problems. | Camil Demetrescu, Irene Finocchi, Andrea Ribichini |
| 2006 | Combination can be hard: approximability of the unique coverage problem. | Erik D. Demaine, Mohammad Taghi Hajiaghayi, Uriel Feige, Mohammad R. Salavatipour |
| 2006 | An algorithmic Friedman--Pippenger theorem on tree embeddings and applications to routing. | Domingos Dellamonica Jr., Yoshiharu Kohayakawa |
| 2006 | Four point conditions and exponential neighborhoods for symmetric TSP. | Vladimir G. Deineko, Bettina Klinz, Gerhard J. Woeginger |
| 2006 | Robbing the bandit: less regret in online geometric optimization against an adaptive adversary. | Varsha Dani, Thomas P. Hayes |
| 2006 | Ordering by weighted number of wins gives a good ranking for weighted tournaments. | Don Coppersmith, Lisa Fleischer, Atri Rudra |
| 2006 | Bottleneck links, variable demand, and the tragedy of the commons. | Richard Cole, Yevgeniy Dodis, Tim Roughgarden |
| 2006 | Leontief economies encode nonzero sum two-player games. | Bruno Codenotti, Amin Saberi, Kasturi R. Varadarajan, Yinyu Ye |
| 2006 | On the competitive ratio of evaluating priced functions. | Ferdinando Cicalese, Eduardo Sany Laber |
| 2006 | Cache-oblivious dynamic programming. | Rezaul Alam Chowdhury, Vijaya Ramachandran |
| 2006 | Anisotropic surface meshing. | Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, Rephael Wenger |
| 2006 | On | Ke Chen |
| 2006 | On the tandem duplication-random loss model of genome rearrangement. | Kamalika Chaudhuri, Kevin C. Chen, Radu Mihaescu, Satish Rao |
| 2006 | The complexity of quantitative concurrent parity games. | Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger |
| 2006 | Directed metrics and directed graph partitioning problems. | Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2006 | A robust maximum completion time measure for scheduling. | Moses Charikar, Samir Khuller |