15. SODA 2004: New Orleans, LA, USA

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
  

Last update Fri May 25 08:40:48 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page