SODA '98 Conference Program
This conference program is the complete list of sessions including individual talks and authors. A Program-at-a-Glance is available in an abbreviated table format that will help you make your travel arrangements and decide what talks to attend. Please refer to Program Updates for a list of changes made to this program since it was posted.
Saturday Evening, January 24
5:30 PM-7:30 PM Registration
6:00 PM-8:30 PM
Welcoming Reception
Redwood Room
Sunday Morning, January 25
7:30 AM-4:00 PM Registration
8:00 AM-8:50 AM Continental Breakfast
9:00 AM-10:35 AM Concurrent Sessions
-
Session 1
9:00 AM-10:35 AM
Chair: Howard Karloff, Georgia Institute of Technology
Gold Rush A Room
- 9:00-9:20 Analysis of a Local Search Heuristic for Facility Location Problems
- Madhukar R. Korupolu, C. Greg Plaxton and Rajmohan Rajaraman, University of Texas, Austin
- 9:25-9:45 Minimizing Service and Operation Costs of Periodic Scheduling
- Amotz Bar-Noy, Tel-Aviv University, Israel; Randeep Bhatia, University of Maryland, College Park; Joseph (Seffi) Naor, Technion-Israel Institute of Technoloy, Israel; and Baruch Schieber, IBM T. J. Watson Research Center
- 9:50-10:10 A Polynomial-time Approximation Scheme for Mimimum Routing Cost Spanning Trees
- B. Y. Wu, National Tsing Hua University, Taiwan, Republic of China; Giuseppe Lancia, Universit� di Padova, Italy; Vineet Bafna, SmithKline Beecham Pharmaceuticals; K.M. Chao, Providence University, Taiwan, Republic of China; R. Ravi, Carnegie Mellon University; and C.Y. Tang, National Tsing Hua University, Taiwan, Republic of China
- 10:15-10:35 A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP
- Sanjeev Arora, Princeton University; Michelangelo Grigni, Emory University; David Karger, Massachusetts Institute of Technology; Philip Klein, Brown University; and Andrzej Woloszyn, Emory University
-
Session 2
9:00 AM-10:35 AM
Chair: Madhu Sudan, IBM T. J. Watson Research Center
Gold Rush B Room
- 9:00-9:20 Computing Univariate GCDs over Number Fields
- Michael Monagan, Simon Fraser University, Canada; and Roger Margot, Eidgen�ssische Technische Hochschule-Zurich, Switzerland
- 9:25-9:45 Extended Hilbert Irreducibility and Its Applications
- Ming-Deh Huang and Yiu-Chung Wong, University of Southern California
- 9:50-10:10 Reconstructing Randomly Sampled Multivariate Polynomials from Highly Noisy Data
- Hal Wasserman, University of California, Berkeley
- 10:15-10:35 Computation of Approximate Polynomial Gcds and an Extension
- Victor Y. Pan, Lehman College, City University of New York, Bronx
10:35 AM-11:00 AM Coffee
11:00 AM-12:35 PM Concurrent Sessions
Sunday Afternoon, January 25
12:35 PM-2:00 PM Lunch (attendees are on their own)
IP1
Algorithms and Geometric Representations of Graphs
2:00 PM-3:00 PM
Chair: Howard Karloff, Georgia Institute of Technology
Gold Rush A Room
To represent a graph in a geometric way is a very natural and old problem. For example, it was proved by Steinitz early in this century that every 3-connected planar graph can be represented as the graph of vertices and edges of a (3-dimensional) polytope.
Representability of a graph in various geometric fashions turns out to be closely related to a number of basic properties of the graph. Moreover, computing these representations often helps in the design of algorithms for purely graph-theoretic problems.
Examples of such techniques include the representation of a graph by considering the edges as "rubber bands", which relate to higher connectivity, and also to mixing properties of random walks; orthogonal representations of graphs, which relate to independence, chromatic number, connectivity and tree-width; and other representations which relate to planarity and linkless embeddability.
Laszlo Lovasz
Department of Computer Science
Yale University
3:05 PM-4:15 PM Concurrent Sessions
-
Session 5
3:05 PM-4:15 PM
Chair: David Shmoys, Cornell University
Gold Rush A Room
- 3:05-3:25 Faster Algorithms for the Quickest Transshipment Problem
- Lisa Fleischer, Cornell University
- 3:30-3:50 Exact Arithmetic at Low Cost - A Case Study in Linear Programming
- Bernd G�rtner, Eidgen�ssische Technische Hochschule-Zurich, Switzerland
- 3:55-4:15 A Faster Algorithm for Minimum Cost Submodular Flows
- Satoru Iwata, Osaka University, Japan; S. Thomas McCormick, University of British Columbia, Canada; and Maiko Shigeno, Tokyo Institute of Technology, Japan
-
Session 6
3:05 PM-4:15 PM
Chair: Vojta Rodl, Emory University
Gold Rush B Room
- 3:05-3:25 The Ultimate Interval Graph Recognition Algorithm?
- Derek G. Corneil, University of Toronto, Canada; Stephan Olariu, Old Dominion University; and Lorna Stewart, University of Alberta, Canada
- 3:30-3:50 Sparse 0-1-Matrices and Forbidden Hypergraphs
- Claudia Bertram-Kretzberg and Thomas Hofmeister, Universit�t Dortmund, Germany; and Hanno Lefmann, Universit�t L�beck, Germany
- 3:55-4:15 Fast Backtracking Principles Applied to Find New Cages
- Brendan McKay, Australian National University, Australia;
Wendy Myrvold, University of Victoria, Canada; and Jacqueline Nadon, Sandwell Construction
4:15 PM-4:40 PM Coffee
4:40 PM-5:50 PM Concurrent Sessions
-
Session 7
4:40 PM-5:50 PM
Chair: Yuval Rabani, Technion-Israel Institute of Technology, Israel
Gold Rush A Room
- 4:40-5:00 Approximation Algorithms for Directed Steiner Problems
- Moses Charikar and Chandra Chekuri, Stanford University; To-Yat Cheung and Zuo Dai, City University of Hong Kong; Ashish Goel and Sudipto Guha, Stanford University; and Ming Li, City University of Hong Kong
- 5:05-5:25 Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables Per Constraint
- Uri Zwick, Tel-Aviv University
- 5:30-5:50 New Approximation Techniques for Some Ordering Problems
- Satish Rao, NEC Research Institute, Princeton; and Andrea W. Richa, Carnegie Mellon University
-
Session 8
4:40 PM-5:50 PM
Chair: Aravind Srinivasan, National University of Singapore, Singapore
Gold Rush B Room
- 4:40-5:00 On the Distributed Complexity of Computing Maximal Matchings
- Michal Hanckowiak and Michal Kar�nski, Adam Mickiewicz University, Poland; and Alessandro Panconesi, Humboldt University, Germany
- 5:05-5:25 The Power of Migration in Multi-Processor Scheduling of Real-Time Systems
- Gilad Koren, Netania College and Bar-Ilan University, Israel; Amihood Amir, Georgia Institute of Technology and Bar-Ilan University, Israel; and Emanuel Dar, Bar-Ilan
Univeristy, Israel
- 5:30-5:50 Computation in Noisy Radio Networks
- Eyal Kushilevitz, Technion-Israel Institute of Technology, Israel; and Yishay Mansour, Tel-Aviv University
Sunday Evening, January 25
Changed to Monday Evening, January 26
6:00 PM-7:00 PM
Business Meeting - SODA '99
Redwood Room
Monday Morning, January 26
7:30 AM-4:00 PM Registration
8:00 AM-8:50 AM Continental Breakfast
9:00 AM-10:35 AM Concurrent Sessions
-
Session 9
9:00 AM-10:35 AM
Chair: Howard Karloff, Georgia Institute of Technology
Gold Rush A Room
- 9:00-9:20 A 3/2-Approximation Algorithm for Sorting by Reversals
- David A. Christie, The University of Glasgow, Scotland
- 9:25-9:45 A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- Naveen Garg, Max-Planck-Institut f�r Informatik-Saarbr�cken, Germany; Goran Konjevod and R. Ravi, Carnegie Mellon University
- 9:50-10:10 A New Approximation Algorithm for the Planar Augmentation Problem
- Sergej Fialko and Petra Mutzel, Max-Planck Institut f�r Informatik-Saarbr�cken, Germany
- 10:15-10:35 Flow and Stretch Metrics for Scheduling Continuous Job Streams
- Michael Bender, Bell Laboratories, Lucent Technologies; Soumen Chakravarti, IBM Almaden Research Center; and S. Muthukrishnan, Bell Laboratories, Lucent Technologies
-
Session 10
9:00 AM-10:35 AM
Chair: Jeremy Spinrad, Vanderbilt University
Gold Rush B Room
- 9:00-9:20 Optimal Augmentation of a Biconnected Graph to a k-Edge-Connected and Triconnected Graph
- Toshimasa Ishii, Hiroshi Nagamochi and Toshihide Ibaraki, Kyoto University, Japan
- 9:25-9:45 Average-Case Analyses of First Fit and Random Fit Bin Packing
- Susanne Albers, Max-Planck-Institut fur Informatik-Saarbrucken, Germany; and Michael Mitzenmacher, Digital Equipment Corporation
- 9:50-10:10 A Probabilistic Algorithm for Updating Files over a Communication Link
- Alexandre V. Evfimievski, Moscow State University, Russia
- 10:15-10:35 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
10:35 AM-11:00 AM Coffee
11:00 AM-12:35 PM Concurrent Sessions
-
Session 11
11:00 AM-12:35 PM
Chair: Amos Fiat, Tel-Aviv University, Israel
Gold Rush A Room
- 11:00-11:20 Exploring Unknown Undirected Graphs
- Petrisor Panaite and Andrzej Pelc, Universit� du Quebec a Hull, Canada
- 11:25-11:45 On-line Randomized Call Control Revisited
- Stefano Leonardi, Max-Planck-Institut f�r Informatik-Saarbr�cken, Germany and Universit� di Roma "La Sapienza", Italy; Alberto Marchetti-Spaccamela and Alessio Presciutti, Universit� di Roma "La Sapienza", Italy; and Adi Ros�n, University of Toronto, Canada
- 11:50-12:10 Ring Routing and Wavelength Translation
- Gordon Wilfong and Peter Winkler, Bell Laboratories, Lucent Technologies
- 12:15-12:35 Direct Routing on Trees
- Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg and Mikkel Thorup, University of Copenhagen, Denmark
-
Session 12
11:00 AM-12:35 PM
Chair: Claire Kenyon, LRI, Université de Paris-Sud, France
Gold Rush B Room
- 11:00-11:20 Faster Random Generation of Linear Extensions
- Russ Bubley and Martin Dyer, University of Leeds, United Kingdom
- 11:25-11:45 Beating the 2\delta Bound for Approximately Counting Colourings: A Computer-Assisted Proof of Rapid Mixing
- Russ Bubley, Martin Dyer and Catherine Greenhill, University of Leeds, United Kingdom
- 11:50-12:10 Analysis of Random Processes via And-Or Tree Evaluation
- Micahel G. Luby and Michael Mitzenmacher, Digital Equipment Corporation; and M. Amin Shokrollahi, Universit�t Bonn, Germany
- 12:15-12:35 Output-Sensitive Generation of Random Events
- Paul B. Callahan, Eidgenossische Technische Hochschule-Zurich, Switzerland
Monday Afternoon, January 26
12:35 PM-2:00 PM Lunch (attendees are on their own)
IP2
Factoring: Facts and Fables
2:00 PM-3:00 PM
Chair: Amos Fiat, Tel-Aviv University, Israel
Gold Rush A Room
In theory, the security of most Public Key Cryptosystems is based on the assumption that a number theoretical problem (such as integer factorization or computing discrete logarithms) is hard. In practice, when using Public Key Cryptosystems, to secure Internet traffic for instance, the situation is not so clear. In this talk the speaker will discuss various security assumptions and will show how our credulity may lead to interesting business opportunities.
Arjen K. Lenstra
Citibank, N.A.,
Parsippany, NJ
3:05 PM-4:15 PM Concurrent Sessions
-
Session 13
3:05 PM-4:15 PM
Chair: Nati Linial, Hebrew University
Gold Rush A Room
- 3:05-3:25 On Approximating Rectangle Tiling and Packing
- Sanjeev Khanna and S. Muthukrishnan, Bell Laboratories, Lucent Technologies; and Mike Paterson, University of Warwick, United Kingdom
- 3:30-3:50 The Maximum Subforest Problem: Approximation and Exact Algorithms
- Ron Shamir and Dekel Tsur, Tel-Aviv University, Israel
- 3:55-4:15 Matroid Decomposition Methods for the Set Maxima Problem
- Vincenzo Liberatore, Rutgers University
-
Session 14
3:05 PM-4:15 PM
Chair: Yuval Rabani, Technion-Israel Institute of Technology, Israel
Gold Rush B Room
- 3:05-3:25 The Dynamic Servers Problem
- Moses Charikar, Stanford University; Dan Halperin, Tel-Aviv University, Israel; and Rajeev Motwani, Stanford University
- 3:30-3:50 Bounding the Diffuse Adversary
- Neal E. Young, Dartmouth College
- 3:55-4:15 Ancient and New Algorithms for Load Balancing in the Lp Norm
- Adi Avidor and Yossi Azar, Tel-Aviv University, Israel; and
Jiri Sgall, Mathematical Institute, Czech Republic
4:15 PM-4:40 PM Coffee
4:40 PM-5:50 PM Concurrent Sessions
-
Session 15
4:40 PM-5:50 PM
Chair: Jeremy Spinrad, Vanderbilt University
Gold Rush A Room
- 4:40-5:00 Optimal Edge Ranking of Trees in Linear Time
- Tak Wah Lam, University of Hong Kong; and Fung Ling Yue, City University of Hong Kong
- 5:05-5:25 Algorithms for the Maximum Subarray Problem Based on Matrix Multiplication
- Hisao Tamaki, Meiji University, Japan; and Takeshi Tokuyama, Tokyo Research Laboratory, Japan
- 5:30-5:50 An Experimental Study of Linear Programming-Based Approximation Algorithms for Scheduling Problems
- Martin W. P. Savelsbergh, Georgia Institute of Technology; R. N. Uma and Joel Wein, Polytechnic University
-
Session 16
4:40 PM-5:50 PM
Chair: Hal Kierstead, Arizona State University
Gold Rush B Room
- 4:40-5:00 Approximate String Matching: A Simpler Faster Algorithm
- Richard Cole, Courant Institute of Mathematical Sciences, New York University; and Ramesh Hariharan, Indian Institute of Science, India
- 5:05-5:25 Fast Distributed Algorithms for Brooks-Vizing Colourings
- David A. Grable and Alessandro Panconesi, Humboldt-Universit�t zu Berlin, Germany
- 5:30-5:50 Mutual Search
- Harry Buhrman, Centrum voor Wiskunde en Informatica, The Netherlands; Matthew Franklin, AT&T Research; Juan A. Garay, IBM T. J. Watson Research Center; Jaap-Henk Hoepman,
John Tromp and Paul Vitanyi, Centrum voor Wiskunde en Informatica, The Netherlands
Monday Evening, January 26
6:00 PM-7:00 PM
Business Meeting - SODA '99
Redwood Room
Tuesday Morning, January 27
7:30 AM-2:00 PM Registration
8:00 AM-8:50 AM Continental Breakfast
9:00 AM-10:35 AM Concurrent Sessions
-
Session 17
9:00 AM-10:35 AM
Chair: Andrew Goldberg, NEC Research Institute
Gold Rush A Room
- 9:00-9:20 Better Random Sampling Algorithms for Flows in Undirected Graphs
- David Karger, Massachusetts Institute of Technology
- 9:25-9:45 Augmenting Undirected Edge Connectivity in O (n squared) Time
- Andras Benczur and David Karger, Massachusetts Institute of Technology
- 9:50-10:10 Go With the Winners for Graph Bisection
- Tassos Dimitriou and Russell Impagliazzo, University of California, San Diego
- 10:15-10:35 Two New Upper Bounds for SAT
- Edward A. Hirsch, Steklov Institute of Mathematics, Russian Academy of Sciences, Russia
-
Session 18
9:00 AM-10:35 AM
Chair: Rao Kosaraju, Johns Hopkins University
Gold Rush B Room
- 9:00-9:20 The Analysis of Hybrid Trie Structures
- Julien Cl�ment, INRIA-Rocquencourt, France and Universit� de Caen, France; Philippe Flajolet, INRIA-Rocquencourt, France; and Brigitte Vallee, Universit� de Caen, France
- 9:25-9:45 Finger Search Trees with Constant Insertion Time
- Gerth S. Brodal, Max-Planck-Institut fur Informatik-Saarbrucken, Germany
- 9:50-10:10 Faster Deterministic Sorting and Priority Queues in Linear Space
- Mikkel Thorup, University of Copenhagen, Denmark
- 10:15-10:35 Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries
- Peter Bro Miltersen, University of Aarhus, Denmark
10:35 AM-11:00 Coffee
11:00 AM-12:35 PM Concurrent Sessions
-
Session 19
11:00 AM-12:35 PM
Chair: Sampath Kannan, University of Pennsylvania
Gold Rush A Room
- 11:00-11:20 On Local Register Allocation
- Martin Farach and Vincenzo Liberatore, Rutgers University
- 11:25-11:45 Linear-time Register Allocation For a Fixed Number of Registers
- Hans Bodlaender, University of Utrecht, The Netherlands; Jens Gustedt, Technische Universit�t Berlin, Germany; and Jan Arne Telle, Universiteit Bergen, Norway
- 11:50-12:10 Multi-Item Inventory Staggering Problems: Heuristics and Bounds
- Chung-Piaw Teo, Jihong Ou and Kok-Choon Tan, National University of Singapore, Singapore
- 12:15-12:35 Finding a Large Hidden Clique in a Random Graph
- Noga Alon, Michael Krivelevich and Benny Sudakov, Tel-Aviv University, Israel
-
Session 20
11:00 AM-12:35 PM
Chair: Marshall Bern, Xerox Palo Alto Research Center
Gold Rush B Room
- 11:00-11:20 Learning Deterministic Finite Automata from Smallest Counterexamples
- Andreas Birkendorf, Andreas Boeker and Hans Ulrich Simon, Universit�t Dortmund, Germany
- 11:25-11:45 On the Exact Worst Case Complexity of Planar Point Location
- Udo Adamy and Raimund Seidel, Universit�t des Saarlandes, Germany
- 11:50-12:10 Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs
- David Eppstein, University of California, Irvine
- 12:15-12:35 Analysis of First-Come-First-Serve Parallel Job Scheduling
- Uwe Schwiegelshohn and Ramin Yahyapour, Universit�t Dortmund, Germany
Tuesday Afternoon, January 27
12:35 PM-2:00 PM Lunch (attendees are on their own)
IP3
Four Decades of Optimal Network Design
2:00 PM-3:00 PM
Chair: David Shmoys , Cornell University
Gold Rush A Room
The optimal design of telecommunication and other networks poses considerable modeling and algorithmic challenges to the applied mathematics, computer science, and operations research communities. In this problem domain, (mixed) integer programming models often contain thousands or even millions of variables and constraints. The speaker will trace the evolution of optimization methods for network design, reviewing some major developments, including the design and analysis of heuristics, Lagrangian relaxation, dual ascent methods, and polyhedral combinatorics. He will also summarize several applications and suggest some open research issues as well as attempt to suggest why network design remains among the most computationally elusive of all combinatorial optimization problems and continues to pose significant challenges to the research community.
Thomas L. Magnanti
Operations Research Center
Massachusetts Institute of Technology
3:05 PM-4:40 PM Concurrent Sessions
-
Session 21
3:05 PM-4:40 PM
Chair: Daniel Spielman, Massachusetts Institute of Technology
Gold Rush A Room
- 3:05-3:25 Spatial Codes and the Hardness of String Folding Problems
- Ashwin Nayak and Alistair Sinclair, University of California, Berkeley; and Uri Zwick, Tel-Aviv University, Israel
- 3:30-3:50 Greedy Strikes Back: Improved Facility Location Algorithms
- Sudipto Guha, Stanford University; and Samir Khuller, University of Maryland, College Park
- 3:55-4:15 Exact and Approximation Algorithms for Clustering
- Pankaj K. Agarwal and Cecilia M. Procopiuc, Duke University
- 4:20-4:40 Authoritative Sources in a Hyperlinked Environment
- Jon M. Kleinberg, Cornell University
-
Session 22
3:05 PM-4:15 PM
Chair: Nati Linial, Hebrew University, Israel
Gold Rush B Room
- 3:05-3:25 Hiding Cliques for Cryptographic Security
- Ari Juels, RSA Laboratories, Bedford, Massachusetts; and
Marcus Peinado, German National Research Center for Information Technology, Germany
- 3:30-3:50 Theory and Practice of I/O-Efficient Algorithms for Multidimensional Batched Searching Problems
- Lars Arge and Octavian Procopiuc, Duke University; Sridhar Ramaswamy and Torsten Suel, Bell Laboratories, Lucent Technologies; and Jeffrey Scott Vitter, Duke University
- 3:55-4:15 Identification of Gene Regulatory Networks by Strategic Gene Disruptions and Gene Overexpressions
- Tatsuya Akutsu, University of Tokyo, Japan; Satoru Kuhara, Kyushu University, Japan; Osamu Maruyama and Satoru Miyano, University of Tokyo, Japan
4:40 PM Conference adjourns
SODA'98 Homepage | Program Updates| Registration | Hotel | Transportation | Program-at-a-Glance |
Author Index |
MMD, 1/13/98