Proceedings of the Sixteenth Annual ACM-Siam Symposium on Discrete Algorithms

The Symposium was jointly sponsored by the SIAM Activity Group on Discrete Mathematics and by SIGACT, the ACM Special Interest Group on Algorithms and Computation Theory. This volume contains 136 papers that were selected from a field of 491 submissions based on their originality, technical contribution, and relevance. The symposium and the papers focus on research topics related to efficient algorithms and data structures for discrete problems. In addition to the design of such methods and structures, the scope also includes their use, performance analysis, and the mathematical problems related to their development or limitations. Themes and application areas come primarily from Computer Science and Discrete Mathematics, but also include other areas of application areas such as Biology, Physics and Finance. combinatorics; combinatorial structures; communication networks; computational biology; computational physics; computational finance; computational geometry; computer graphics and computer vision; computer systems; cryptography and security; databases and information retrieval; discrete optimization; discrete probability; distributed algorithms; experimental algorithmics; graph drawing; graphs and networks; machine learning; mathematical programming; molecular computing; number theory and algebra; on-line problems; pattern matching and data compression; quantum computing; random structures; robotics; statistical inference; and symbolic computation. Although the papers were not formally refereed, every attempt was made to verify the main claims. Extended versions of many of these papers may appear later in more polished form in various scientific journals.