12. SODA 2001:
Washington,
DC,
USA
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms,
January 7-9,
2001,
Washington,
DC,
USA. ACM/SIAM
- Eran Halperin, Uri Zwick:
Combinatorial approximation algorithms for the maximum directed cut problem.
1-7
Electronic Edition (ACM DL) BibTeX
- Gruia Calinescu, Howard J. Karloff, Yuval Rabani:
Approximation algorithms for the 0-extension problem.
8-16
Electronic Edition (ACM DL) BibTeX
- Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat:
A faster implementation of the Goemans-Williamson clustering algorithm.
17-25
Electronic Edition (ACM DL) BibTeX
- Joseph Naor, Yuval Rabani:
Tree packing and approximating k-cuts.
26-27
Electronic Edition (ACM DL) BibTeX
- Xiang-Yang Li, Shang-Hua Teng:
Generating well-shaped Delaunay meshed in 3D.
28-37
Electronic Edition (ACM DL) BibTeX
- Adrian Dumitrescu, Joseph S. B. Mitchell:
Approximation algorithms for TSP with neighborhoods in the plane.
38-46
Electronic Edition (ACM DL) BibTeX
- Ho-Lun Cheng, Tamal K. Dey, Herbert Edelsbrunner, John Sullivan:
Dynamic skin triangulation.
47-56
Electronic Edition (ACM DL) BibTeX
- Sariel Har-Peled, Micha Sharir:
Online point location in planar arrangements and its applications.
57-66
Electronic Edition (ACM DL) BibTeX
- Peter Sanders:
Reconciling simplicity and realism in parallel disk models.
67-76
Electronic Edition (ACM DL) BibTeX
- Jeffrey Scott Vitter, David A. Hutchinson:
Distribution sort with randomizing cycle.
77-86
Electronic Edition (ACM DL) BibTeX
- Ulrich Meyer:
External memory BFS on undirected graphs with bounded degree.
87-88
Electronic Edition (ACM DL) BibTeX
- Anil Maheshwari, Norbert Zeh:
I/O-efficient algorithms for graphs of bounded treewidth.
89-90
Electronic Edition (ACM DL) BibTeX
- Noga Alon, Benny Sudakov, Uri Zwick:
Constructing worst case instances for semidefinite programming based approximation algorithms.
92-100
Electronic Edition (ACM DL) BibTeX
- Marco Pellegrini:
Randomizing combinatorial algorithms for linear programming when the dimension is moderately high.
101-108
Electronic Edition (ACM DL) BibTeX
- Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin:
Approximation algorithms for the metric labeling problem via a new linear programming formulation.
109-118
Electronic Edition (ACM DL) BibTeX
- Benjamin Doerr:
Lattice approximation and linear discrepency of totally unimodular matrices.
119-125
Electronic Edition (ACM DL) BibTeX
- Ravi Kumar, D. Sivakumar:
On polynomial approximation to the shortest lattice vector length.
126-127
Electronic Edition (ACM DL) BibTeX
- Francis Y. L. Chin, Stanley P. Y. Fung, Cao An Wang:
Approximation for minimum triangulation of convex polyhedra.
128-137
Electronic Edition (ACM DL) BibTeX
- Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia:
Optimal covering tours with turn costs.
138-147
Electronic Edition (ACM DL) BibTeX
- Pankaj K. Agarwal, Sariel Har-Peled:
Maintaining approximate extent measures of moving points.
148-157
Electronic Edition (ACM DL) BibTeX
- John Hershberger, Subhash Suri:
Simplified kinetic connectivity for rectangles and hypercubes.
158-167
Electronic Edition (ACM DL) BibTeX
- Menelaos I. Karavelas, Leonidas J. Guibas:
Static and kinetic geometric spanners with applications.
168-176
Electronic Edition (ACM DL) BibTeX
- David Liben-Nowell:
Gossip is synteny: incomplete gossip and an exact algorithm for syntenic distance.
177-185
Electronic Edition (ACM DL) BibTeX
- Tandy Warnow, Bernard M. E. Moret, Katherine St. John:
Absolute convergence: true trees from short sequences.
186-195
Electronic Edition (ACM DL) BibTeX
- Katherine St. John, Tandy Warnow, Bernard M. E. Moret, Lisa Vawter:
Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining.
196-205
Electronic Edition (ACM DL) BibTeX
- Daniel G. Brown:
A probabilistic analysis of a greedy algorithm arising from computational biology.
206-207
Electronic Edition (ACM DL) BibTeX
- Rahul Shah, Martin Farach-Colton:
On the midpath tree conjuncture: a counter-example.
208-209
Electronic Edition (ACM DL) BibTeX
- Cyril Gavoille, David Peleg, Stephane Perennes, Ran Raz:
Distance labeling in graphs.
210-219
Electronic Edition (ACM DL) BibTeX
- Anupam Gupta:
Steiner points in tree metrics don't (really) help.
220-227
Electronic Edition (ACM DL) BibTeX
- David Eppstein, Joseph Wang:
Fast approximation of centrality.
228-229
Electronic Edition (ACM DL) BibTeX
- Guangting Chen, Guoliang Xue:
K-pair delay constrained minimum cost routing in undirected networks.
230-231
Electronic Edition (ACM DL) BibTeX
- Chandra Chekuri, Sanjeev Khanna, Joseph Naor:
A deterministic algorithm for the cost-distance problem.
232-233
Electronic Edition (ACM DL) BibTeX
- Yunhong Zhou, Subhash Suri:
Shape sensitive geometric permutations.
234-243
Electronic Edition (ACM DL) BibTeX
- Yingping Huang, Jinhui Xu, Danny Z. Chen:
Geometric permutations of high dimensional spheres.
244-245
Electronic Edition (ACM DL) BibTeX
- Carsten Gutwenger, Petra Mutzel, René Weiskircher:
Inserting an edge into a planar graph.
246-255
Electronic Edition (ACM DL) BibTeX
- Sunil Arya, Theocharis Malamatos, David M. Mount:
Entropy-preserving cuttings and space-efficient planar point location.
256-261
Electronic Edition (ACM DL) BibTeX
- Sunil Arya, Theocharis Malamatos, David M. Mount:
A simple entropy-based algorithm for planar point location.
262-268
Electronic Edition (ACM DL) BibTeX
- Paolo Ferragina, Giovanni Manzini:
An experimental study of an opportunistic index.
269-278
Electronic Edition (ACM DL) BibTeX
- Amihood Amir, Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat:
Overlap matching.
279-288
Electronic Edition (ACM DL) BibTeX
- Erik D. Demaine, Alejandro López-Ortiz:
A linear lower bound on index size for text retrieval.
289-294
Electronic Edition (ACM DL) BibTeX
- Alon Efrat, Piotr Indyk, Suresh Venkatasubramanian:
Pattern matching for sets of segments.
295-304
Electronic Edition (ACM DL) BibTeX
- Amihood Amir, Ely Porat, Moshe Lewenstein:
Approximate subset matching with Don't Cares.
305-306
Electronic Edition (ACM DL) BibTeX
- Arne Andersson, Mikkel Thorup:
Dynamic string searching.
307-308
Electronic Edition (ACM DL) BibTeX
- Guy Kortsarz, Robert Krauthgamer:
On approximating the achromatic number.
309-318
Electronic Edition (ACM DL) BibTeX
- Eran Halperin, Ram Nathaniel, Uri Zwick:
Coloring k-colorable graphs using smaller palettes.
319-326
Electronic Edition (ACM DL) BibTeX
- Michael Krivelevich, Ram Nathaniel, Benny Sudakov:
Approximating coloring and maximum independent sets in 3-uniform hypergraphs.
327-328
Electronic Edition (ACM DL) BibTeX
- David Eppstein:
Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
329-337
Electronic Edition (ACM DL) BibTeX
- Mirela Damian-Iordache, Sriram V. Pemmaraju:
Computing optimal alpha-fat and alpha-small decompositions.
338-339
Electronic Edition (ACM DL) BibTeX
- John Iacono:
Optimal planar point location.
340-341
Electronic Edition (ACM DL) BibTeX
- Danny Z. Chen, Ovidiu Daescu, John Hershberger, Peter M. Kogge, Jack Snoeyink:
Polygonal path approximation with angle constraints.
342-343
Electronic Edition (ACM DL) BibTeX
- Stefan Funke, Edgar A. Ramos:
Reconstructing a collection of curves with corners and endpoints.
344-353
Electronic Edition (ACM DL) BibTeX
- Adam Meyerson, Kamesh Munagala, Serge A. Plotkin:
Web caching using access statistics.
354-363
Electronic Edition (ACM DL) BibTeX
- Amotz Bar-Noy, Richard E. Ladner:
Competitive on-line stream merging algorithms for media-on-demand.
364-373
Electronic Edition (ACM DL) BibTeX
- Mark Brehob, Richard J. Enbody, Eric Torng, Stephen Wagner:
On-line restricted caching.
374-383
Electronic Edition (ACM DL) BibTeX
- Ashish Goel, Adam Meyerson, Serge A. Plotkin:
Approximate majorization and fair online load balancing.
384-390
Electronic Edition (ACM DL) BibTeX
- Christos H. Papadimitriou:
Game theory, algorithms, and the Internet.
391
Electronic Edition (ACM DL) BibTeX
- David R. Karger, Nathan Srebro:
Learning Markov networks: maximum bounded tree-width graphs.
392-401
Electronic Edition (ACM DL) BibTeX
- Dieter Rautenbach, Bruce A. Reed:
Approximately covering by cycles in planar graphs.
402-406
Electronic Edition (ACM DL) BibTeX
- Alexander Zelikovsky, Ion I. Mandoiu:
Practical approximation algorithms for zero- and bounded-skew trees.
407-416
Electronic Edition (ACM DL) BibTeX
- Adrian Vetta:
Approximating the minimum strongly connected subgraph via a matching lower bound.
417-426
Electronic Edition (ACM DL) BibTeX
- Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan, Suneeta Ramaswami:
Improved approximation algorithms for rectangle tiling and packing.
427-436
Electronic Edition (ACM DL) BibTeX
- Nina Mishra, Daniel Oblinger, Leonard Pitt:
Sublinear time approximate clustering.
439-447
Electronic Edition (ACM DL) BibTeX
- Moni Naor, Benny Pinkas:
Efficient oblivious transfer protocols.
448-457
Electronic Edition (ACM DL) BibTeX
- Moni Naor, Omer Reingold:
Constructing pseudo-random permutations with a prescribed structure.
458-459
Electronic Edition (ACM DL) BibTeX
- Vijay Raghavan, Jeremy Spinrad:
Robust algorithms for restricted domains.
460-467
Electronic Edition (ACM DL) BibTeX
- Daniel Kobler, Udi Rotics:
Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract).
468-476
Electronic Edition (ACM DL) BibTeX
- Julie L. Johnson, Jeremy Spinrad:
A polynomial time recognition algorithm for probe interval graphs.
477-486
Electronic Edition (ACM DL) BibTeX
- Johann A. Makowsky:
Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width.
487-495
Electronic Edition (ACM DL) BibTeX
- Chen Li, Chee-Keng Yap:
A new constructive root bound for algebraic expressions.
496-505
Electronic Edition (ACM DL) BibTeX
- Yi-Ting Chiang, Ching-Chi Lin, Hsueh-I Lu:
Orderly spanning trees with applications to graph encoding and graph drawing.
506-515
Electronic Edition (ACM DL) BibTeX
- John Iacono:
Alternatives to splay trees with O(log n) worst-case access times.
516-522
Electronic Edition (ACM DL) BibTeX
- Andrej Brodnik, Svante Carlsson, Johan Karlsson, J. Ian Munro:
Worst case constant time priority queue.
523-528
Electronic Edition (ACM DL) BibTeX
- J. Ian Munro, Venkatesh Raman, Adam J. Storm:
Representing dynamic binary trees succinctly.
529-536
Electronic Edition (ACM DL) BibTeX
- Amos Fiat, Haim Kaplan:
Making data structures confluently persistent.
537-546
Electronic Edition (ACM DL) BibTeX
- Serge Abiteboul, Haim Kaplan, Tova Milo:
Compact labeling schemes for ancestor queries.
547-556
Electronic Edition (ACM DL) BibTeX
- János Csirik, David S. Johnson, Claire Kenyon:
Better approximation algorithms for bin covering.
557-566
Electronic Edition (ACM DL) BibTeX
- Aravind Srinivasan:
New approaches to covering and packing problems.
567-576
Electronic Edition (ACM DL) BibTeX
- Daniel W. Engels, Jon Feldman, David R. Karger, Matthias Ruhl:
Parallel processor scheduling with delay constraints.
577-585
Electronic Edition (ACM DL) BibTeX
- Edward G. Coffman Jr., George S. Lueker:
Approximation algorithms for extensible bin packing.
586-588
Electronic Edition (ACM DL) BibTeX
- Martin Skutella, Marc Uetz:
Scheduling precedence-constrained jobs with stochastic processing times on parallel machines.
589-590
Electronic Edition (ACM DL) BibTeX
- Alexander Kesselman, Yishay Mansour:
Loss-bounded analysis for differentiated services.
591-600
Electronic Edition (ACM DL) BibTeX
- Allan Borodin, Rafail Ostrovsky, Yuval Rabani:
Stability preserving transformations: packet routing networks with edge capacities and speeds.
601-610
Electronic Edition (ACM DL) BibTeX
- Ashish Goel, Adam Meyerson, Serge A. Plotkin:
Distributed admission control, scheduling, and routing with stale information.
611-619
Electronic Edition (ACM DL) BibTeX
- Joseph Hall, Jason D. Hartline, Anna R. Karlin, Jared Saia, John Wilkes:
On algorithms for efficient data migration.
620-629
Electronic Edition (ACM DL) BibTeX
- Gianluca De Marco, Andrzej Pelc:
Fast distributed graph coloring with O(Delta) colors.
630-635
Electronic Edition (ACM DL) BibTeX
- Sudipto Guha, Adam Meyerson, Kamesh Munagala:
Improved algorithms for fault tolerant facility location.
636-641
Electronic Edition (ACM DL) BibTeX
- Moses Charikar, Samir Khuller, David M. Mount, Giri Narasimhan:
Algorithms for facility location problems with outliers.
642-651
Electronic Edition (ACM DL) BibTeX
- Alan M. Frieze, Gregory B. Sorkin:
The probabilistic relationship between the assignment and asymmetric traveling salesman problems.
652-660
Electronic Edition (ACM DL) BibTeX
- Ivan D. Baev, Rajmohan Rajaraman:
Approximation algorithms for data placement in arbitrary networks.
661-670
Electronic Edition (ACM DL) BibTeX
- Thomas Erlebach, Klaus Jansen, Eike Seidel:
Polynomial-time approximation schemes for geometric graphs.
671-679
Electronic Edition (ACM DL) BibTeX
- Alon Efrat, Sariel Har-Peled, Leonidas J. Guibas, T. M. Murali:
Morphing between polylines.
680-689
Electronic Edition (ACM DL) BibTeX
- Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, Joan Antoni Sellarès, Diane L. Souvaine, Ileana Streinu, Anja Struyf:
Fast implementation of depth contours using topological sweep.
690-699
Electronic Edition (ACM DL) BibTeX
- Marshall W. Bern:
Computing the depth of a flat.
700-701
Electronic Edition (ACM DL) BibTeX
- Hana Chockler, Uri Zwick:
Which formulae shrink under random restrictions?
702-708
Electronic Edition (ACM DL) BibTeX
- Andrea E. F. Clementi, Angelo Monti, Riccardo Silvestri:
Selective families, superimposed codes, and broadcasting on unknown radio networks.
709-718
Electronic Edition (ACM DL) BibTeX
- Gabriel Istrate, Madhav V. Marathe, S. S. Ravi:
Adversarial models in evolutionary game dynamics.
719-720
Electronic Edition (ACM DL) BibTeX
- Dimitris Achlioptas, Arthur D. Chtcherba, Gabriel Istrate, Cristopher Moore:
The phase transition in 1-in-k SAT and NAE 3-SAT.
721-722
Electronic Edition (ACM DL) BibTeX
- Fan R. K. Chung, Ronald L. Graham, Frank Thomson Leighton:
Guessing secrets.
723-726
Electronic Edition (ACM DL) BibTeX
- Gopal Pandurangan, Eli Upfal:
Can entropy characterize performance of online algorithms?.
727-734
Electronic Edition (ACM DL) BibTeX
- Andrew V. Goldberg, Jason D. Hartline, Andrew Wright:
Competitive auctions and digital goods.
735-744
Electronic Edition (ACM DL) BibTeX
- James Aspnes, David F. Fischer, Michael J. Fischer, Ming-Yang Kao, Alok Kumar:
Towards understanding the predictability of stock markets from the perspective of computational complexity.
745-754
Electronic Edition (ACM DL) BibTeX
- Tak Wah Lam, Kar-Keung To:
Performance guarentee for online deadline scheduling in the presence of overload.
755-764
Electronic Edition (ACM DL) BibTeX
- Gerhard J. Woeginger:
Assigning chain-like tasks to a chain-like network.
765-766
Electronic Edition (ACM DL) BibTeX
- Richard J. Anderson, Brian Tjaden:
The inverse nearest neighbor problem with astrophysical applications.
767-768
Electronic Edition (ACM DL) BibTeX
- Ashish Goel, Piotr Indyk, Kasturi R. Varadarajan:
Reductions among high dimensional proximity problems.
769-778
Electronic Edition (ACM DL) BibTeX
- Stephen Alstrup, Thore Husfeldt, Theis Rauhe:
A cell probe lower bound for dynamic nearest-neighbor searching.
779-780
Electronic Edition (ACM DL) BibTeX
- Philip N. Klein, Thomas B. Sebastian, Benjamin B. Kimia:
Shape matching using edit-distance: an implementation.
781-790
Electronic Edition (ACM DL) BibTeX
- Vida Dujmovic, Sue Whitesides:
On validating planar worlds.
791-792
Electronic Edition (ACM DL) BibTeX
- Yijie Han:
Improved fast integer sorting in linear space.
793-796
Electronic Edition (ACM DL) BibTeX
- Ulrich Meyer:
Single-source shortest-paths on arbitrary directed graphs in linear average-case time.
797-806
Electronic Edition (ACM DL) BibTeX
- Christian A. Duncan, Stephen G. Kobourov, V. S. Anil Kumar:
Optimal constrained graph exploration.
807-814
Electronic Edition (ACM DL) BibTeX
- Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, Sven Thiel:
An efficient algorithm for the configuration problem of dominance graphs.
815-824
Electronic Edition (ACM DL) BibTeX
- Therese C. Biedl:
Linear reductions of maximum matching.
825-826
Electronic Edition (ACM DL) BibTeX
- David Eppstein, S. Muthukrishnan:
Internet packet filter management and rectangle geometry.
827-835
Electronic Edition (ACM DL) BibTeX
- Haim Kaplan, Robert Endre Tarjan, Kostas Tsioutsiouliklis:
Faster kinetic heaps and their use in broadcast scheduling.
836-844
Electronic Edition (ACM DL) BibTeX
- Michael A. Bender, Giridhar Pemmasani, Steven Skiena, Pavel Sumazin:
Finding least common ancestors in directed acyclic graphs.
845-854
Electronic Edition (ACM DL) BibTeX
- Eduardo Sany Laber, Ruy Luiz Milidiú, Artur Alves Pessoa:
On binary searching with non-uniform costs.
855-864
Electronic Edition (ACM DL) BibTeX
- Artur Czumaj, Christian Sohler:
Soft kinetic data structures.
865-872
Electronic Edition (ACM DL) BibTeX
- Eldar Fischer:
Testing graphs for colorable properties.
873-882
Electronic Edition (ACM DL) BibTeX
- Alon Amit, Nathan Linial, Jirí Matousek, Eyal Rozenman:
Random lifts of graphs.
883-894
Electronic Edition (ACM DL) BibTeX
- Justin A. Boyan, Michael Mitzenmacher:
IMproved results for route planning in stochastic transportation.
895-902
Electronic Edition (ACM DL) BibTeX
- Ted Carson, Russell Impagliazzo:
Hill-climbing finds random planted bisections.
903-909
Electronic Edition (ACM DL) BibTeX
- Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro:
On universally easy classes for NP-complete problems.
910-911
Electronic Edition (ACM DL) BibTeX
- Linyuan Lu:
The diameter of random massive graphs.
912-921
Electronic Edition (ACM DL) BibTeX
- Aravind Srinivasan:
Domatic partitions and the Lovász local lemma.
922-923
Electronic Edition (ACM DL) BibTeX
- Sriram V. Pemmaraju:
Equitable colorings extend Chernoff-Hoeffding bounds.
924-925
Electronic Edition (ACM DL) BibTeX
- Yevgeniy Dodis, Peter Winkler:
Universal configurations in light-flipping games.
926-927
Electronic Edition (ACM DL) BibTeX
- Jérémy Barbay, Claire Kenyon:
On the discrete Bak-Sneppen model of self-organized criticality.
928-933
Electronic Edition (ACM DL) BibTeX
Copyright © Tue May 27 18:13:16 2008
by Michael Ley (ley@uni-trier.de)
