| 2005 | Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT. | Adi Avidor, Ido Berkovitch, Uri Zwick |
| 2005 | On the Minimum Load Coloring Problem. | Nitin Ahuja, Andreas Baltz, Benjamin Doerr, Ales Prvetiv, Anand Srivastav |
| 2005 | "Almost Stable" Matchings in the Roommates Problem. | David J. Abraham, Pter Bir, David F. Manlove |
| 2004 | Approximation Schemes for Deal Splitting and Covering Integer Programs with Multiplicity Constraints. | Hadas Shachnai, Oded Shmueli, Robert Sayegh |
| 2004 | More Powerful and Simpler Cost-Sharing Methods. | Paolo Penna, Carmine Ventre |
| 2004 | Stochastic Online Scheduling on Parallel Machines. | Nicole Megow, Marc Uetz, Tjark Vredeveld |
| 2004 | Minimum Sum Multicoloring on the Edges of Planar Graphs and Partial k-Trees. | Dniel Marx |
| 2004 | Approximation Algorithm for Directed Multicuts. | Yana Kortsarts, Guy Kortsarz, Zeev Nutov |
| 2004 | Approximation Algorithms for Mixed Fractional Packing and Covering Problems. | Klaus Jansen |
| 2004 | Pricing Network Edges to Cross a River. | Alexander Grigoriev, Stan P. M. van Hoesel, Anton F. van der Kraaij, Marc Uetz, Mustapha Bouhtou |
| 2004 | Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum Criteria. | Rajiv Gandhi, Magns M. Halldrsson, Guy Kortsarz, Hadas Shachnai |
| 2004 | Submodular Integer Cover and Its Application to Production Planning. | Toshihiro Fujito, Takatoshi Yabuta |
| 2004 | Joint Base Station Scheduling. | Thomas Erlebach, Riko Jacob, Mats Mihalk, Marc Nunkesser, Gbor Szab, Peter Widmayer |
| 2004 | This Side Up! | Leah Epstein, Rob van Stee |
| 2004 | Online Bin Packing with Resource Augmentation. | Leah Epstein, Rob van Stee |
| 2004 | Better Bounds for Minimizing SONET ADMs. | Leah Epstein, Asaf Levin |
| 2004 | A PTAS for Delay Minimization in Establishing Wireless Conference Calls. | Leah Epstein, Asaf Levin |
| 2004 | Approximation Algorithms for Spreading Points. | Sergio Cabello |
| 2004 | Universal Bufferless Routing. | Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas |
| 2004 | Priority Algorithms for Graph Optimization Problems. | Allan Borodin, Joan Boyar, Kim S. Larsen |
| 2004 | A 5/4-Approximation Algorithm for Biconnecting a Graph with a Given Hamiltonian Path. | Davide Bil, Guido Proietti |
| 2004 | Online Packet Switching. | Yossi Azar |
| 2004 | Order-Preserving Transformations and Greedy-Like Algorithms. | Spyros Angelopoulos |
| 2004 | Deterministic Monotone Algorithms for Scheduling on Related Machines. | Pasquale Ambrosio, Vincenzo Auletta |
| 2004 | Strong Colorings of Hypergraphs. | Geir Agnarsson, Magns M. Halldrsson |