| 2004 | Tiling a Polygon with Two Kinds of Rectangles. | Eric Rmila |
| 2004 | Efficient IP Table Lookup via Adaptive Stratified Trees with Selective Reconstructions. | Marco Pellegrini, Giordano Fusco |
| 2004 | On Adaptive Integer Sorting. | Anna Pagh, Rasmus Pagh, Mikkel Thorup |
| 2004 | Fast Multipoint Evaluation of Bivariate Polynomials. | Michael Nsken, Martin Ziegler |
| 2004 | Maximum Matchings in Planar Graphs via Gaussian Elimination. | Marcin Mucha, Piotr Sankowski |
| 2004 | Solving Geometric Covering Problems by Data Reduction. | Steffen Mecke, Dorothea Wagner |
| 2004 | Flows on Few Paths: Algorithms and Lower Bounds. | Maren Martens, Martin Skutella |
| 2004 | On the Stability of Multiple Partner Stable Marriages with Ties. | Varun S. Malhotra |
| 2004 | Beyond Optimal Play in Two-Person-Zerosum Games. | Ulf Lorenz |
| 2004 | Load Balancing in Hypercubic Distributed Hash Tables with Heterogeneous Processors. | Junning Liu, Micah Adler |
| 2004 | Equivalence of Search Capability Among Mobile Guards with Various Visibilities. | Jae-Ha Lee, Sang-Min Park, Kyung-Yong Chwa |
| 2004 | Multi-word Atomic Read/Write Registers on Multiprocessor Systems. | Andreas Larsson, Anders Gidenstam, Phuong Hoai Ha, Marina Papatriantafilou, Philippas Tsigas |
| 2004 | Seeking a Vertex of the Planar Matching Polytope in NC. | Raghav Kulkarni, Meena Mahajan |
| 2004 | Radio Network Clustering from Scratch. | Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer |
| 2004 | On Rectangular Cartograms. | Marc J. van Kreveld, Bettina Speckmann |
| 2004 | Approximate Unions of Lines and Minkowski Sums. | Marc J. van Kreveld, A. Frank van der Stappen |
| 2004 | Fast 3-Coloring Triangle-Free Planar Graphs. | Lukasz Kowalik |
| 2004 | Approximation of Rectangle Stabbing and Interval Stabbing Problems. | Sofia Kovaleva, Frits C. R. Spieksma |
| 2004 | Stable Minimum Storage Merging by Symmetric Comparisons. | Pok-Son Kim, Arne Kutzner |
| 2004 | Classroom Examples of Robustness Problems in Geometric Computations. | Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, Chee-Keng Yap |
| 2004 | Algorithmic Aspects of Web Search Engines. | Monika Henzinger |
| 2004 | Approximate Parameterized Matching. | Carmit Hazay, Moshe Lewenstein, Dina Sokol |
| 2004 | An Approximation Algorithm for Maximum Triangle Packing. | Refael Hassin, Shlomi Rubinstein |
| 2004 | Approximation Algorithms for Quickest Spanning Tree Problems. | Refael Hassin, Asaf Levin |
| 2004 | Negotiation-Range Mechanisms: Coalition-Resistant Markets. | Rica Gonen |