Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
Sponsored by ACM Sigact and SIAM Activity Group on DM
January 25-27, 1998
Holiday Inn Golden Gateway Hotel,
San Francisco, California
List of Accepted Papers to be Presented at the Symposium
- A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP
- Sanjeev Arora and Michelangelo Grigni and David Karger and Philip Klein and Andrzej Woloszyn
- Kinetic BSPs for Intersecting Segments and Disjoint Triangles
- Pankaj K. Agarwal and Jeff Erickson and Leonidas K. Guibas
- A polylogarithmic approximation algorithm for the group Steiner problem
- Naveen Garg and Goran Konjevod and R. Ravi
- Computing Univariate GCDs over Number Fields
- Michael Monagan and Roger Margot
- Minimizing Service and Operation Costs of Periodic Scheduling
- Amotz Bar-Noy and Randeep Bhatia and Joseph (Seffi) Naor and Baruch Schieber
- Analysis of a Local Search Heuristic for Facility Location Problems
- Madhukar R. Korupolu and C. Greg Plaxton and Rajmohan Rajaraman
- On Local Register Allocation
- Martin Farach and Vincenzo Liberatore
- Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries
- Peter Bro Miltersen
- Average-Case Analyses of First Fit and Random Fit Bin Packing
- Susanne Albers and Michael Mitzenmacher
- Faster Algorithms for the Quickest Transshipment Problem
- Lisa Fleischer
- Finding a large hidden clique in a random graph
- Noga Alon and Michael Krivelevich and Benny Sudakov
- Breaking the $2\Delta$ Bound for Approximately Counting Colourings: A
Computer-Assisted Proof of Rapid Mixing
- Russ Bubley and Martin Dyer and Catherine Greenhill
- Faster deterministic sorting and priority queues in linear space
- Mikkel Thorup
- Planar Point Location Close to the Information-theoretic Lower Bound
- Udo Adamy and Raimund Seidel
- Extended Hilbert Irreducibility and its Applications
- Ming-Deh Huang and Yiu-Chung Wong
- A 3/2-Approximation Algorithm for Sorting by Reversals
- David A. Christie
- Collision Detection in Aspect and Scale Bounded Polyhedra
- Subhash Suri and Philip M. Hubbard and John F. Hughes
- The Dynamic Servers Problem
- Moses Charikar and Dan Halperin and Rajeev Motwani
- Multi-Item Inventory Staggering Problems: Heuristics and Bounds
- Chung-Piaw Teo, Jihong Ou, and Kok-Choon Tan, National University
of Singapore, Singapore
- A Polynomial-time Approximation Scheme for Minimum Routing Cost Spanning Trees
- B. Y. Wu, G. Lancia, V. Bafna, K. M. Chao, R. Ravi and C. Y. Tang.
- Mutual Search
- Harry Buhrman, Matthew Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul Vitanyi
- A New Approximation Algorithm for the Planar Augmentation Problem
- Sergej Fialko and Petra Mutzel
- New Approximation Techniques for Some Ordering Problems
- Satish Rao and Andrea W. Richa
- Bounding the Diffuse Adversary
- Neal E. Young
- Flow and Stretch Metrics for Scheduling Continuous Job Streams
- Michael Bender and Soumen Chakravarti and S. Muthukrishnan
- Computation of Approximate Polynomial Gcds and an Extension
- Victor Y. Pan, Lehman College, City University of New York, Bronx
- Edge-Connectivity Augmentation with Partition Constraints
- Jorgen Bang-Jensen, Odense University, Denmark; Harold N. Gabow,
University of Colorado, Boulder; Tibor Jordan, Odense University,
Denmark; and Zoltan Szigeti, Universite Paris VI, France
- An Experimental Study of Linear Programming-Based Scheduling Heuristics
- Martin W.P.Savelsbergh and R.N.Uma and Joel Wein
- An Efficient Algorithm for the Three-Dimensional Diameter Problem
- Sergei N. Bespamyatnikh
- Analysis of Random Processes via And-Or Tree Evaluation
- Micahel G. Luby and Michael Mitzenmacher and M. Amin Shokrollahi
- Theory and Practice of I/O-Efficient Algorithms for Multidimensional Batched Searching Problems
- Lars Arge and Octavian Procopiuc and Sridhar Ramaswamy and Torsten Suel and Jeffrey Scott Vitter
- Learning Deterministic Finite Automata from Smallest Counterexamples
- Andreas Birkendorf and Andreas Boeker and Hans Ulrich Simon
- Optimal Augmentation of a Biconnected Graph to a k-Edge-Connected and
Triconnected Graph
- ISHII Toshimasa and NAGAMOCHI Hiroshi and IBARAKI Toshihide
- Algorithms for the Maximum Subarray Problem Based on Matrix Multiplication
- Hisao Tamaki and Takeshi Tokuyama
- Sparse 0-1-Matrices and Forbidden Hypergraphs
- Claudia Bertram-Kretzberg and Thomas Hofmeister and Hanno Lefmann
- The Ultimate Interval Graph Recognition Algorithm?
- Derek G. Corneil and Stephan Olariu and Lorna Stewart
- Fast Backtracking Principles Applied to Find New Cages
- Brendan McKay and Wendy Myrvold and Jacqueline Nadon
- Matroid Decomposition Methods for the Set Maxima Problem
- Vincenzo Liberatore
- Output-sensitive generation of random events
- Paul B. Callahan
- Finger Search Trees with Constant Insertion Time
- Gerth S. Brodal
- Improved Routing on Trees
- Stephen Alstrup and Jacob Holm and Kristian de Lichtenberg and Mikkel Thorup, University of Copenhagen, Denmark
- Authoritative Sources in a Hyperlinked Environment
- Jon M. Kleinberg
- Computation in Noisy Radio Networks
- Eyal Kushilevitz and Yishay Mansour
- The Analysis of Hybrid Trie Structures
- Julien Clement and Philippe Flajolet and Brigitte Vallee
- On-Line File Caching
- Neal E. Young
- Identification of Gene Regulatory Networks by Strategic Gene Disruptions and Gene Amplifications
- Tatsuya Akutsu and Satoru Kuhara and Osamu Maruyama and Satoru Miyano
- Linear-Time Register Allocation for a Fixed Number of Registers
- Hans Bodlaender, Jens Gustedt and Jan Arne Telle
- Approximation Algorithms for Directed Steiner Problems
- Charikar and Chekuri and Cheung and Dai and Goel and Guha and Li
- Hiding Cliques for Cryptographic Security
- Ari Juels and Marcus Peinado
- Reconstructing Randomly Sampled Multivariate Polynomials from Highly Noisy Data
- Hal Wasserman
- On-line Randomized Call Control Revisited
- Stefano Leonardi and Alberto Marchetti-Spaccamela and Alessio Presciutti and Adi Ros\'{e}n
- Analysis of First-Come-First-Serve Parallel Job Scheduling
- Uwe Schwiegelshohn and Ramin Yahyapour
- The Power of Migration in Multi-Processor Scheduling of Real-Time Systems
- Gilad Koren and Amihood Amir and Emanuel Dar
- The Maximum Subforest Problem: Approximation and Exact Algorithms
- Ron Shamir and Dekel Tsur
- Exact and Approximation Algorithms for Clustering
- Pankaj K. Agarwal and Cecilia M. Procopiuc
- Ring Routing and Wavelength Translation
- Gordon Wilfong and Peter Winkler
- Approximate String Matching: A Faster Simpler Algorithm
- R. Cole and R. Hariharan
- Two New Upper Bounds for SAT
- Edward A. Hirsch
- Greedy Strikes Back: Improved Facility Location Algorithms
- Sudipto Guha and Samir Khuller
- Spatial Codes and the Hardness of String Folding Problems
- Ashwin Nayak and Alistair Sinclair and Uri Zwick
- Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables Per Constraint
- Uri Zwick
- Fast Distributed Algorithms for Brooks-Vizing Colourings
- David A. Grable and Alessandro Panconesi
- Faster Random Generation of Linear Extensions
- Russ Bubley and Martin Dyer
- Exploring Unknown Undirected Graphs
- Petrisor Panaite and Andrzej Pelc
- A Probabilistic Algorithm for Updating Files over a Communication Link
- Alexandre V. Evfimievski
- LRU is Better than FIFO
- Marek Chrobak and John Noga
- A Faster Algorithm for Minimum Cost Submodular Flows
- Satoru Iwata and S. Thomas McCormick and Maiko Shigeno
- Optimal Edge Ranking of Trees in Linear Time
- Tak Wah Lam and Fung Ling Yue
- Go with the Winners for Graph Bisection
- Tassos Dimitriou and Russell Impagliazzo
- Competitive algorithms for multilevel caching and relaxed list update
- Marek Chrobak and John Noga
- Quadratic-time Algorithms for Edge-Connectivity Augmentation and Splitting Off
- Andras Benczur and David Karger
- Better Sampling Algorithms for Maximum Flows in Undirected Graphs
- David Karger
- Ancient and New Algorithms for Load Balancing in the L_p Norm
- Adi Avidor and Yossi Azar and Jiri Sgall
- On the distributed complexity of computing maximal matchings
- Michal Hanckoviak and Michal Karonski and Alessandro Panconesi
- I/O-efficient algorithms for contour-line extraction and planar graph blocking
- Pankaj K. Agarwal and Lars Arge and T. M. Murali and Kasturi R. Varadarajan and Jeffrey S. Vitter
- Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs
- David Eppstein
- On Approximating Rectangle Tiling and Packing
- Sanjeev Khanna and S. Muthukrishnan and Mike Paterson
- Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control
- Ashish Goel and Monika Henzinger and Serge Plotkin
- Exact Arithmetic at Low Cost - A Case Study in Linear Programming
- Bernd Gaertner
Back to SODA'98 Call for Papers
MMD, Created 9/10/97
Updated, 9/15/97