| 2010 | A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover. | Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy |
| 2010 | Towards the Randomized k-Server Conjecture: A Primal-Dual Approach. | Nikhil Bansal, Niv Buchbinder, Joseph Naor |
| 2010 | Lower Bounds for Sparse Recovery. | Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff |
| 2010 | A 1.43-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model. | Bahman Bahmani, Aranyak Mehta, Rajeev Motwani |
| 2010 | Monotonicity in Bargaining Networks. | Yossi Azar, Nikhil R. Devanur, Kamal Jain, Yuval Rabani |
| 2010 | An Improved Competitive Algorithm for Reordering Buffer Management. | Noa Avigdor-Elgrabli, Yuval Rabani |
| 2010 | An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem. | Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi |
| 2010 | Improved Approximation Algorithms for the Minimum Latency Problem via Prize-Collecting Strolls. | Aaron Archer, Anna Blasiak |
| 2010 | Testing Planarity of Partially Embedded Graphs. | Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vt Jelnek, Jan Kratochvl, Maurizio Patrignani, Ignaz Rutter |
| 2010 | Near-Optimal Sublinear Time Algorithms for Ulam Distance. | Alexandr Andoni, Huy L. Nguyen |
| 2010 | Lower Bounds for Edit Distance and Product Metrics via Poincar-Type Inequalities. | Alexandr Andoni, T. S. Jayram, Mihai Patrascu |
| 2010 | Solving MAX-r-SAT Above a Tight Lower Bound. | Noga Alon, Gregory Z. Gutin, Eun Jung Kim, Stefan Szeider, Anders Yeo |
| 2010 | Correlation Robust Stochastic Optimization. | Shipra Agrawal, Yichuan Ding, Amin Saberi, Yinyu Ye |
| 2010 | Streaming Algorithms for Extent Problems in High Dimensions. | Pankaj K. Agarwal, R. Sharathkumar |
| 2010 | Testing Monotone Continuous Distributions on High-dimensional Real Cubes. | Michal Adamaszek, Artur Czumaj, Christian Sohler |
| 2010 | Highway Dimension, Shortest Paths, and Provably Efficient Algorithms. | Ittai Abraham, Amos Fiat, Andrew V. Goldberg, Renato Fonseca F. Werneck |
| 2010 | Shape Replication through Self-Assembly and RNase Enzymes. | Zachary Abel, Nadia M. Benbernou, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin Y. Flatland, Scott Duke Kominers, Robert Schweller |
| 2009 | Efficient algorithms on sets of permutations, dominance, and real-weighted APSP. | Raphael Yuster |
| 2009 | Multi-dimensional online tracking. | Ke Yi, Qin Zhang |
| 2009 | Loopless generation of multiset permutations using a constant number of variables by prefix shifts. | Aaron Williams |
| 2009 | Column subset selection, matrix factorization, and eigenvalue optimization. | Joel A. Tropp |
| 2009 | String hashing for linear probing. | Mikkel Thorup |
| 2009 | A quadratic kernel for feedback vertex set. | Stphan Thomass |
| 2009 | Probability, algorithms and complexity. | Volker Strassen |
| 2009 | Improved approximation bound for quadratic optimization problems with orthogonality constraints. | Anthony Man-Cho So |