11. SODA 2000:
San Francisco,
California,
USA
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms,
January 9-11,
2000,
San Francisco,
CA,
USA. ACM/SIAM
- Daniel Bienstock:
epsilon-Approximate linear programs: new bounds and computation.
1-2
Electronic Edition (ACM DL) BibTeX
- Markus Eiglsperger, Ulrich Fößmeier, Michael Kaufmann:
Orthogonal graph drawing with constraints.
3-11
Electronic Edition (ACM DL) BibTeX
- Alberto Caprara, Giuseppe Lancia, See-Kiong Ng:
Fast practical solution of sorting by reversals.
12-21
Electronic Edition (ACM DL) BibTeX
- Mayur Datar, Abhiram G. Ranade:
Commuting with delay prone buses.
22-29
Electronic Edition (ACM DL) BibTeX
- Artur Czumaj, Christian Scheideler:
Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma.
30-39
Electronic Edition (ACM DL) BibTeX
- Jan Kratochvíl, Zsolt Tuza:
On the complexity of bicoloring clique hypergraphs of graphs (extended abstract).
40-41
Electronic Edition (ACM DL) BibTeX
- Ryan Hayward, Jeremy Spinrad, R. Sritharan:
Weakly chordal graph algorithms via handles.
42-49
Electronic Edition (ACM DL) BibTeX
- Vasek Chvátal, Jean Fonlupt, L. Sun, A. Zemirline:
Recognizing dart-free perfect graphs.
50-53
Electronic Edition (ACM DL) BibTeX
- Stefan Langerman, William L. Steiger:
An optimal algorithm for hyperplane depth in the plane.
54-59
Electronic Edition (ACM DL) BibTeX
- Hanno Lefmann:
On Heilbronn's problem in higher dimension.
60-64
Electronic Edition (ACM DL) BibTeX
- Alexander Below, Jesús A. De Loera, Jürgen Richter-Gebert:
Finding minimal triangulations of convex 3-polytopes is NP-hard.
65-66
Electronic Edition (ACM DL) BibTeX
- Michael Murphy, David M. Mount, Carl W. Gable:
A point-placement strategy for conforming Delaunay tetrahedralization.
67-74
Electronic Edition (ACM DL) BibTeX
- Robin Thomas:
Digraph minors and algorithms (abstract only).
75
Electronic Edition (ACM DL) BibTeX
- Michel X. Goemans, Martin Skutella:
Cooperative facility location games.
76-85
Electronic Edition (ACM DL) BibTeX
- Neal E. Young:
K-medians, facility location, and the Chernoff-Wald bound.
86-95
Electronic Edition (ACM DL) BibTeX
- Takao Asano, David P. Williamson:
Improved approximation algorithms for MAX SAT.
96-105
Electronic Edition (ACM DL) BibTeX
- Robert D. Carr, Lisa Fleischer, Vitus J. Leung, Cynthia A. Phillips:
Strengthening integrality gaps for capacitated network design and covering problems.
106-115
Electronic Edition (ACM DL) BibTeX
- Robert D. Carr, Santosh Vempala, Jacques Mandler:
Towards a 4/3 approximation for the asymmetric traveling salesman problem.
116-125
Electronic Edition (ACM DL) BibTeX
- Olivier Dubois, Yacine Boufkhad, Jacques Mandler:
Typical random 3-SAT formulae and the satisfiability threshold.
126-127
Electronic Edition (ACM DL) BibTeX
- Pavel Pudlák, Russell Impagliazzo:
A lower bound for DLL algorithms for k-SAT (preliminary version).
128-136
Electronic Edition (ACM DL) BibTeX
- Toshiya Itoh, Yoshinori Takei, Jun Tarui:
On permutations with limited independence.
137-146
Electronic Edition (ACM DL) BibTeX
- Andrei Z. Broder, Uriel Feige:
Min-Wise versus linear independence (extended abstract).
147-154
Electronic Edition (ACM DL) BibTeX
- Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu:
Hamiltonicity and colorings of arrangement graphs.
155-164
Electronic Edition (ACM DL) BibTeX
- Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan:
Testing and spot-checking of data streams (extended abstract).
165-174
Electronic Edition (ACM DL) BibTeX
- Adam L. Buchsbaum, Donald F. Caldwell, Kenneth Ward Church, Glenn S. Fowler, S. Muthukrishnan:
Engineering the compression of massive tables: an experimental approach.
175-184
Electronic Edition (ACM DL) BibTeX
- Z. Cohen, Yossi Matias, S. Muthukrishnan, Süleyman Cenk Sahinalp, Jacob Ziv:
On the temporal HZY compression scheme.
185-186
Electronic Edition (ACM DL) BibTeX
- Charles Knessl, Wojciech Szpankowski:
Height in a digital search tree and the longest phrase of the Lempel-Ziv scheme.
187-196
Electronic Edition (ACM DL) BibTeX
- Graham Cormode, Mike Paterson, Süleyman Cenk Sahinalp, Uzi Vishkin:
Communication complexity of document exchange.
197-206
Electronic Edition (ACM DL) BibTeX
- Petra Schuurman, Gerhard J. Woeginger:
Scheduling a pipelined operator graph.
207-212
Electronic Edition (ACM DL) BibTeX
- Chandra Chekuri, Sanjeev Khanna:
A PTAS for the multiple knapsack problem.
213-222
Electronic Edition (ACM DL) BibTeX
- Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, An Zhu:
Approximation algorithms for data placement on parallel disks.
223-232
Electronic Edition (ACM DL) BibTeX
- Wolfgang Espelage, Egon Wanke:
Movement minimization in conveyor flow shop processing.
233-234
Electronic Edition (ACM DL) BibTeX
- Rolf H. Möhring, Martin Skutella, Frederik Stork:
Forcing relations for AND/OR precedence constraints.
235-236
Electronic Edition (ACM DL) BibTeX
- Richard Arratia, Béla Bollobás, Gregory B. Sorkin:
The interlace polynomial: a new graph polynomial.
237-245
Electronic Edition (ACM DL) BibTeX
- Martin E. Dyer, Catherine S. Greenhill:
The complexity of counting graph homomorphisms (extended abstract).
246-255
Electronic Edition (ACM DL) BibTeX
- Frank Ruskey, Joe Sawada:
A fast algorithm to generate unlabeled necklaces.
256-262
Electronic Edition (ACM DL) BibTeX
- Christian Kuhlmann, Hans-Ulrich Simon:
Construction of visual secret sharing schemes with almost optimal contrast.
263-272
Electronic Edition (ACM DL) BibTeX
- Giovanni Di Crescenzo:
Sharing one secret vs. sharing many secrets: tight bounds on the average improvement ratio.
273-274
Electronic Edition (ACM DL) BibTeX
- Deborah Goldman, Sorin Istrail, Giuseppe Lancia, Antonio Piccolboni, Brian Walenz:
Algorithmic strategies in combinatorial chemistry.
275-284
Electronic Edition (ACM DL) BibTeX
- David Bryant, John Tsang, Paul E. Kearney, Ming Li:
Computing the quartet distance between evolutionary trees.
285-286
Electronic Edition (ACM DL) BibTeX
- Vincent Berry, David Bryant, Tao Jiang, Paul E. Kearney, Ming Li, Todd Wareham, Haoyong Zhang:
A practical algorithm for recovering the best supported edges of an evolutionary tree (extended abstract).
287-296
Electronic Edition (ACM DL) BibTeX
- Laxmi Parida, Isidore Rigoutsos, Aris Floratos, Daniel E. Platt, Yuan Gao:
Pattern discovery on character sets and real-valued data: linear bound on irredundant motifs and an efficient polynomial time algorithm.
297-308
Electronic Edition (ACM DL) BibTeX
- Yi Li, Philip M. Long, Aravind Srinivasan:
Improved bounds on the sample complexity of learning.
309-318
Electronic Edition (ACM DL) BibTeX
- Samir Khuller, Randeep Bhatia, Robert Pless:
On local search and placement of meters in networks.
319-328
Electronic Edition (ACM DL) BibTeX
- Eran Halperin:
Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs.
329-337
Electronic Edition (ACM DL) BibTeX
- Goran Konjevod, R. Ravi:
An approximation algorithm for the covering Steiner problem.
338-344
Electronic Edition (ACM DL) BibTeX
- Robert D. Carr, Srinivas Doddi, Goran Konjevod, Madhav V. Marathe:
On the red-blue set cover problem.
345-353
Electronic Edition (ACM DL) BibTeX
- Piotr Indyk, Suresh Venkatasubramanian:
Approximate congruence in nearly linear time.
354-360
Electronic Edition (ACM DL) BibTeX
- Peter N. Yianilos:
Locally lifting the curse of dimensionality for nearest neighbor search (extended abstract).
361-370
Electronic Edition (ACM DL) BibTeX
- Piotr Indyk:
Dimensionality reduction techniques for proximity problems.
371-378
Electronic Edition (ACM DL) BibTeX
- Sunil Arya, Ho-Yam Addy Fu:
Expected-case complexity of approximate nearest neighbor searching.
379-388
Electronic Edition (ACM DL) BibTeX
- Ting Chen, Ming-Yang Kao, Matthew Tepel, John Rush, George M. Church:
A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry.
389-398
Electronic Edition (ACM DL) BibTeX
- Éva Czabarka, Goran Konjevod, Madhav V. Marathe, Allon G. Percus, David C. Torney:
Algorithms for optimizing production DNA sequencing.
399-408
Electronic Edition (ACM DL) BibTeX
- J. Kevin Lanctot, Ming Li, En-Hui Yang:
Estimating DNA sequence entropy.
409-418
Electronic Edition (ACM DL) BibTeX
- Daniel G. Brown, Todd J. Vision, Steven D. Tanksley:
Selective mapping: a discrete optimization approach to selecting a population subset for use in a high-density genetic mapping project.
419-428
Electronic Edition (ACM DL) BibTeX
- David Applegate, Robert E. Bixby, Vasek Chvátal, William Cook:
Cutting planes and the traveling salesman problem (abstract only).
429
Electronic Edition (ACM DL) BibTeX
- Friedhelm Meyer auf der Heide, Berthold Vöcking, Matthias Westermann:
Caching in networks (extended abstract).
430-439
Electronic Edition (ACM DL) BibTeX
- Matthew Andrews:
Instability of FIFO in session-oriented networks.
440-447
Electronic Edition (ACM DL) BibTeX
- Matthew Andrews, Lisa Zhang:
The effects of temporary sessions on network performance.
448-457
Electronic Edition (ACM DL) BibTeX
- Costas Busch, Maurice Herlihy, Roger Wattenhofer:
Randomized greedy hot-potato routing.
458-466
Electronic Edition (ACM DL) BibTeX
- David Gamarnik:
On deciding stability of scheduling policies in queueing systems.
467-476
Electronic Edition (ACM DL) BibTeX
- William S. Evans, David G. Kirkpatrick:
Restructuring ordered binary trees.
477-486
Electronic Edition (ACM DL) BibTeX
- Rasmus Pagh:
Faster deterministic dictionaries.
487-493
Electronic Edition (ACM DL) BibTeX
- Michael T. Goodrich:
Competitive tree-structured dictionaries.
494-495
Electronic Edition (ACM DL) BibTeX
- Mikkel Thorup:
Even strongly universal hashing is pretty fast.
496-497
Electronic Edition (ACM DL) BibTeX
- Stephen Alstrup, Jens P. Secher, Mikkel Thorup:
Word encoding tree connectivity works.
498-499
Electronic Edition (ACM DL) BibTeX
- Yunhong Zhou, Subhash Suri:
Algorithms for minimum volume enclosing simplex in R3.
500-509
Electronic Edition (ACM DL) BibTeX
- Pankaj K. Agarwal, Boris Aronov, Micha Sharir:
Exact and approximation algorithms for minimum-width cylindrical shells.
510-517
Electronic Edition (ACM DL) BibTeX
- Olivier Devillers, Franco P. Preparata:
Evaluating the cylindricity of a nominally cylindrical point set.
518-527
Electronic Edition (ACM DL) BibTeX
- Pankaj K. Agarwal, Pavan K. Desikan:
Approximation algorithms for layered manufacturing.
528-537
Electronic Edition (ACM DL) BibTeX
- Pankaj K. Agarwal, Cecilia Magdalena Procopiuc:
Approximation algorithms for projective clustering.
538-547
Electronic Edition (ACM DL) BibTeX
- Luca Becchetti, Stefano Leonardi, S. Muthukrishnan:
Scheduling to minimize average stretch without migration.
548-557
Electronic Edition (ACM DL) BibTeX
- Yair Bartal, S. Muthukrishnan:
Minimizing maximum response time in scheduling broadcasts.
558-559
Electronic Edition (ACM DL) BibTeX
- Mark Brehob, Eric Torng, Patchrawat Uthaisombut:
Applying extra-resource analysis to load balancing.
560-561
Electronic Edition (ACM DL) BibTeX
- Ashish Goel, Kamesh Munagala:
Balancing Steiner trees and shortest path trees online.
562-563
Electronic Edition (ACM DL) BibTeX
- Todd Gormley, Nick Reingold, Eric Torng, Jeffery Westbrook:
Generating adversaries for request-answer games.
564-565
Electronic Edition (ACM DL) BibTeX
- Adam L. Buchsbaum, Jeffery Westbrook:
Maintaining hierarchical graph views.
566-575
Electronic Edition (ACM DL) BibTeX
- Andrei Z. Broder, Robert Krauthgamer, Michael Mitzenmacher:
Improved classification via connectivity information.
576-585
Electronic Edition (ACM DL) BibTeX
- Omer Berkman, Michal Parnas, Jiri Sgall:
Efficient dynamic traitor tracing.
586-595
Electronic Edition (ACM DL) BibTeX
- Sanjeev Khanna, Francis Zane:
Watermarking maps: hiding information in structured data.
596-605
Electronic Edition (ACM DL) BibTeX
- April Rasala, Gordon T. Wilfong:
Strictly non-blocking WDM cross-connects.
606-615
Electronic Edition (ACM DL) BibTeX
- Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum, Michael Mitzenmacher:
An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract).
616-624
Electronic Edition (ACM DL) BibTeX
- Mark Huber:
A faster method for sampling independent sets.
625-626
Electronic Edition (ACM DL) BibTeX
- László Babai, Igor Pak:
Strong bias of group generators: an obstacle to the ``product replacement algorithm''.
627-635
Electronic Edition (ACM DL) BibTeX
- Dana Randall, Gary D. Yngve:
Random three-dimensional tilings of Aztec octahedra and tetrahedra: an extension of domino tilings.
636-645
Electronic Edition (ACM DL) BibTeX
- Eric Rémila:
An algebraic method to compute a shortest path of local flips between two tilings.
646-653
Electronic Edition (ACM DL) BibTeX
- Geir Agnarsson, Magnús M. Halldórsson:
Coloring powers of planar graphs.
654-662
Electronic Edition (ACM DL) BibTeX
- Sanjeev Khanna, Joseph Naor, F. Bruce Shepherd:
Directed network design with orientation constraints.
663-671
Electronic Edition (ACM DL) BibTeX
- Mirela Damian-Iordache, Sriram V. Pemmaraju:
A (2 + epsilon)-approximation scheme for minimum domination on circle graphs.
672-679
Electronic Edition (ACM DL) BibTeX
- Sundar Vishwanathan:
An approximation algorithm for finding a long path in Hamiltonian graphs.
680-685
Electronic Edition (ACM DL) BibTeX
- Ernst Althaus, Kurt Mehlhorn:
TSP-based curve reconstruction in polynomial time.
686-695
Electronic Edition (ACM DL) BibTeX
- Philip N. Klein, Srikanta Tirthapura, Daniel Sharvit, Benjamin B. Kimia:
A tree-edit-distance algorithm for comparing simple, closed shapes.
696-704
Electronic Edition (ACM DL) BibTeX
- Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos:
Computing the arrangement of curve segments: divide-and-conquer algorithms via sampling.
705-706
Electronic Edition (ACM DL) BibTeX
- Danny Z. Chen, Ovidiu Daescu, Yang Dai, Naoki Katoh, Xiaodong Wu, Jinhui Xu:
Optimizing the sum of linear fractional functions and applications.
707-716
Electronic Edition (ACM DL) BibTeX
- Alan M. Frieze:
Edge-disjoint paths in expander graphs.
717-725
Electronic Edition (ACM DL) BibTeX
- Wun-Tat Chan, Francis Y. L. Chin, Hing-Fung Ting:
Escaping a grid by edge-disjoint paths.
726-734
Electronic Edition (ACM DL) BibTeX
- Matthew S. Levine:
Fast randomized algorithms for computing minimum {3, 4, 5, 6}-way cuts.
735-742
Electronic Edition (ACM DL) BibTeX
- Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro:
Adaptive set intersections, unions, and differences.
743-752
Electronic Edition (ACM DL) BibTeX
- Gene Myers:
The whole genome assembly of Drosophila.
753
Electronic Edition (ACM DL) BibTeX
- Sanjeev Arora, George Karakostas:
A 2+epsilon approximation algorithm for the k-MST problem.
754-759
Electronic Edition (ACM DL) BibTeX
- David S. Johnson, Maria Minkoff, Steven Phillips:
The prize collecting Steiner tree problem: theory and practice.
760-769
Electronic Edition (ACM DL) BibTeX
- Gabriel Robins, Alexander Zelikovsky:
Improved Steiner tree approximation in graphs.
770-779
Electronic Edition (ACM DL) BibTeX
- Weiping Shi, Chen Su:
The rectilinear Steiner arborescence problem is NP-complete.
780-787
Electronic Edition (ACM DL) BibTeX
- Anupam Gupta:
Improved bandwidth approximation for trees.
788-793
Electronic Edition (ACM DL) BibTeX
- Amihood Amir, Moshe Lewenstein, Ely Porat:
Faster algorithms for string matching with k mismatches.
794-803
Electronic Edition (ACM DL) BibTeX
- Gad M. Landau, Michal Ziv-Ukelson:
On the shared substring alignment problem.
804-814
Electronic Edition (ACM DL) BibTeX
- Amihood Amir, Ayelet Butman, Moshe Lewenstein:
Real scaled matching.
815-816
Electronic Edition (ACM DL) BibTeX
- Amihood Amir, Gad M. Landau, Dina Sokol:
Inplace run-length 2d compressed search.
817-818
Electronic Edition (ACM DL) BibTeX
- Stephen Alstrup, Gerth Stølting Brodal, Theis Rauhe:
Pattern matching in dynamic texts.
819-828
Electronic Edition (ACM DL) BibTeX
- Sandeep Sen, Siddhartha Chatterjee:
Towards a theory of cache-efficient algorithms.
829-838
Electronic Edition (ACM DL) BibTeX
- Yossi Matias, Eran Segal, Jeffrey Scott Vitter:
Efficient bundle sorting.
839-848
Electronic Edition (ACM DL) BibTeX
- Peter Sanders, Sebastian Egner, Jan H. M. Korst:
Fast concurrent access to parallel disks.
849-858
Electronic Edition (ACM DL) BibTeX
- Adam L. Buchsbaum, Michael H. Goldwasser, Suresh Venkatasubramanian, Jeffery Westbrook:
On external memory graph traversal.
859-860
Electronic Edition (ACM DL) BibTeX
- Bogdan S. Chlebus, Leszek Gasieniec, Alan Gibbons, Andrzej Pelc, Wojciech Rytter:
Deterministic broadcasting in unknown radio networks.
861-870
Electronic Edition (ACM DL) BibTeX
- Maurice Queyranne, Maxim Sviridenko:
New and improved algorithms for minsum shop scheduling.
871-878
Electronic Edition (ACM DL) BibTeX
- Cynthia A. Phillips, R. N. Uma, Joel Wein:
Off-line admission control for general scheduling problems.
879-888
Electronic Edition (ACM DL) BibTeX
- Esther M. Arkin, Refael Hassin:
Approximating the maximum quadratic assignment problem.
889-890
Electronic Edition (ACM DL) BibTeX
- Donald Aingworth, Rajeev Motwani, Jeffrey D. Oldham:
Accurate approximations for Asian options.
891-900
Electronic Edition (ACM DL) BibTeX
- Jeff Erickson:
Finite-resolution hidden surface removal.
901-909
Electronic Edition (ACM DL) BibTeX
- Alon Efrat, Leonidas J. Guibas, Olaf A. Hall-Holt, Li Zhang:
On incremental rendering of silhouette maps of polyhedral scene.
910-917
Electronic Edition (ACM DL) BibTeX
- Hamish Carr, Jack Snoeyink, Ulrike Axen:
Computing contour trees in all dimensions.
918-926
Electronic Edition (ACM DL) BibTeX
- Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, David C. Lin, Joseph S. B. Mitchell, T. M. Murali:
Sweeping simple polygons with a chain of guards.
927-936
Electronic Edition (ACM DL) BibTeX
- Philip N. Klein:
Finding the closest lattice vector when it's unusually close.
937-941
Electronic Edition (ACM DL) BibTeX
- José Coelho de Pina, José Soares:
A new bound for the Carathéodory rank of the bases of a matroid.
942-943
Electronic Edition (ACM DL) BibTeX
- S. Thomas McCormick, Akiyoshi Shioura:
Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks.
944-952
Electronic Edition (ACM DL) BibTeX
- Victor Y. Pan:
Nearly optimal computations with structured matrices.
953-962
Electronic Edition (ACM DL) BibTeX
Copyright © Sat May 16 23:41:52 2009
by Michael Ley (ley@uni-trier.de)
