| 2009 | Fast edge orientation for unweighted graphs. | Anand Bhalgat, Ramesh Hariharan |
| 2009 | A new approach to incremental topological ordering. | Michael A. Bender, Jeremy T. Fineman, Seth Gilbert |
| 2009 | Constructing Laplace operator from point clouds in | Mikhail Belkin, Jian Sun, Yusu Wang |
| 2009 | Monotone minimal perfect hashing: searching a sorted table with | Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna |
| 2009 | Appointment scheduling with discrete random durations. | Mehmet A. Begen, Maurice Queyranne |
| 2009 | Generating random graphs with large girth. | Mohsen Bayati, Andrea Montanari, Amin Saberi |
| 2009 | Assignment problem in content distribution networks: unsplittable hard-capacitated facility location. | MohammadHossein Bateni, MohammadTaghi Hajiaghayi |
| 2009 | On the relative strength of split, triangle and quadrilateral cuts. | Amitabh Basu, Pierre Bonami, Grard Cornujols, Franois Margot |
| 2009 | Packing multiway cuts in capacitated graphs. | Siddharth Barman, Shuchi Chawla |
| 2009 | The uniform hardcore lemma via approximate Bregman projections. | Boaz Barak, Moritz Hardt, Satyen Kale |
| 2009 | A logarithmic approximation for unsplittable flow on line graphs. | Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, Mohammad R. Salavatipour |
| 2009 | Speed scaling with an arbitrary power function. | Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs |
| 2009 | Weighted flow time does not admit O(1)-competitive algorithms. | Nikhil Bansal, Ho-Leung Chan |
| 2009 | Improved equilibria via public service advertising. | Maria-Florina Balcan, Avrim Blum, Yishay Mansour |
| 2009 | Approximate clustering without the approximation. | Maria-Florina Balcan, Avrim Blum, Anupam Gupta |
| 2009 | Secretary problems: weights and discounts. | Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, Kunal Talwar |
| 2009 | Approximate shared-memory counting despite a strong adversary. | James Aspnes, Keren Censor |
| 2009 | Paging and list update under bijective analysis. | Spyros Angelopoulos, Pascal Schweitzer |
| 2009 | Approximate line nearest neighbor in high dimensions. | Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen |
| 2009 | Overcoming the | Alexandr Andoni, Piotr Indyk, Robert Krauthgamer |
| 2009 | High rate fingerprinting codes and the fingerprinting capacity. | Ehsan Amiri, Gbor Tardos |
| 2009 | Reasoning about online algorithms with weighted automata. | Benjamin Aminof, Orna Kupferman, Robby Lampert |
| 2009 | A unified approach to distance-two colouring of planar graphs. | Omid Amini, Louis Esperet, Jan van den Heuvel |
| 2009 | Combinatorial algorithms for wireless information flow. | Aurore Amaudruz, Christina Fragouli |
| 2009 | Decomposition of multiple coverings into more parts. | Greg Aloupis, Jean Cardinal, Sbastien Collette, Stefan Langerman, David Orden, Pedro Ramos |