default search action
15th SODA 2004: New Orleans, LA, USA
- J. Ian Munro:
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 Õ(n2) 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 J. 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 A. 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 G. 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 J. 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
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 E. Shparlinski:
Polynomial interpolation from multiples. 1132-1137
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-25 22:30 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: