13. SODA 2002:
San Francisco,
CA,
USA
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms,
January 6-8,
2002,
San Francisco,
CA,
USA. ACM/SIAM,
2002
- Avrim Blum, Shuchi Chawla, Adam Kalai:
Static optimality and dynamic search-optimality in lists and trees.
1-8
Electronic Edition (ACM DL) BibTeX
- Rasmus Pagh, Jakob Pagter:
Optimal time-space trade-offs for non-comparison-based sorting.
9-18
Electronic Edition (ACM DL) BibTeX
- Haim Kaplan, Nira Shafrir, Robert Endre Tarjan:
Union-find with deletions.
19-28
Electronic Edition (ACM DL) BibTeX
- Michael A. Bender, Ziyang Duan, John Iacono, Jing Wu:
A locality-preserving cache-oblivious dynamic dictionary.
29-38
Electronic Edition (ACM DL) BibTeX
- Gerth Stølting Brodal, Rolf Fagerberg, Riko Jacob:
Cache oblivious search trees via binary trees of small height.
39-48
Electronic Edition (ACM DL) BibTeX
- Guy Even, Guy Kortsarz:
An approximation algorithm for the group Steiner problem.
49-58
Electronic Edition (ACM DL) BibTeX
- Leonid Zosin, Samir Khuller:
On directed Steiner trees.
59-63
Electronic Edition (ACM DL) BibTeX
- Markus Bläser:
An 8/13-approximation algorithm for the asymmetric maximum TSP.
64-73
Electronic Edition (ACM DL) BibTeX
- Béla Csaba, Marek Karpinski, Piotr Krysta:
Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems.
74-83
Electronic Edition (ACM DL) BibTeX
- Harold N. Gabow:
An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph.
84-93
Electronic Edition (ACM DL) BibTeX
- Amos Fiat, Jared Saia:
Censorship resistant peer-to-peer content addressable networks.
94-103
Electronic Edition (ACM DL) BibTeX
- Tomás Feder, Rajeev Motwani, Rina Panigrahy, An Zhu:
Web caching with request reordering.
104-105
Electronic Edition (ACM DL) BibTeX
- Sudipto Guha, Kamesh Munagala:
Improved algorithms for the data placement problem.
106-107
Electronic Edition (ACM DL) BibTeX
- Rahul Shah, Martin Farach-Colton:
Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees.
108-115
Electronic Edition (ACM DL) BibTeX
- Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev:
Temporary tasks assignment resolved.
116-124
Electronic Edition (ACM DL) BibTeX
- Jeff Erickson:
Dense point sets have sparse Delaunay triangulations: or "... but not too nasty".
125-134
Electronic Edition (ACM DL) BibTeX
- Sunghee Choi, Nina Amenta:
Delaunay triangulation programs on surface data.
135-136
Electronic Edition (ACM DL) BibTeX
- Siu-Wing Cheng, Tamal K. Dey:
Quality meshing with weighted Delaunay refinement.
137-146
Electronic Edition (ACM DL) BibTeX
- Sunil Arya, Theocharis Malamatos:
Linear-size approximate voronoi diagrams.
147-155
Electronic Edition (ACM DL) BibTeX
- Siu-Wing Cheng, Antoine Vigneron:
Motorcycle graphs and straight skeletons.
156-165
Electronic Edition (ACM DL) BibTeX
- George Karakostas:
Faster approximation schemes for fractional multicommodity flow problems.
166-173
Electronic Edition (ACM DL) BibTeX
- Ekkehard Köhler, Martin Skutella:
Flows over time with load-dependent transit times.
174-183
Electronic Edition (ACM DL) BibTeX
- Petr Kolman, Christian Scheideler:
Improved bounds for the unsplittable flow problem.
184-193
Electronic Edition (ACM DL) BibTeX
- Thomas Erlebach, Alexander Hall:
NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow.
194-202
Electronic Edition (ACM DL) BibTeX
- Tim Roughgarden:
How unfair is optimal routing?
203-204
Electronic Edition (ACM DL) BibTeX
- Eric Lehman, Abhi Shelat:
Approximation algorithms for grammar-based compression.
205-212
Electronic Edition (ACM DL) BibTeX
- Adam L. Buchsbaum, Glenn S. Fowler, Raffaele Giancarlo:
Improving table compression with combinatorial optimization.
213-222
Electronic Edition (ACM DL) BibTeX
- Hsueh-I Lu:
Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits.
223-224
Electronic Edition (ACM DL) BibTeX
- Kunihiko Sadakane:
Succinct representations of lcp information and improvements in the compressed suffix arrays.
225-232
Electronic Edition (ACM DL) BibTeX
- Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao:
Succinct indexable dictionaries with applications to encoding k-ary trees and multisets.
233-242
Electronic Edition (ACM DL) BibTeX
- Uri Zwick:
Jenga.
243-246
Electronic Edition (ACM DL) BibTeX
- Fan R. K. Chung, Ronald L. Graham, Linyuan Lu:
Guessing secrets with inner product questions.
247-253
Electronic Edition (ACM DL) BibTeX
- Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan:
Guessing secrets efficiently via list decoding.
254-262
Electronic Edition (ACM DL) BibTeX
- Sven Oliver Krumke, Maarten Lipmann, Willem de Paepe, Diana Poensgen, Jörg Rambau, Leen Stougie, Gerhard J. Woeginger:
How to cut a cake almost fairly.
263-264
Electronic Edition (ACM DL) BibTeX
- Giovanni Rinaldi, Ulrich Voigt, Gerhard J. Woeginger:
The mathematics of playing golf.
265-266
Electronic Edition (ACM DL) BibTeX
- Seth Pettie, Vijaya Ramachandran:
Computing shortest paths with comparisons and additions.
267-276
Electronic Edition (ACM DL) BibTeX
- Yoshiharu Kohayakawa, Vojtech Rödl, Lubos Thoma:
An optimal algorithm for checking regularity (extended abstract).
277-286
Electronic Edition (ACM DL) BibTeX
- Ojas Parekh:
Edge dominating and hypomatchable sets.
287-291
Electronic Edition (ACM DL) BibTeX
- Vilhelm Dahllöf, Peter Jonsson:
An algorithm for counting maximum weighted independent sets and its applications.
292-298
Electronic Edition (ACM DL) BibTeX
- Ryan Williams:
Algorithms for quantified Boolean formulas.
299-307
Electronic Edition (ACM DL) BibTeX
- Eleni Drinea, Alan M. Frieze, Michael Mitzenmacher:
Balls and bins models with feedback.
308-315
Electronic Edition (ACM DL) BibTeX
- Colin Cooper, Alan M. Frieze, Gregory B. Sorkin:
A note on random 2-SAT with prescribed literal degrees.
316-320
Electronic Edition (ACM DL) BibTeX
- Igor Pak:
Mixing time and long paths in graphs.
321-328
Electronic Edition (ACM DL) BibTeX
- Don Coppersmith, David Gamarnik, Maxim Sviridenko:
The diameter of a long range percolation graph.
329-337
Electronic Edition (ACM DL) BibTeX
- Cedric Adjih, Leonidas Georgiadis, Philippe Jacquet, Wojciech Szpankowski:
Is the internet fractal?
338-345
Electronic Edition (ACM DL) BibTeX
- Victor Chepoi, Feodor F. Dragan, Yann Vaxès:
Center and diameter problems in plane triangulations and quadrangulations.
346-355
Electronic Edition (ACM DL) BibTeX
- Seok-Hee Hong, Brendan D. McKay, Peter Eades:
Symmetric drawings of triconnected planar graphs.
356-365
Electronic Edition (ACM DL) BibTeX
- Shimon Even, Roni Kupershtok:
Layout area of the hypercube (extended abstract).
366-371
Electronic Edition (ACM DL) BibTeX
- Anil Maheshwari, Norbert Zeh:
I/O-optimal algorithms for planar graphs using separators.
372-381
Electronic Edition (ACM DL) BibTeX
- Ryan B. Hayward, Stefan Hougardy, Bruce A. Reed:
Polynomial time recognition of P4-structure.
382-389
Electronic Edition (ACM DL) BibTeX
- Jérémy Barbay, Claire Kenyon:
Adaptive intersection and t-threshold problems.
390-399
Electronic Edition (ACM DL) BibTeX
- Amihood Amir, Kenneth Ward Church, Emanuel Dar:
Separable attributes: a technique for solving the sub matrices character count problem.
400-401
Electronic Edition (ACM DL) BibTeX
- Cristopher Moore, Ivan Rapaport, Eric Rémila:
Tiling groups for Wang tiles.
402-411
Electronic Edition (ACM DL) BibTeX
- Adam Kalai:
Generating random factored numbers, easily.
412-412
Electronic Edition (ACM DL) BibTeX
- Artur Czumaj, Berthold Vöcking:
Tight bounds for worst-case equilibria.
413-420
Electronic Edition (ACM DL) BibTeX
- Jeff Edmonds, Kirk Pruhs:
Broadcast scheduling: when fairness is fine.
421-430
Electronic Edition (ACM DL) BibTeX
- Lars Engebretsen, Madhu Sudan:
Harmonic broadcasting is optimal.
431-432
Electronic Edition (ACM DL) BibTeX
- Amotz Bar-Noy, Richard E. Ladner:
Windows scheduling problems for broadcast systems.
433-442
Electronic Edition (ACM DL) BibTeX
- Matthew Andrews, Lisa Zhang:
Scheduling protocols for switches with large envelopes.
443-452
Electronic Edition (ACM DL) BibTeX
- Alon Efrat, Frank Hoffmann, Christian Knauer, Klaus Kriegel, Günter Rote, Carola Wenk:
Covering shapes by ellipses.
453-454
Electronic Edition (ACM DL) BibTeX
- Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan:
Slice and dice: a simple, improved approximate tiling recipe.
455-464
Electronic Edition (ACM DL) BibTeX
- Csaba D. Tóth:
Binary space partitions for line segments with a limited number of directions.
465-471
Electronic Edition (ACM DL) BibTeX
- Timothy M. Chan:
Closest-point problems simplified on the RAM.
472-473
Electronic Edition (ACM DL) BibTeX
- Timothy M. Chan:
Semi-online maintenance of geometric optima and measures.
474-483
Electronic Edition (ACM DL) BibTeX
- Sudipto Guha, Kamesh Munagala:
Generalized clustering.
484-485
Electronic Edition (ACM DL) BibTeX
- Steven S. Seiden, Rob van Stee:
New bounds for multi-dimensional packing.
486-495
Electronic Edition (ACM DL) BibTeX
- Uri Zwick:
Computer assisted proof of optimal approximability results.
496-505
Electronic Edition (ACM DL) BibTeX
- Eran Halperin, Dror Livnat, Uri Zwick:
MAX CUT in cubic graphs.
506-513
Electronic Edition (ACM DL) BibTeX
- Piotr Berman, Marek Karpinski:
Approximating minimum unsatisfiability of linear equations.
514-516
Electronic Edition (ACM DL) BibTeX
- Sandy Irani, Xiangwen Lu, Amelia Regan:
On-line algorithms for the dynamic traveling repair problem.
517-524
Electronic Edition (ACM DL) BibTeX
- Amotz Bar-Noy, Ari Freund, Shimon Landa, Joseph Naor:
Competitive on-line switching policies.
525-534
Electronic Edition (ACM DL) BibTeX
- Sanjeev Arora, Bo Brinkman:
A randomized online algorithm for bandwidth utilization.
535-539
Electronic Edition (ACM DL) BibTeX
- Parikshit Gopalan, Howard J. Karloff, Aranyak Mehta, Milena Mihail, Nisheeth K. Vishnoi:
Caching with expiration times.
540-547
Electronic Edition (ACM DL) BibTeX
- Edward J. Anderson, Chris N. Potts:
On-line scheduling of a single machine to minimize total weighted completion time.
548-557
Electronic Edition (ACM DL) BibTeX
- Shankar Krishnan, Nabil H. Mustafa, Suresh Venkatasubramanian:
Hardware-assisted computation of depth contours.
558-567
Electronic Edition (ACM DL) BibTeX
- Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell, Martin Skutella:
The freeze-tag problem: how to wake up a swarm of robots.
568-577
Electronic Edition (ACM DL) BibTeX
- Darin Goldstein, Nick Meyer:
The wake up and report problem is time-equivalent to the firing squad synchronization problem.
578-587
Electronic Edition (ACM DL) BibTeX
- Krzysztof Diks, Pierre Fraigniaud, Evangelos Kranakis, Andrzej Pelc:
Tree exploration with little memory.
588-597
Electronic Edition (ACM DL) BibTeX
- József Beck, Sachin Lodha:
Efficient proper 2-coloring of almost disjoint hypergraphs.
598-605
Electronic Edition (ACM DL) BibTeX
- Irene Finocchi, Alessandro Panconesi, Riccardo Silvestri:
Experimental analysis of simple, distributed vertex coloring algorithms.
606-615
Electronic Edition (ACM DL) BibTeX
- Moses Charikar:
On semidefinite programming relaxations for graph coloring and vertex cover.
616-620
Electronic Edition (ACM DL) BibTeX
- R. Ravi, Amitabh Sinha II:
Approximating k-cuts via network strength.
621-622
Electronic Edition (ACM DL) BibTeX
- Ziv Bar-Yossef, Ravi Kumar, D. Sivakumar:
Reductions in streaming algorithms, with an application to counting triangles in graphs.
623-632
Electronic Edition (ACM DL) BibTeX
- Brian Babcock, Mayur Datar, Rajeev Motwani:
Sampling from a moving window over streaming data.
633-634
Electronic Edition (ACM DL) BibTeX
- Mayur Datar, Aristides Gionis, Piotr Indyk, Rajeev Motwani:
Maintaining stream statistics over sliding windows (extended abstract).
635-644
Electronic Edition (ACM DL) BibTeX
- Noga Alon, Asaf Shapira:
Testing satisfiability.
645-654
Electronic Edition (ACM DL) BibTeX
- Adam Kalai:
Efficient pattern-matching with don't cares.
655-656
Electronic Edition (ACM DL) BibTeX
- S. Muthukrishnan:
Efficient algorithms for document retrieval problems.
657-666
Electronic Edition (ACM DL) BibTeX
- Graham Cormode, S. Muthukrishnan:
The string edit distance matching problem with moves.
667-676
Electronic Edition (ACM DL) BibTeX
- Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan:
Simple approximation algorithm for nonoverlapping local alignments.
677-678
Electronic Edition (ACM DL) BibTeX
- Maxime Crochemore, Gad M. Landau, Michal Ziv-Ukelson:
A sub-quadratic sequence alignment algorithm for unrestricted cost matrices.
679-688
Electronic Edition (ACM DL) BibTeX
- Leszek Gasieniec, Andrzej Lingas:
On adaptive deterministic gossiping in ad hoc radio networks.
689-690
Electronic Edition (ACM DL) BibTeX
- Alexander Gamburd, Igor Pak:
Expansion of product replacement graphs.
691-696
Electronic Edition (ACM DL) BibTeX
- Piotr Indyk:
Explicit constructions of selectors and related combinatorial structures, with applications.
697-704
Electronic Edition (ACM DL) BibTeX
- Lars Engebretsen, Piotr Indyk, Ryan O'Donnell:
Derandomized dimensionality reduction with applications.
705-712
Electronic Edition (ACM DL) BibTeX
- Seth Pettie, Vijaya Ramachandran:
Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms.
713-722
Electronic Edition (ACM DL) BibTeX
- April Rasala, Clifford Stein, Eric Torng, Patchrawat Uthaisombut:
Existence theorems, lower bounds and algorithms for scheduling to meet two objectives.
723-731
Electronic Edition (ACM DL) BibTeX
- Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, Irina Shapira:
Scheduling split intervals.
732-741
Electronic Edition (ACM DL) BibTeX
- Amotz Bar-Noy, Sudipto Guha, Yoav Katz, Joseph Naor, Baruch Schieber, Hadas Shachnai:
Throughput maximization of real-time scheduling with batching.
742-751
Electronic Edition (ACM DL) BibTeX
- Allan Borodin, Morten N. Nielsen, Charles Rackoff:
(Incremental) priority algorithms.
752-761
Electronic Edition (ACM DL) BibTeX
- Michael A. Bender, S. Muthukrishnan, Rajmohan Rajaraman:
Improved algorithms for stretch scheduling.
762-771
Electronic Edition (ACM DL) BibTeX
- Tamal K. Dey, Joachim Giesen, Samrat Goswami, Wulue Zhao:
Shape dimension and approximation from samples.
772-780
Electronic Edition (ACM DL) BibTeX
- Stefan Funke, Edgar A. Ramos:
Smooth-surface reconstruction in near-linear time.
781-790
Electronic Edition (ACM DL) BibTeX
- Pankaj K. Agarwal, Herbert Edelsbrunner, Yusu Wang:
Computing the writhing number of a polygonal knot.
791-799
Electronic Edition (ACM DL) BibTeX
- Pankaj K. Agarwal, Micha Sharir:
Pseudo-line arrangements: duality, algorithms, and applications.
800-809
Electronic Edition (ACM DL) BibTeX
- Vladlen Koltun, Micha Sharir:
On the overlay of envelopes in four dimensions.
810-819
Electronic Edition (ACM DL) BibTeX
- Philip N. Klein:
Preprocessing an undirected planar network to enable fast approximate distance queries.
820-827
Electronic Edition (ACM DL) BibTeX
- Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel H. M. Smid:
Approximate distance oracles for geometric graphs.
828-837
Electronic Edition (ACM DL) BibTeX
- Camil Demetrescu, Mikkel Thorup:
Oracles for distances avoiding a link-failure.
838-843
Electronic Edition (ACM DL) BibTeX
- Liam Roditty, Mikkel Thorup, Uri Zwick:
Roundtrip spanners and roundtrip routing in directed graphs.
844-851
Electronic Edition (ACM DL) BibTeX
- Michelangelo Grigni, Papa Sissokho:
Light spanners and approximate TSP in weighted graphs with forbidden minors.
852-857
Electronic Edition (ACM DL) BibTeX
- Sudipto Guha, Refael Hassin, Samir Khuller, Einat Or:
Capacitated vertex covering with applications.
858-865
Electronic Edition (ACM DL) BibTeX
- Ross M. McConnell, Jeremy Spinrad:
Construction of probe interval models.
866-875
Electronic Edition (ACM DL) BibTeX
- Alantha Newman:
A new algorithm for protein folding in the HP model.
876-884
Electronic Edition (ACM DL) BibTeX
- David Hart:
An optimal (expected time) algorithm for minimizing lab costs in DNA sequencing.
885-893
Electronic Edition (ACM DL) BibTeX
- Gianluca Della Vedova, Tao Jiang, Jing Li, Jianjun Wen:
Approximating minimum quartet inconsistency (abstract).
894-895
Electronic Edition (ACM DL) BibTeX
- Tetsuo Asano, Naoki Katoh, Koji Obokata, Takeshi Tokuyama:
Matrix rounding under the Lp-discrepancy measure and its application to digital halftoning.
896-904
Electronic Edition (ACM DL) BibTeX
- Avrim Blum, John Dunagan:
Smoothed analysis of the perceptron algorithm for linear programming.
905-914
Electronic Edition (ACM DL) BibTeX
- Satoru Iwata:
A fully combinatorial algorithm for submodular function minimization.
915-919
Electronic Edition (ACM DL) BibTeX
- Friedrich Eisenbrand, Giovanni Rinaldi, Paolo Ventura:
0/1 optimization and 0/1 primal separation are equivalent.
920-926
Electronic Edition (ACM DL) BibTeX
- Michal Katz, Nir A. Katz, Amos Korman, David Peleg:
Labeling schemes for flow and connectivity.
927-936
Electronic Edition (ACM DL) BibTeX
- Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick:
Reachability and distance queries via 2-hop labels.
937-946
Electronic Edition (ACM DL) BibTeX
- Stephen Alstrup, Theis Rauhe:
Improved labeling scheme for ancestor queries.
947-953
Electronic Edition (ACM DL) BibTeX
- Haim Kaplan, Tova Milo, Ronen Shabo:
A comparison of labeling schemes for ancestor queries.
954-963
Electronic Edition (ACM DL) BibTeX
- Ziv Bar-Yossef, Kirsten Hildrum, Felix Wu:
Incentive-compatible online auctions for digital goods.
964-970
Electronic Edition (ACM DL) BibTeX
- Avrim Blum, Tuomas Sandholm, Martin Zinkevich:
Online algorithms for market clearing.
971-980
Electronic Edition (ACM DL) BibTeX
- Micah Adler, Dan Rubenstein:
Pricing multicasting in more practical network models.
981-990
Electronic Edition (ACM DL) BibTeX
- Aaron Archer, Éva Tardos:
Frugal path mechanisms.
991-999
Electronic Edition (ACM DL) BibTeX
- R. Ravi, David P. Williamson:
Erratum: an approximation algorithm for minimum-cost vertex-connectivity problems.
1000-1001
Electronic Edition (ACM DL) BibTeX
Copyright © Sat May 16 23:41:52 2009
by Michael Ley (ley@uni-trier.de)
