13. SODA 2002:
San Francisco, CA, USA
David Eppstein (Ed.):
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA.
ACM/SIAM 2002, ISBN 0-89871-513-X
- Avrim Blum, Shuchi Chawla, Adam Kalai:
Static optimality and dynamic search-optimality in lists and trees.
1-8

- Rasmus Pagh, Jakob Pagter:
Optimal time-space trade-offs for non-comparison-based sorting.
9-18

- Haim Kaplan, Nira Shafrir, Robert Endre Tarjan:
Union-find with deletions.
19-28

- Michael A. Bender, Ziyang Duan, John Iacono, Jing Wu:
A locality-preserving cache-oblivious dynamic dictionary.
29-38

- Gerth Stølting Brodal, Rolf Fagerberg, Riko Jacob:
Cache oblivious search trees via binary trees of small height.
39-48

- Guy Even, Guy Kortsarz:
An approximation algorithm for the group Steiner problem.
49-58

- Leonid Zosin, Samir Khuller:
On directed Steiner trees.
59-63

- Markus Bläser:
An 8/13-approximation algorithm for the asymmetric maximum TSP.
64-73

- Béla Csaba, Marek Karpinski, Piotr Krysta:
Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems.
74-83

- Harold N. Gabow:
An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph.
84-93

- Amos Fiat, Jared Saia:
Censorship resistant peer-to-peer content addressable networks.
94-103

- Tomás Feder, Rajeev Motwani, Rina Panigrahy, An Zhu:
Web caching with request reordering.
104-105

- Sudipto Guha, Kamesh Munagala:
Improved algorithms for the data placement problem.
106-107

- Rahul Shah, Martin Farach-Colton:
Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees.
108-115

- Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev:
Temporary tasks assignment resolved.
116-124

- Jeff Erickson:
Dense point sets have sparse Delaunay triangulations: or "... but not too nasty".
125-134

- Sunghee Choi, Nina Amenta:
Delaunay triangulation programs on surface data.
135-136

- Siu-Wing Cheng, Tamal K. Dey:
Quality meshing with weighted Delaunay refinement.
137-146

- Sunil Arya, Theocharis Malamatos:
Linear-size approximate voronoi diagrams.
147-155

- Siu-Wing Cheng, Antoine Vigneron:
Motorcycle graphs and straight skeletons.
156-165

- George Karakostas:
Faster approximation schemes for fractional multicommodity flow problems.
166-173

- Ekkehard Köhler, Martin Skutella:
Flows over time with load-dependent transit times.
174-183

- Petr Kolman, Christian Scheideler:
Improved bounds for the unsplittable flow problem.
184-193

- Thomas Erlebach, Alexander Hall:
NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow.
194-202

- Tim Roughgarden:
How unfair is optimal routing?
203-204

- Eric Lehman, Abhi Shelat:
Approximation algorithms for grammar-based compression.
205-212

- Adam L. Buchsbaum, Glenn S. Fowler, Raffaele Giancarlo:
Improving table compression with combinatorial optimization.
213-222

- Hsueh-I Lu:
Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits.
223-224

- Kunihiko Sadakane:
Succinct representations of lcp information and improvements in the compressed suffix arrays.
225-232

- Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao:
Succinct indexable dictionaries with applications to encoding k-ary trees and multisets.
233-242

- Uri Zwick:
Jenga.
243-246

- Fan R. K. Chung, Ronald L. Graham, Linyuan Lu:
Guessing secrets with inner product questions.
247-253

- Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan:
Guessing secrets efficiently via list decoding.
254-262

- 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

- Giovanni Rinaldi, Ulrich Voigt, Gerhard J. Woeginger:
The mathematics of playing golf.
265-266

- Seth Pettie, Vijaya Ramachandran:
Computing shortest paths with comparisons and additions.
267-276

- Yoshiharu Kohayakawa, Vojtech Rödl, Lubos Thoma:
An optimal algorithm for checking regularity (extended abstract).
277-286

- Ojas Parekh:
Edge dominating and hypomatchable sets.
287-291

- Vilhelm Dahllöf, Peter Jonsson:
An algorithm for counting maximum weighted independent sets and its applications.
292-298

- Ryan Williams:
Algorithms for quantified Boolean formulas.
299-307

- Eleni Drinea, Alan M. Frieze, Michael Mitzenmacher:
Balls and bins models with feedback.
308-315

- Colin Cooper, Alan M. Frieze, Gregory B. Sorkin:
A note on random 2-SAT with prescribed literal degrees.
316-320

- Igor Pak:
Mixing time and long paths in graphs.
321-328

- Don Coppersmith, David Gamarnik, Maxim Sviridenko:
The diameter of a long range percolation graph.
329-337

- Cedric Adjih, Leonidas Georgiadis, Philippe Jacquet, Wojciech Szpankowski:
Is the internet fractal?
338-345

- Victor Chepoi, Feodor F. Dragan, Yann Vaxès:
Center and diameter problems in plane triangulations and quadrangulations.
346-355

- Seok-Hee Hong, Brendan D. McKay, Peter Eades:
Symmetric drawings of triconnected planar graphs.
356-365

- Shimon Even, Roni Kupershtok:
Layout area of the hypercube (extended abstract).
366-371

- Anil Maheshwari, Norbert Zeh:
I/O-optimal algorithms for planar graphs using separators.
372-381

- Ryan B. Hayward, Stefan Hougardy, Bruce A. Reed:
Polynomial time recognition of P4-structure.
382-389

- Jérémy Barbay, Claire Kenyon:
Adaptive intersection and t-threshold problems.
390-399

- Amihood Amir, Kenneth Ward Church, Emanuel Dar:
Separable attributes: a technique for solving the sub matrices character count problem.
400-401

- Cristopher Moore, Ivan Rapaport, Eric Rémila:
Tiling groups for Wang tiles.
402-411

- Adam Kalai:
Generating random factored numbers, easily.
412-412

- Artur Czumaj, Berthold Vöcking:
Tight bounds for worst-case equilibria.
413-420

- Jeff Edmonds, Kirk Pruhs:
Broadcast scheduling: when fairness is fine.
421-430

- Lars Engebretsen, Madhu Sudan:
Harmonic broadcasting is optimal.
431-432

- Amotz Bar-Noy, Richard E. Ladner:
Windows scheduling problems for broadcast systems.
433-442

- Matthew Andrews, Lisa Zhang:
Scheduling protocols for switches with large envelopes.
443-452

- Alon Efrat, Frank Hoffmann, Christian Knauer, Klaus Kriegel, Günter Rote, Carola Wenk:
Covering shapes by ellipses.
453-454

- Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan:
Slice and dice: a simple, improved approximate tiling recipe.
455-464

- Csaba D. Tóth:
Binary space partitions for line segments with a limited number of directions.
465-471

- Timothy M. Chan:
Closest-point problems simplified on the RAM.
472-473

- Timothy M. Chan:
Semi-online maintenance of geometric optima and measures.
474-483

- Sudipto Guha, Kamesh Munagala:
Generalized clustering.
484-485

- Steven S. Seiden, Rob van Stee:
New bounds for multi-dimensional packing.
486-495

- Uri Zwick:
Computer assisted proof of optimal approximability results.
496-505

- Eran Halperin, Dror Livnat, Uri Zwick:
MAX CUT in cubic graphs.
506-513

- Piotr Berman, Marek Karpinski:
Approximating minimum unsatisfiability of linear equations.
514-516

- Sandy Irani, Xiangwen Lu, Amelia Regan:
On-line algorithms for the dynamic traveling repair problem.
517-524

- Amotz Bar-Noy, Ari Freund, Shimon Landa, Joseph Naor:
Competitive on-line switching policies.
525-534

- Sanjeev Arora, Bo Brinkman:
A randomized online algorithm for bandwidth utilization.
535-539

- Parikshit Gopalan, Howard J. Karloff, Aranyak Mehta, Milena Mihail, Nisheeth K. Vishnoi:
Caching with expiration times.
540-547

- Edward J. Anderson, Chris N. Potts:
On-line scheduling of a single machine to minimize total weighted completion time.
548-557

- Shankar Krishnan, Nabil H. Mustafa, Suresh Venkatasubramanian:
Hardware-assisted computation of depth contours.
558-567

- 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

- Darin Goldstein, Nick Meyer:
The wake up and report problem is time-equivalent to the firing squad synchronization problem.
578-587

- Krzysztof Diks, Pierre Fraigniaud, Evangelos Kranakis, Andrzej Pelc:
Tree exploration with little memory.
588-597

- József Beck, Sachin Lodha:
Efficient proper 2-coloring of almost disjoint hypergraphs.
598-605

- Irene Finocchi, Alessandro Panconesi, Riccardo Silvestri:
Experimental analysis of simple, distributed vertex coloring algorithms.
606-615

- Moses Charikar:
On semidefinite programming relaxations for graph coloring and vertex cover.
616-620

- R. Ravi, Amitabh Sinha II:
Approximating k-cuts via network strength.
621-622

- Ziv Bar-Yossef, Ravi Kumar, D. Sivakumar:
Reductions in streaming algorithms, with an application to counting triangles in graphs.
623-632

- Brian Babcock, Mayur Datar, Rajeev Motwani:
Sampling from a moving window over streaming data.
633-634

- Mayur Datar, Aristides Gionis, Piotr Indyk, Rajeev Motwani:
Maintaining stream statistics over sliding windows (extended abstract).
635-644

- Noga Alon, Asaf Shapira:
Testing satisfiability.
645-654

- Adam Kalai:
Efficient pattern-matching with don't cares.
655-656

- S. Muthukrishnan:
Efficient algorithms for document retrieval problems.
657-666

- Graham Cormode, S. Muthukrishnan:
The string edit distance matching problem with moves.
667-676

- Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan:
Simple approximation algorithm for nonoverlapping local alignments.
677-678

- Maxime Crochemore, Gad M. Landau, Michal Ziv-Ukelson:
A sub-quadratic sequence alignment algorithm for unrestricted cost matrices.
679-688

- Leszek Gasieniec, Andrzej Lingas:
On adaptive deterministic gossiping in ad hoc radio networks.
689-690

- Alexander Gamburd, Igor Pak:
Expansion of product replacement graphs.
691-696

- Piotr Indyk:
Explicit constructions of selectors and related combinatorial structures, with applications.
697-704

- Lars Engebretsen, Piotr Indyk, Ryan O'Donnell:
Derandomized dimensionality reduction with applications.
705-712

- Seth Pettie, Vijaya Ramachandran:
Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms.
713-722

- April Rasala, Clifford Stein, Eric Torng, Patchrawat Uthaisombut:
Existence theorems, lower bounds and algorithms for scheduling to meet two objectives.
723-731

- Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, Irina Shapira:
Scheduling split intervals.
732-741

- Amotz Bar-Noy, Sudipto Guha, Yoav Katz, Joseph Naor, Baruch Schieber, Hadas Shachnai:
Throughput maximization of real-time scheduling with batching.
742-751

- Allan Borodin, Morten N. Nielsen, Charles Rackoff:
(Incremental) priority algorithms.
752-761

- Michael A. Bender, S. Muthukrishnan, Rajmohan Rajaraman:
Improved algorithms for stretch scheduling.
762-771

- Tamal K. Dey, Joachim Giesen, Samrat Goswami, Wulue Zhao:
Shape dimension and approximation from samples.
772-780

- Stefan Funke, Edgar A. Ramos:
Smooth-surface reconstruction in near-linear time.
781-790

- Pankaj K. Agarwal, Herbert Edelsbrunner, Yusu Wang:
Computing the writhing number of a polygonal knot.
791-799

- Pankaj K. Agarwal, Micha Sharir:
Pseudo-line arrangements: duality, algorithms, and applications.
800-809

- Vladlen Koltun, Micha Sharir:
On the overlay of envelopes in four dimensions.
810-819

- Philip N. Klein:
Preprocessing an undirected planar network to enable fast approximate distance queries.
820-827

- Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel H. M. Smid:
Approximate distance oracles for geometric graphs.
828-837

- Camil Demetrescu, Mikkel Thorup:
Oracles for distances avoiding a link-failure.
838-843

- Liam Roditty, Mikkel Thorup, Uri Zwick:
Roundtrip spanners and roundtrip routing in directed graphs.
844-851

- Michelangelo Grigni, Papa Sissokho:
Light spanners and approximate TSP in weighted graphs with forbidden minors.
852-857

- Sudipto Guha, Refael Hassin, Samir Khuller, Einat Or:
Capacitated vertex covering with applications.
858-865

- Ross M. McConnell, Jeremy Spinrad:
Construction of probe interval models.
866-875

- Alantha Newman:
A new algorithm for protein folding in the HP model.
876-884

- David Hart:
An optimal (expected time) algorithm for minimizing lab costs in DNA sequencing.
885-893

- Gianluca Della Vedova, Tao Jiang, Jing Li, Jianjun Wen:
Approximating minimum quartet inconsistency (abstract).
894-895

- Tetsuo Asano, Naoki Katoh, Koji Obokata, Takeshi Tokuyama:
Matrix rounding under the Lp-discrepancy measure and its application to digital halftoning.
896-904

- Avrim Blum, John Dunagan:
Smoothed analysis of the perceptron algorithm for linear programming.
905-914

- Satoru Iwata:
A fully combinatorial algorithm for submodular function minimization.
915-919

- Friedrich Eisenbrand, Giovanni Rinaldi, Paolo Ventura:
0/1 optimization and 0/1 primal separation are equivalent.
920-926

- Michal Katz, Nir A. Katz, Amos Korman, David Peleg:
Labeling schemes for flow and connectivity.
927-936

- Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick:
Reachability and distance queries via 2-hop labels.
937-946

- Stephen Alstrup, Theis Rauhe:
Improved labeling scheme for ancestor queries.
947-953

- Haim Kaplan, Tova Milo, Ronen Shabo:
A comparison of labeling schemes for ancestor queries.
954-963

- Ziv Bar-Yossef, Kirsten Hildrum, Felix Wu:
Incentive-compatible online auctions for digital goods.
964-970

- Avrim Blum, Tuomas Sandholm, Martin Zinkevich:
Online algorithms for market clearing.
971-980

- Micah Adler, Dan Rubenstein:
Pricing multicasting in more practical network models.
981-990

- Aaron Archer, Éva Tardos:
Frugal path mechanisms.
991-999

- R. Ravi, David P. Williamson:
Erratum: an approximation algorithm for minimum-cost vertex-connectivity problems.
1000-1001

Last update Sat May 18 19:48:57 2013
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page