9. SODA 1998:
San Francisco,
California
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms,
25-27 January 1998,
San Francisco,
California. ACM/SIAM
- 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 Lp 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
Copyright © Tue Nov 10 00:15:47 2009
by Michael Ley (ley@uni-trier.de)
