9. SODA 1998: San Francisco, California

• Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman:
  Analysis of a Local Search Heuristic for Facility Location Problems. 1-10
  
• Amotz Bar-Noy, Randeep Bhatia, Joseph Naor, Baruch Schieber:
  Minimizing Service and Operation Costs of Periodic Scheduling (Extended Abstract). 11-20
  
• Bang Ye Wu, Giuseppe Lancia, Vineet Bafna, Kun-Mao Chao, R. Ravi, Chuan Yi Tang:
  A Polynomial Time Approximation Scheme for Minimum Routing Cost Spanning Trees. 21-32
  
• Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, Andrzej Woloszyn:
  A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP. 33-41
  
• Michael B. Monagan, Roger Margot:
  Computing Univariate GCDs over Number Fields. 42-49
  
• Ming-Deh A. Huang, Yiu-Chung Wong:
  Extended Hilbert Irreducibility and its Applications. 50-58
  
• Hal Wasserman:
  Reconstructing Randomly Sampled Multivariate Polynomials from Highly Noisy Data. 59-67
  
• Victor Y. Pan:
  Approximate Polynomials Gcds, Padé Approximation, Polynomial Zeros and Bipartite Graphs. 68-77
  
• Marek Chrobak, John Noga:
  LRU is Better than FIFO. 78-81
  
• Neal E. Young:
  On-Line File Caching. 82-86
  
• Marek Chrobak, John Noga:
  Competive Algorithms for Multilevel Caching and Relaxed List Update (Extended Abstract). 87-96
  
• Ashish Goel, Monika Rauch Henzinger, Serge A. Plotkin:
  Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control. 97-106
  
• Pankaj K. Agarwal, Jeff Erickson, Leonidas J. Guibas:
  Kinetic Binary Space Partitions for Intersecting Segments and Disjoint Triangles (Extended Abstract). 107-116
  
• Pankaj K. Agarwal, Lars Arge, T. M. Murali, Kasturi R. Varadarajan, Jeffrey Scott Vitter:
  I/O-Efficient Algorithms for Contour-line Extraction and Planar Graph Blocking (Extended Abstract). 117-126
  
• Subhash Suri, Philip M. Hubbard, John F. Hughes:
  Collision Detection in Aspect and Scale Bounded Polyhedra. 127-136
  
• Sergei Bespamyatnikh:
  An Efficient Algorithm for the Three-Dimensional Diameter Problem. 137-146
  
• Lisa Fleischer:
  Faster Algorithms for the Quickest Transshipment Problem with Zero Transit Times. 147-156
  
• Bernd Gärtner:
  Exact Arithmetic at Low Cost - A Case Study in Linear Programming. 157-166
  
• Satoru Iwata, S. Thomas McCormick, Maiko Shigeno:
  A Faster Algorithm for Minimum Cost Submodular Flows. 167-174
  
• Derek G. Corneil, Stephan Olariu, Lorna Stewart:
  The Ultimate Interval Graph Recognition Algorithm? (Extended Abstract). 175-180
  
• Claudia Bertram-Kretzberg, Thomas Hofmeister, Hanno Lefmann:
  Sparse 0-1-Matrices and Forbidden Hypergraphs (Extended Abstract). 181-187
  
• Brendan D. McKay, Wendy J. Myrvold, Jacqueline Nadon:
  Fast Backtracking Principles Applied to Find New Cages. 188-191
  
• Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, Ming Li:
  Approximation Algorithms for Directed Steiner Problems. 192-200
  
• Uri Zwick:
  Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint. 201-210
  
• Satish Rao, Andréa W. Richa:
  New Approximation Techniques for Some Ordering Problems. 211-218
  
• Michal Hanckowiak, Michal Karonski, Alessandro Panconesi:
  On the Distributed Complexity of Computing Maximal Matchings. 219-225
  
• Gilad Koren, Amihood Amir, Emanuel Dar:
  The Power of Migration in Multi-Processor Scheduling of Real-Time Systems. 226-235
  
• Eyal Kushilevitz, Yishay Mansour:
  Computation in Noisy Radio Networks. 236-243
  
• David A. Christie:
  A 3/2-Approximation Algorithm for Sorting by Reversals. 244-252
  
• Naveen Garg, Goran Konjevod, R. Ravi:
  A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem. 253-259
  
• Sergej Fialko, Petra Mutzel:
  A New Approximation Algorithm for the Planar Augmentation Problem. 260-269
  
• Michael A. Bender, Soumen Chakrabarti, S. Muthukrishnan:
  Flow and Stretch Metrics for Scheduling Continuous Job Streams. 270-279
  
• Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki:
  Optimal Augmentation to Make a Graph k-Edge-Connected and Triconnected. 280-289
  
• Susanne Albers, Michael Mitzenmacher:
  Average-Case Analyses of First Fit and Random Fit Bin Packing. 290-299
  
• Alexandre V. Evfimievski:
  A Probabilistic Algorithm for Updating Files over a Communication Link. 300-305
  
• Jørgen Bang-Jensen, Harold N. Gabow, Tibor Jordán, Zoltán Szigeti:
  Edge-Connectivity Augmentation with Partition Constraints. 306-315
  
• Petrisor Panaite, Andrzej Pelc:
  Exploring Unknown Undirected Graphs. 316-322
  
• Stefano Leonardi, Alberto Marchetti-Spaccamela, Alessio Presciutti, Adi Rosén:
  On-line Randomized Call Control Revisited. 323-332
  
• Gordon T. Wilfong, Peter Winkler:
  Ring Routing and Wavelength Translation. 333-341
  
• Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup:
  Direct Routing on Trees (Extended Abstract). 342-349
  
• Russ Bubley, Martin E. Dyer:
  Faster Random Generation of Linear Extensions. 350-354
  
• Russ Bubley, Martin E. Dyer, Catherine S. Greenhill:
  Beating the 2 Delta Bound for Approximately Counting Colourings: A Computer-Assisted Proof of Rapid Mixing. 355-363
  
• Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi:
  Analysis of Random Processes via And-Or Tree Evaluation. 364-373
  
• Paul B. Callahan:
  Output-Sensitive Generation of Random Events. 374-383
  
• Sanjeev Khanna, S. Muthukrishnan, Mike Paterson:
  On Approximating Rectangle Tiling and Packing. 384-393
  
• Ron Shamir, Dekel Tsur:
  The Maximum Subforest Problem: Approximation and Exact Algorithms (Extended Abstract). 394-399
  
• Vincenzo Liberatore:
  Matroid Decomposition Methods for the Set Maxima Problem. 400-409
  
• Moses Charikar, Dan Halperin, Rajeev Motwani:
  The Dynamic Servers Problem. 410-419
  
• Neal E. Young:
  Bounding the Diffuse Adversary. 420-425
  
• Adi Avidor, Yossi Azar, Jiri Sgall:
  Ancient and New Algorithms for Load Balancing in the L_p Norm. 426-435
  
• Tak Wah Lam, Fung Ling Yue:
  Optimal Edge Ranking of Trees in Linear Time. 436-445
  
• Hisao Tamaki, Takeshi Tokuyama:
  Algorithms for the Maxium Subarray Problem Based on Matrix Multiplication. 446-452
  
• Martin W. P. Savelsbergh, R. N. Uma, Joel Wein:
  An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems. 453-462
  
• Richard Cole, Ramesh Hariharan:
  Approximate String Matching: A Simpler Faster Algorithm. 463-472
  
• David A. Grable, Alessandro Panconesi:
  Fast Distributed Algorithms for {Brooks-Vizing} Colourings. 473-480
  
• Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi:
  Mutual Search (Extended Abstract). 481-489
  
• David R. Karger:
  Better Random Sampling Algorithms for Flows in Undirected Graphs. 490-499
  
• András A. Benczúr, David R. Karger:
  Augmenting Undirected Edge Connectivity in Õ(n²) Time. 500-509
  
• Tassos Dimitriou, Russell Impagliazzo:
  Go with the Winners for Graph Bisection. 510-520
  
• Edward A. Hirsch:
  Two New Upper Bounds for SAT. 521-530
  
• Julien Clément, Philippe Flajolet, Brigitte Vallée:
  The Analysis of Hybrid Trie Structures. 531-539
  
• Gerth Stølting Brodal:
  Finger Search Trees with Constant Insertion Time. 540-549
  
• Mikkel Thorup:
  Faster Deterministic Sorting and Priority Queues in Linear Space. 550-555
  
• Peter Bro Miltersen:
  Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries. 556-563
  
• Martin Farach, Vincenzo Liberatore:
  On Local Register Allocation. 564-573
  
• Hans L. Bodlaender, Jens Gustedt, Jan Arne Telle:
  Linear-Time Register Allocation for a Fixed Number of Registers. 574-583
  
• Chung-Piaw Teo, Jihong Ou, Kok-Choon Tan:
  Multi-Item Inventory Staggering Problems: Heuristic and Bounds. 584-593
  
• Noga Alon, Michael Krivelevich, Benny Sudakov:
  Finding a Large Hidden Clique in a Random Graph. 594-598
  
• Andreas Birkendorf, Andreas Böker, Hans-Ulrich Simon:
  Learning Deterministic Finite Automata from Smallest Counterexamples. 599-608
  
• Udo Adamy, Raimund Seidel:
  On the Exact Worst Case Query Complexity of Planar Point Location. 609-618
  
• David Eppstein:
  Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs. 619-628
  
• Uwe Schwiegelshohn, Ramin Yahyapour:
  Analysis of First-Come-First-Serve Parallel Job Scheduling. 629-638
  
• Ashwin Nayak, Alistair Sinclair, Uri Zwick:
  Spatial Codes and the Hardness of String Folding Problems (Extended Abstract). 639-648
  
• Sudipto Guha, Samir Khuller:
  Greedy Strikes Back: Improved Facility Location Algorithms. 649-657
  
• Pankaj K. Agarwal, Cecilia Magdalena Procopiuc:
  Exact and Approximation Algorithms for Clustering (Extended Abstract). 658-667
  
• Jon M. Kleinberg:
  Authoritative Sources in a Hyperlinked Environment. 668-677
  
• Ari Juels, Marcus Peinado:
  Hiding Cliques for Cryptographic Security. 678-684
  
• Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter:
  Theory and Practice of I/O-Efficient Algorithms for Multidimensional Batched Searching Problems (Extended Abstract). 685-694
  
• Tatsuya Akutsu, Satoru Kuhara, Osamu Maruyama, Satoru Miyano:
  Identification of Gene Regulatory Networks by Strategic Gene Disruptions and Gene Overexpressions. 695-702
  

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