11. SODA 2000: San Francisco, California, USA

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

Last update Thu May 23 06:19:28 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page