Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms

Edited by Moses Charikar

Preface and Acknowledgements

The papers in this volume were presented at the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, held January 17-19, 2010 in Austin, Texas. The Symposium was jointly sponsored by SIGACT (the ACM Special Interest Group on Algorithms and Computation Theory) and by the SIAM Activity Group on Discrete Mathematics.

The program committee accepted 135 submissions of the 445 that were submitted. Some accepted submissions were merged, resulting in 132 papers at the conference.  Papers were chosen based on originality, technical contribution, and relevance. The committee was helped immensely in this process by input from over 550 reviewers. We are very grateful to them for their help.

The submissions were not formally refereed, although a sincere attempt was made to verify the main claims and to provide detailed feedback to authors. It is expected that most of the accepted papers will appear subsequently (possibly in more complete form) in scientific journals.

The program committee awarded the Best Paper award to
An O(log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem, Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, and Amin Saberi.

The Best Student Paper award was given jointly to two papers:
A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs, Aaron Bernstein
An Online Scalable Algorithm for Average Flow Time in Broadcast Scheduling, Sungjin Im and Benjamin Moseley.

Three speakers were invited to give plenary talks at the conference: Emmanuel Candes, Cynthia Dwork, and Noam Nisan.

The program committee thanks all the authors for supporting the conference with their submissions. I thank David Johnson and Prasad Tetali for their advice throughout the process. I am grateful to Eddie Kohler for all his help with HotCRP, the software used to run the conference server. I thank Thomas Jablin and Hanjun Kim for their help with hosting the conference server at Princeton. I also thank Kirsten Wilden, Linda Thiel, and other members of the SIAM staff for their support.

Moses Charikar
SODA 2010 Program Committee chair

The SODA 2010 Program Committee 

Acknowledgments

The program committee thanks the following colleagues who generously gave their help and time to read the review SODA 2010 submissions.

Renew SIAM · Contact Us · Site Map · Join SIAM · My Account