List of accepted papers for SODA 2009: Jeff Edmonds and Kirk Pruhs. Scalably Scheduling Processes with Arbitrary Speedup Curves Zdenek Dvorak, Ken-ichi Kawarabayashi and Robin Thomas. Three-coloring triangle-free planar graphs in linear time Amin Coja-Oghlan, Colin Cooper and Alan Frieze. An Efficient Sparse Regularity Concept Toniann Pitassi and Nathan Segerlind. Exponential Lower Bounds and Integrality Gaps for Lovasz-Schrijver Procedures Uriel Feige and Noga Alon. On the power of two, three and four probes Siu-Wing Cheng and Man-Kwun Chiu. Dimension detection via slivers Ioannis Caragiannis, Jason Covey, Michal Feldman, Christopher Homan, Christos Kaklamanis, Nikos Karanikolas, Ariel Procaccia and Jeffrey Rosenschein. On the Approximability of Dodgson and Young Elections David Eppstein and Elena Mumford. Self-overlapping Curves Revisited Jiri Matousek, Martin Tancer and Uli Wagner. Hardness of embedding simplicial complexes in R^d MohammadTaghi Hajiaghayi and Mohammad H. Bateni. The Assignment Problem in Content Distribution Networks: Unsplittable Hard-Capacitated Facility Location Sudipto Guha, Kamesh Munagala and Peng Shi. Approximation Algorithms for Restless Bandit Problems Vida Dujmovic, John Howat and Pat Morin. Biased Range Trees Zeev Nutov. An almost O(log k)-approximation for k-connected subgraphs David Eppstein, Michael Goodrich and Darren Strash. Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings Moran Feldman, Guy Kortsarz and Zeev Nutov. Improved Approximating Algorithms for Directed Steiner Forest Haim Kaplan, Natan Rubin and Micha Sharir. Line Transversals of Convex Polyhedra in S^3 Mikkel Thorup. String Hashing for Linear Probing Anthony Man-Cho So. Improved Approximation Bound for Quadratic Optimization Problems with Orthogonality Constraints Ken-ichi Kawarabayashi and Yusuke Kobayashi. Algorithms for Finding an Induced Cycle in Planar Graphs Stephan Thomasse. A quadratic kernel for feedback vertex set Martin Dietzfelbinger and Ulf Schellbach. On risks of using cuckoo hashing with simple universal hash classes Michael Molloy and Bruce Reed. Asymptotically optimal frugal colouring Omid Amini, Louis Esperet and Jan van den Heuvel. A Unified Approach to Distance-Two Colouring of Planar Graphs Nikhil Bansal and Ho-Leung Chan. Weighted flow time does not admit O(1)-competitive algorithms Paolo Ferragina, Igor Nitto and Rossano Venturini. On the bit-complexity of Lempel-Ziv compression Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld and Rocco Servedio. Testing Halfspaces Ke Yi and Qin Zhang. Multi-Dimensional Online Tracking Krishnendu Chatterjee, Luca de Alfaro and Thomas Henzinger. Termination Criteria for Solving Concurrent Safety and Reachability Games Philip Klein, Shay Mozes and Oren Weimann. Shortest Paths in Directed Planar Graphs with Negative Lengths: a linear-space O(n log^2 n)-time algorithm Ioannis Caragiannis. Efficient coordination mechanisms for unrelated machine scheduling Daniel Marx. Approximating fractional hypertree width Bodo Manthey and Heiko Roeglin. Improved Smoothed Analysis of the k-Means Method Christos Boutsidis, Michael Mahoney and Petros Drineas. An Improved Approximation Algorithm for the Column Subset Selection Problem Michael Drmota and Wojciech Szpankowski. (Un)Expected Behavior of Digital Search Tree Profile Nikhil Bansal, Zachary Friggstad, Rohit Khandekar and Mohammad Salavatipour. A logarithmic approximation for the unsplittable flow on line graphs Edith Cohen, Nick Duffield, Haim Kaplan, Carsten Lund and Mikkel Thorup. Variance-optimal sampling-based estimation of subset sums Sergio Cabello. Finding shortest contractible cycles in embedded graphs Khaled Elbassioni, Rajiv Raman, Saurabh Ray and Rene Sitters. On the approximability of the maximum feasible subsystem problem with 0/1-coefficients S. Charles Brubaker. Clustering on Noisy Mixtures Ashish Goel, Michael Kapralov and Sanjeev Khanna. Perfect matchings via uniform sampling in regular bipartite graphs David Karger and Debmalya Panigrahi. An tilde{O}(m) algorithm for constructing a cactus of an undirected graph Joel Tropp. Efficient Algorithms for Column Subset Selection Gabriel Nivasch. Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations Raphael Yuster. Efficient algorithms on sets of permutations, dominance, and real-weighted APSP Gabor Tardos and Ehsan Amiri. High rate fingerprinting codes and the fi ngerprinting capacity Yury Person and Mathias Schacht. Almost all hypergraphs without Fano planes are bipartite Amr Elmasry. Pairing Heaps with O(loglog n}) decrease Cost Haim Kaplan and Uri Zwick. A simpler implementation and analysis of Chazelle's Soft Heaps Mikkel Thorup, Uri Zwick and Omid Madani. Discounted Deterministic Markov Decision Processes and Discounted All-Pairs Shortest Paths Alon Shalita and Uri Zwick. Efficient algorithms for the 2-gathering problem david cohen-steiner, Herbert Edelsbrunner, John Harer and Dmitriy Morozov. Persistent Homology for Kernels, Images, and Cokernels Fedor Fomin, Petr Golovach, Daniel Lokshtanov and Saket Saurabh. Clique-width: On the Price of Generality Parinya Chalermsook and Julia Chuzhoy. Maximum Independent Set of Rectangles Brendan Nagle, Annika Poerschke, Vojtech R?dl and Mathias Schacht. On Algorithmic Hypergraph Regularity Robi Krauthgamer, Seffi Naor and Roy Schwartz. Partitioning Graphs into Balanced Components Nikhil Bansal, Ho-Leung Chan and Kirk Pruhs. Speed Scaling with an Arbitrary Power Function Zdenek Dvorak, Daniel Kral and Robin Thomas. Coloring triangle-free graphs on surfaces Amitabh Basu, Pierre Bonami, gerard cornuejols and Francois Margot. On the Relative Strength of Split, Triangle and Quadrilateral Cuts (Extended Abstract) Raphael Clifford, Klim Efremenko, Ely Porat and Amir Rothschild. From coding theory to efficient pattern matching Ramesh Hariharan and Anand Bhalgat. Fast Edge Orientation for Unweighted Graphs Viswanath Nagarajan and Maxim Sviridenko. On the Maximum Quadratic Assignment Problem Bernard Chazelle. Natural Algorithms Timothy M. Chan. Comparison-Based, Time-Space Lower Bounds for Selection Peyman Afshani and Timothy M. Chan. Optimal Halfspace Range Reporting in Three Dimensions Justin Salez and Devavrat Shah. Optimality of Belief Propagation for Random Assignment Problem Ping Li. Compressed Counting Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane and Mihai Patrascu. The Geometry of Binary Search Trees Satoru Iwata and James Orlin. A Simple Combinatorial Algorithm for Submodular Function Minimization Prasad Raghavendra and David Steurer. Towards Computing the Grothendieck Constant Mordecai J. Golin, Xiaoming Xu and Jiajin Yu. A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding Ken-ichi Kawarabayashi, Erik Demaine and Mohammad Taghi Haijaghayi. Additive Approximation Algorithms for List-Coloring Minor-Closed Class of Graphs Ken-ichi Kawarabayashi and Bruce Reed. A Nearly Linear Time Algorithm For The Half Integral Parity Disjoint Paths Packing Problem Michel Goemans, Nicholas J.A. Harvey, Satoru Iwata and Vahab Mirrokni. Approximating Submodular Functions Everywhere Baharak Rastegari, Anne Condon and Kevin Leyton-Brown. Stepwise Randomized Combinatorial Auctions Achieve Revenue Monotonicity Ilia Binder and Mark Braverman. The complexity of simulating Brownian Motion Prosenjit Bose, Eric Chen, Meng He, Anil Maheshwari and Pat Morin. Succinct Geometric Indexes Supporting Point Location Queries Djamal Belazzougui, Paolo Boldi, Rasmus Pagh and Sebastiano Vigna. Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses Alexandr Andoni, Piotr Indyk, Robi Krauthgamer and Huy Nguyen. Approximate Nearest Neighbors for Affine Subspaces Queries Marcin Bienkowski, Marek Chrobak, Christoph D?rr, Mathilde Hurand, Artur Jez, ?ukasz Je? and Grzegorz Stachowiak. Collecting Weighted Items from a Dynamic Queue Boaz Barak, Moritz Hardt and Satyen Kale. The Uniform Hardcore Lemma via Approximate Bregman Projections Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David Woodruff. Transitive-Closure Spanners Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant and Paul Valiant. On the Complexity of Nash Equilibria of Action-Graph Games Alexandr Andoni, Piotr Indyk and Robi Krauthgamer. Overcoming the L_1 Non-Embeddability Barrier: Algorithms for Product Metrics Parikshit Gopalan and Jaikumar Radhakrishnan. Finding repeats in a data-stream James Aspnes and Keren Censor. Approximate Shared-Memory Counting Despite a Strong Adversary Ittai Abraham, Yair Bartal and Ofer Neiman. On Low Dimensional Local Embeddings Michael Bender, Jeremy Fineman and Seth Gilbert. Online Topological Ordering William Johnson and Assaf Naor. The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite Klaus Jansen. Parameterized approximation scheme for the multiple knapsack problem Markus Chimani, Carsten Gutwenger, Petra Mutzel and Christian Wolf. Inserting a Vertex into a Planar Graph Spyros Angelopoulos and Pascal Schweitzer. Paging and List Update under Bijective Analysis Adrian Dumitrescu, Csaba Toth and G Xu. On stars and Steiner stars. II Benjamin Aminof, Orna Kupferman and Robby Lampert. Reasoning about Online Algorithms with Weighted Automata Amin Coja-Oghlan, Uriel Feige, Alan Frieze, Michael Krivelevich and Dan Vilenchik. On smoothed k-CNF formulas and the Walksat algorithm Elad Hazan and Robi Krauthgamer. How hard is it to approximate the best Nash equilibrium? Ashish Goel, Sanjeev Khanna and Brad Null. The Ratio Index for Budgeted Learning, with Applications Serge Gaspers and Gregory Sorkin. A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between Greg Aloupis, Jean Cardinal, Sebastien Collette, Stefan Langerman, David Orden and Pedro Ramos. Decomposition of Multiple Coverings into More Parts Edith Elkind and Dmitrii Pasechnik. Computing the nucleolus of weighted voting games Konstantinos Panagiotou and Angelika Steger. Maximum Biconnected Subgraphs of Random Planar Graphs Ken-ichi Kawarabayashi and Bojan Mohar. List-Color-Critical Graphs on a Fixed Surface Ariel Kulik, Hadas Shachnai and Tami Tamir. Maximizing Submodular Set Functions Subject to Multiple Linear Constraints Marcel R. Ackermann and Johannes Bl?mer. Coresets and Approximate Clustering for Bregman Divergences Benjamin Moseley and Chandra Chekuri. Online Scheduling to Minimize the Maximum Delay Factor Maria-Florina Balcan, Avrim Blum and Anupam Gupta. Approximate Clustering without the Approximation Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica and Kunal Talwar. Secretary Problems: Weights and Discounts Maria-Florina Balcan, Avrim Blum and Yishay Mansour. Improved Equilibria via Public Service Advertising Yusu Wang, Kevin Buchin and Maike Buchin. Exact Algorithm for Partial Curve Matching via the Frechet Distance Pankaj K Agarwal, R Sharathkumar and Hai Yu. Approximate Euclidean Shortest Path amid convex obstacles Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld and Elad Verbin. Sorting and Selection in Posets Sergi Elizalde and Peter Winkler. Sorting by Placement and Shift Ryan O'Donnell and Yi Wu. 3-Bit Dictator Testing: 1 vs. 5/8 Siddharth Barman and Shuchi Chawla. Packing multiway cuts in graphs Frederic Chazal, Leonidas Guibas, Steve Oudot and Primoz Skraba. Analysis of Scalar Fields over Point Cloud Data Frederic Magniez, Ashwin Nayak, Peter Richter and Miklos Santha. On the hitting times of quantum versus random walks Elad Hazan and Satyen Kale. Better Algorithms for Benign Bandits Florin Constantin, Jon Feldman, S Muthukrishnan and Martin Pal. An Online Mechanism for Ad Slot Reservations with Cancellations Colin Cooper and Alan Frieze. The cover time of random geometric graphs Lorenz Minder and Alistair Sinclair. The extended k-tree algorithm Misha Belkin, jian sun and Yusu Wang. Constructing Laplace operators from Point Clouds Anirban Dasgupta, Arpita Ghosh, Hamid Nazerzadeh and Prabhakar Raghavan. Online story scheduling for web advertising Mohsen Bayati, Andrea Montanari and Amin Saberi. Generating Random Graphs with Large Girth Florian Diedrich and Klaus Jansen. Improved Approximation Algorithms for Scheduling with Fixed Jobs Aurore Amaudruz and Christina Fragouli. Combinatorial Algorithms for Wireless Information Flow Ran Duan and Seth Pettie. Fast Algorithms for (Max,Min)-Matrix Multiplication and Bottleneck Shortest Paths Mehmet Begen and Maurice Queyranne. Appointment Scheduling with Discrete Random Durations Navin Goyal, Luis Rademacher and Santosh Vempala. Expanders via Random Spanning Trees Aaron Williams. Loopless Generation of Multiset Permutations using a Constant Number of Variables by Prefix Shifts Ran Duan and Seth Pettie. Dual-Failure Distance and Connectivity Oracles david gamarnik and Dimitry Katz. Sequential cavity method for computing limits of the log-partition function for Alexander Golynski. Lower Bounds for Succinct Data Structures Umang Bhaskar, Lisa Fleischer, Darrell Hoy and Chien-Chung Huang. Equilibria of Collusive Flow Games are not Unique Sam Greenberg, Amanda Pascoe and Dana Randall. Sampling Biased Lattice Configurations using Exponential Metrics Beno?t Hudson, Gary Miller, Todd Phillips and Don Sheehy. Size Complexity of Volume Meshes vs. Surface Meshes Yury Lifshits and Shengyu Zhang. Combinatorial Algorithms for Nearest Neighbors, Near-Duplicates and Small-World Design.