| 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 | Lower bound for sparse Euclidean spanners. | Pankaj K. Agarwal, Yusu Wang, Peng Yin |
| 2005 | An optimal dynamic interval stabbing-max data structure? | Pankaj K. Agarwal, Lars Arge, Ke Yi |
| 2005 | Collecting correlated information from a sensor network. | Micah Adler |
| 2005 | Popular matchings. | David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn |
| 2004 | Approximating the two-level facility location problem via a quasi-greedy approach. | Jiawei Zhang |
| 2004 | Family trees: an ordered dictionary with optimal congestion, locality, degree, and search time. | Kevin C. Zatloukal, Nicholas J. A. Harvey |
| 2004 | Detecting short directed cycles using rectangular matrix multiplication and dynamic programming. | Raphael Yuster, Uri Zwick |
| 2004 | Optimal space lower bounds for all frequency moments. | David P. Woodruff |
| 2004 | How random is the human genome? | Peter Winkler |
| 2004 | Approximation schemes for Metric Bisection and partitioning. | Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon |
| 2004 | Graph decomposition and a greedy algorithm for edge-disjoint paths. | Kasturi R. Varadarajan, Ganesh Venkataraman |
| 2004 | Tabulation based 4-universal hashing with applications to second moment estimation. | Mikkel Thorup, Yin Zhang |
| 2004 | Correlation Clustering: maximizing agreements via semidefinite programming. | Chaitanya Swamy |
| 2004 | Facility location with Service Installation Costs. | David B. Shmoys, Chaitanya Swamy, Retsef Levi |
| 2004 | The maximum latency of selfish routing. | Tim Roughgarden |
| 2004 | Multicommodity facility location. | R. Ravi, Amitabh Sinha |
| 2004 | Minimum moment Steiner trees. | Wangqi Qiu, Weiping Shi |
| 2004 | Buffer minimization using max-coloring. | Sriram V. Pemmaraju, Rajiv Raman, Kasturi R. Varadarajan |
| 2004 | Tight bounds for the partial-sums problem. | Mihai Patrascu, Erik D. Demaine |
| 2004 | Approximate local search in combinatorial optimization. | James B. Orlin, Abraham P. Punnen, Andreas S. Schulz |
| 2004 | Hole and antihole detection in graphs. | Stavros D. Nikolopoulos, Leonidas Palios |
| 2004 | The directed circular arrangement problem. | Joseph Naor, Roy Schwartz |
| 2004 | Caching queues in memory buffers. | Rajeev Motwani, Dilys Thomas |
| 2004 | The power of basis selection in fourier sampling: hidden subgroup problems in affine groups. | Cristopher Moore, Daniel N. Rockmore, Alexander Russell, Leonard J. Schulman |