| 2008 | More Robust Hashing: Cuckoo Hashing with a Stash. | Adam Kirsch, Michael Mitzenmacher, Udi Wieder |
| 2008 | Better and Simpler Approximation Algorithms for the Stable Marriage Problem. | Zoltn Kirly |
| 2008 | An Optimal Incremental Algorithm for Minimizing Lateness with Rejection. | Samir Khuller, Julin Mestre |
| 2008 | Two-Stage Robust Network Design with Exponential Scenarios. | Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni, Mohammad R. Salavatipour |
| 2008 | Improved Competitive Performance Bounds for CIOQ Switches. | Alexander Kesselman, Kirill Kogan, Michael Segal |
| 2008 | Path Minima in Incremental Unrooted Trees. | Haim Kaplan, Nira Shafrir |
| 2008 | Oblivious Randomized Direct Search for Real-Parameter Optimization. | Jens Jgerskpper |
| 2008 | On the Complexity of Optimal Hotlink Assignment. | Tobias Jacobs |
| 2008 | Relative Convex Hulls in Semi-dynamic Subdivisions. | Mashhood Ishaque, Csaba D. Tth |
| 2008 | Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison. | Benjamin Hiller, Tjark Vredeveld |
| 2008 | Locality and Bounding-Box Quality of Two-Dimensional Space-Filling Curves. | Herman J. Haverkort, Freek van Walderveen |
| 2008 | Range Medians. | Sariel Har-Peled, S. Muthukrishnan |
| 2008 | RFQ: Redemptive Fair Queuing. | Ajay Gulati, Peter J. Varman |
| 2008 | An Optimal Dynamic Spanner for Doubling Metric Spaces. | Lee-Ad Gottlieb, Liam Roditty |
| 2008 | The Partial Augment-Relabel Algorithm for the Maximum Flow Problem. | Andrew V. Goldberg |
| 2008 | Faster Swap Edge Computation in Minimum Diameter Spanning Trees. | Beat Gfeller |
| 2008 | Fitting a Step Function to a Point Set. | Herv Fournier, Antoine Vigneron |
| 2008 | Faster Steiner Tree Computation in Polynomial-Space. | Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch |
| 2008 | The Complexity of Sorting with Networks of Stacks and Queues. | Stefan Felsner, Martin Pergel |
| 2008 | Edge Coloring and Decompositions of Weighted Graphs. | Uriel Feige, Mohit Singh |
| 2008 | Succinct Representations of Arbitrary Graphs. | Arash Farzan, J. Ian Munro |
| 2008 | Improved Randomized Results for That Interval Selection Problem. | Leah Epstein, Asaf Levin |
| 2008 | Selfish Bin Packing. | Leah Epstein, Elena Kleiman |
| 2008 | Improved Approximation Algorithms for Relay Placement. | Alon Efrat, Sndor P. Fekete, Poornananda R. Gaddehosur, Joseph S. B. Mitchell, Valentin Polishchuk, Jukka Suomela |
| 2008 | Detecting Regular Visit Patterns. | Bojan Djordjevic, Joachim Gudmundsson, Anh Pham, Thomas Wolle |