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