• 
  J. Ian Munro (Ed.): Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004. SIAM 2004 ISBN 0-89871-558-X

Session 1A

• 
  Richard F. Geary, Rajeev Raman, Venkatesh Raman: Succinct ordinal trees with level-ancestor queries. 1-10
• 
  Daniel K. Blandford, Guy E. Blelloch: Compact representations of ordered sets. 11-19
• 
  Mihai Patrascu, Erik D. Demaine: Tight bounds for the partial-sums problem. 20-29
• 
  Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, Ayellet Tal: The Bloomier filter: an efficient data structure for static support lookup tables. 30-39
• 
  Ran Mendelson, Mikkel Thorup, Uri Zwick: Meldable RAM priority queues and minimum directed spanning trees. 40-48

Session 1B

• 
  Harold N. Gabow, Shuxin Nie: Finding a long directed cycle. 49-58
• 
  Manuel Bodirsky, Denys Duchier, Joachim Niehren, Sebastian Miele: A new algorithm for normal dominance constraints. 59-67
• 
  Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch: Rank-maximal matchings. 68-75
• 
  Jon M. Kleinberg, Mark Sandler, Aleksandrs Slivkins: Network failure detection and graph connectivity. 76-85
• 
  Joseph Naor, Roy Schwartz: The directed circular arrangement problem. 86-95

Session 1C

• 
  Thomas P. Hayes, Eric Vigoda: Variable length path coupling. 103-110
• 
  David Gamarnik: Linear phase transition in random linear constraint satisfaction problems. 111-120
• 
  Krishnendu Chatterjee, Marcin Jurdzinski, Thomas A. Henzinger: Quantitative stochastic parity games. 121-130
• 
  Guy Kindler, Dan Romik: On distributions computable by random walks on graphs. 131-138
• 
  Dimitris Achlioptas, Paul Beame, Michael Molloy: Exponential bounds for DPLL below the satisfiability threshold. 139-140

Session 2: Invited plenary abstract

• 
  Bernard Chazelle: Who says you have to look at the input? The brave new world of sublinear computing. 141

Session 3A

• 
  April Rasala Lehman, Eric Lehman: Complexity classification of network information flow problems. 142-150
• 
  Don Coppersmith, Ravi Kumar: An improved data stream algorithm for frequency moments. 151-156
• 
  Edith Cohen, Haim Kaplan: Efficient estimation algorithms for neighborhood variance and other moments. 157-166
• 
  David P. Woodruff: Optimal space lower bounds for all frequency moments. 167-175
• 
  Prasanna Ganesan, Gurmeet Singh Manku: Optimal routing in Chord. 176-185

Session 3B

• 
  José R. Correa, Claire Kenyon: Approximation schemes for multidimensional packing. 186-195
• 
  Nikhil Bansal, Maxim Sviridenko: New approximability and inapproximability results for 2-dimensional Bin Packing. 196-203
• 
  Klaus Jansen, Guochuan Zhang: On rectangle packing: maximizing benefits. 204-213
• 
  Leah Epstein, Rob van Stee: Optimal online bounded space multidimensional packing. 214-223
• 
  Amotz Bar-Noy, Richard E. Ladner, Tami Tamir: Windows scheduling as a restricted version of Bin Packing. 224-233

Session 3C

• 
  Harold N. Gabow: Special edges, and approximating the smallest directed k-edge connected spanning subgraph. 234-243
• 
  Geir Agnarsson, Magnús M. Halldórsson: On colorings of squares of outerplanar graphs. 244-253
• 
  Raphael Yuster, Uri Zwick: Detecting short directed cycles using rectangular matrix multiplication and dynamic programming. 254-260
• 
  Yuval Emek, David Peleg: Approximating Minimum Max-Stretch spanning Trees on unweighted graphs. 261-270
• 
  Surender Baswana, Sandeep Sen: Approximate distance oracles for unweighted graphs in Õ(n²) time. 271-280

Session 4A

• 
  Erik D. Demaine, John Iacono, Stefan Langerman: Retroactive data structures. 281-290
• 
  Gianni Franceschini: Proximity Mergesort: optimal in-place sorting in the cache-oblivious model. 291-299
• 
  James Allen Fill, Svante Janson: The number of bit comparisons used by Quicksort: an average-case analysis. 300-307
• 
  Kevin C. Zatloukal, Nicholas J. A. Harvey: Family trees: an ordered dictionary with optimal congestion, locality, degree, and search time. 308-317
• 
  Baruch Awerbuch, Christian Scheideler: The hyperring: a low-congestion deterministic data structure for distributed environments. 318-327

Session 4B

• 
  Kazuo Iwama, Suguru Tamaki: Improved upper bounds for 3-SAT. 328
• 
  Daniel Král: Locally satisfiable formulas. 330-339
• 
  Henry C. Lin, Tim Roughgarden, Éva Tardos: A stronger bound on Braess's Paradox. 340-341
• 
  R. Ravi, Amitabh Sinha: Multicommodity facility location. 342-349
• 
  Jason McCullough, Eric Torng: SRPT optimally utilizes faster machines to minimize flow time. 350-358

Session 4C

• 
  Michael Elkin: A faster distributed protocol for constructing a minimum spanning tree. 359-368
• 
  Camil Demetrescu, Stefano Emiliozzi, Giuseppe F. Italiano: Experimental analysis of dynamic all pairs shortest path algorithms. 369-378
• 
  Kasturi R. Varadarajan, Ganesh Venkataraman: Graph decomposition and a greedy algorithm for edge-disjoint paths. 379-380
• 
  Sashka Davis, Russell Impagliazzo: Models of greedy algorithms for graph problems. 381-390
• 
  Kathie Cameron, Elaine M. Eschen, Chính T. Hoàng, R. Sritharan: The list partition problem for graphs. 391-399

Session 5A

• 
  Gary L. Miller: A time efficient Delaunay refinement algorithm. 400-409
• 
  Deepak Bandyopadhyay, Jack Snoeyink: Almost-Delaunay simplices: nearest neighbor relations for imprecise points. 410-419
• 
  Eti Ezra, Micha Sharir: Output-sensitive construction of the union of triangles. 420-429
• 
  Timothy M. Chan: An optimal randomized algorithm for maximum Tukey depth. 430-436
• 
  Sándor P. Fekete, Marco E. Lübbecke, Henk Meijer: Minimizing the stabbing number of matchings, trees, and triangulations. 437-446

Session 5B

• 
  Conrado Martinez, Daniel Panario, Alfredo Viola: Adaptive sampling for quickselect. 447-455
• 
  Fabio Martinelli, Alistair Sinclair, Dror Weitz: Fast mixing for independent sets, colorings and other models on trees. 456-465
• 
  David Galvin, Prasad Tetali: Slow mixing of Glauber dynamics for the hard-core model on the hypercube. 466-467
• 
  René Beier, Berthold Vöcking: Probabilistic analysis of knapsack core algorithms. 468-477
• 
  Nayantara Bhatnagar, Dana Randall: Torpid mixing of simulated tempering on the Potts model. 478-487

Session 5C

• 
  Wangqi Qiu, Weiping Shi: Minimum moment Steiner trees. 488-495
• 
  Artur Czumaj, Michelangelo Grigni, Papa Sissokho, Hairong Zhao: Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs. 496-505
• 
  Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon: Approximation schemes for Metric Bisection and partitioning. 506-515
• 
  Pankaj K. Agarwal, Mark H. Overmars, Micha Sharir: Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks. 516-525
• 
  Chaitanya Swamy: Correlation Clustering: maximizing agreements via semidefinite programming. 526-527

Session 6: Invited plenary abstract

• 
  Raymond Laflamme: Quantum computing. 528

Session 7A

• 
  Erik D. Demaine, Thouis R. Jones, Mihai Patrascu: Interpolation search for non-independent data. 529-530
• 
  Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes, Shan Leung Maverick Woo: Dynamizing static algorithms, with applications to dynamic trees and history independence. 531-540
• 
  Rajeev Motwani, Dilys Thomas: Caching queues in memory buffers. 541-549
• 
  Ittai Abraham, Dahlia Malkhi, Oren Dobzinski: LAND: stretch (1 + epsilon) locality-aware networks for DHTs. 550-559
• 
  Kirsten Hildrum, John Kubiatowicz, Sean Ma, Satish Rao: A note on the nearest neighbor in growth-restricted metrics. 560-561

Session 7B

• 
  Sriram V. Pemmaraju, Rajiv Raman, Kasturi R. Varadarajan: Buffer minimization using max-coloring. 562-571
• 
  Nikhil Bansal: On minimizing the total flow time on multiple machines. 572-574
• 
  Benjamin Doerr: Matrix rounding and approximation. 575-576
• 
  Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor: A general approach to online network optimization problems. 577-586
• 
  James B. Orlin, Abraham P. Punnen, Andreas S. Schulz: Approximate local search in combinatorial optimization. 587-596

Session 7C

• 
  Jean-François Macq, Michel X. Goemans: Trade-offs on the location of the core node in a network. 597-604
• 
  Howard J. Karloff: On the convergence time of a path-vector protocol. 605-614
• 
  Mikkel Thorup, Yin Zhang: Tabulation based 4-universal hashing with applications to second moment estimation. 615-624
• 
  Markus Bläser: Approximate budget balanced mechanisms with low communication costs for the multicast cost-sharing problem. 625-626
• 
  Carlos Brito, Elias Koutsoupias, Shailesh Vaya: Competitive analysis of organization networks or multicast acknowledgement: how much to wait? 627-635

Session 8A

• 
  Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter: When indexing equals compression: experiments with compressing suffix arrays and applications. 636-645
• 
  Piotr Indyk: Approximate Nearest Neighbor under edit distance via product metrics. 646-650
• 
  Mihai Badoiu, Piotr Indyk: Fast approximate pattern matching with few indels via embeddings. 651-652
• 
  Frédérique Bassino, Julien Clément, Cyril Nicaud: Lyndon words with a fixed standard right factor. 653-654
• 
  Paolo Ferragina, Giovanni Manzini: Compression boosting in optimal linear time using the Burrows-Wheeler Transform. 655-663

Session 8B

• 
  Yair Bartal, Manor Mendel: Dimension reduction for ultrametrics. 664-665
• 
  Yair Bartal, Manor Mendel: Randomized k-server algorithms for growth-rate bounded graphs. 666-671
• 
  Michael Molloy: The pure literal rule threshold and cores in random hypergraphs. 672-681
• 
  Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun: Efficient algorithms for bichromatic separability. 682-690
• 
  Nicole Immorlica, David R. Karger, Maria Minkoff, Vahab S. Mirrokni: On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems. 691-700

Session 8C

• 
  Edith Elkind, Amit Sahai, Kenneth Steiglitz: Frugality in path auctions. 701-709
• 
  Tian-Shyr Dai, Yuh-Dauh Lyuu: An exact subexponential-time lattice algorithm for Asian options. 710-717
• 
  Stephen Eubank, V. S. Anil Kumar, Madhav V. Marathe, Aravind Srinivasan, Nan Wang: Structural and algorithmic aspects of massive social networks. 718-727
• 
  Steve Chien: A determinant-based algorithm for counting perfect matchings in a general graph. 728-735
• 
  Eyal Ackerman, Gill Barequet, Ron Y. Pinter: On the number of rectangular partitions. 736-745

Session 9A

• 
  René Beier, Artur Czumaj, Piotr Krysta, Berthold Vöcking: Computing equilibria for congestion games with (im)perfect information. 746-755
• 
  Venkatesan Guruswami, Piotr Indyk: Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates. 756-757
• 
  Mordecai J. Golin, Kin Keung Ma: Algorithms for infinite huffman-codes. 758-767
• 
  Ross M. McConnell: A certifying algorithm for the consecutive-ones property. 768-777
• 
  Cristopher Moore, Daniel N. Rockmore, Alexander Russell: Generic quantum Fourier transforms. 778-787

Session 9B

• 
  David Eppstein: Quasiconvex analysis of backtracking algorithms. 788-797
• 
  Robert Krauthgamer, James R. Lee: Navigating nets: simple algorithms for proximity search. 798-807
• 
  Jiawei Zhang: Approximating the two-level facility location problem via a quasi-greedy approach. 808-817
• 
  Jeff Edmonds, Kirk Pruhs: A maiden analysis of Longest Wait First. 818-827
• 
  Parinya Chalermsook, Jittat Fakcharoenphol, Danupon Nanongkai: A deterministic near-linear time algorithm for finding minimum cuts in planar graphs. 828-829

Session 9C

• 
  Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos: Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs. 830-839
• 
  Erik D. Demaine, Mohammad Taghi Hajiaghayi: Equivalence of local treewidth and linear local treewidth and its algorithmic applications. 840-849
• 
  Stavros D. Nikolopoulos, Leonidas Palios: Hole and antihole detection in graphs. 850-859
• 
  David Eppstein: Testing bipartiteness of geometric intersection graphs. 860-868
• 
  Loukas Georgiadis, Robert Endre Tarjan: Finding dominators revisited: extended abstract. 869-878

Session 10: Invited plenary abstract

• 
  Peter Winkler: How random is the human genome? 879

Session 11A

• 
  Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller: Complexities for generalized models of self-assembly. 880-889
• 
  Ho-Lin Chen, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, Pablo Moisset de Espanés: Invadable self-assembly: combining robustness with efficiency. 890-899
• 
  Ganeshkumar Ganapathy, Vijaya Ramachandran, Tandy Warnow: On contract-and-refine transformations between phylogenetic trees. 900-909
• 
  Tugkan Batu, Sampath Kannan, Sanjeev Khanna, Andrew McGregor: Reconstructing strings from random traces. 910-918
• 
  Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter, Steven Skiena, Firas Swidan: Improved bounds on sorting with length-weighted reversals. 919-928

Session 11B

• 
  Ernst Althaus, Friedrich Eisenbrand, Stefan Funke, Kurt Mehlhorn: Point containment in the integer hull of a polyhedron. 929-933
• 
  Michel X. Goemans, Jan Vondrák: Covering minimum spanning trees of random subgraphs. 934-941
• 
  Noga Alon, Asaf Shapira: A characterization of easily testable induced subgraphs. 942-951
• 
  Lap Chi Lau: Bipartite roots of graphs. 952-961
• 
  Anne Berry, Martin Charles Golumbic, Marina Lipshteyn: Two tricks to triangulate chordal probe graphs in polynomial time. 962-969

Session 11C

• 
  Ho-Leung Chan, Tak Wah Lam, Kar-Keung To: Non-migratory online deadline scheduling on multiprocessors. 970-979
• 
  Tim Roughgarden: The maximum latency of selfish routing. 980-981
• 
  Tracy Kimbrel, Baruch Schieber, Maxim Sviridenko: Minimizing migrations in fair multiprocessor scheduling of persistent tasks. 982-991
• 
  Marek Chrobak, Leszek Gasieniec, Dariusz R. Kowalski: The wake-up problem in multi-hop radio networks. 992-1000
• 
  Lisa Fleischer: A fast approximation scheme for fractional covering problems with variable upper bounds. 1001-1010

Session 12A

• 
  Samir Khuller, Yoo Ah Kim: On broadcasting in heterogenous networks. 1011-1020
• 
  V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan: End-to-end packet-scheduling in wireless ad-hoc networks. 1021-1030
• 
  Matthew Andrews, Lisa Zhang: Routing and scheduling in multihop wireless networks with time-varying channels. 1031-1040
• 
  William S. Evans, David G. Kirkpatrick: Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ. 1041-1049
• 
  Xiaojie Gao, Kamal Jain, Leonard J. Schulman: Fair and efficient router congestion control. 1050-1059

Session 12B

• 
  Volkan Isler, Sampath Kannan, Sanjeev Khanna: Randomized pursuit-evasion with limited visibility. 1060-1069
• 
  Noa Agmon, David Peleg: Fault-tolerant gathering algorithms for autonomous mobile robots. 1070-1078
• 
  Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, Éva Tardos: Approximate classification via earthmover metrics. 1079-1087
• 
  David B. Shmoys, Chaitanya Swamy, Retsef Levi: Facility location with Service Installation Costs. 1088-1097
• 
  Otfried Cheong, Alon Efrat, Sariel Har-Peled: On finding a guard that sees most and a shop that sells most. 1098-1107

Session 12C

• 
  László Babai, Robert Beals, Ákos Seress: On the diameter of the symmetric group: polynomial bounds. 1108-1112
• 
  Cristopher Moore, Daniel N. Rockmore, Alexander Russell, Leonard J. Schulman: The power of basis selection in fourier sampling: hidden subgroup problems in affine groups. 1113-1122
• 
  László Babai, Daniel Stefankovic: Simultaneous diophantine approximation with excluded primes. 1123-1129
• 
  Qi Cheng: Constructing finite field extensions with large order elements. 1130-1131
• 
  Joachim von zur Gathen, Igor Shparlinski: Polynomial interpolation from multiples. 1132-1137