7. SODA 1996:
Atlanta,
Georgia
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms,
28-30 January 1996,
Atlanta,
Georgia. ACM/SIAM
- Sundar Vishwanathan:
An O(log* n) Approximation Algorithm for the Asymmetric p-Center Problem.
1-5 BibTeX
- Aravind Srinivasan:
An Extension of the Lovász Local Lemma, and its Applications to Integer Programming.
6-15 BibTeX
- Gruia Calinescu, Cristina G. Fernandes, Ulrich Finkler, Howard J. Karloff:
A Better Approximation Algorithm for Finding Planar Subgraphs.
16-25 BibTeX
- Ka Wong Chong, Tak Wah Lam:
Improving Biconnectivity Approximation via Local Optimization.
26-35 BibTeX
- Marek Karpinski, Lawrence L. Larmore, Wojciech Rytter:
Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees.
36-41 BibTeX
- S. Muthukrishnan, Martin Müller:
Time and Space Efficient Method-Lookup for Object-Oriented Programs (Extended Abstract).
42-51 BibTeX
- Gerth Stølting Brodal:
Worst-Case Efficient Priority Queues.
52-58 BibTeX
- Mikkel Thorup:
On RAM Priority Queues.
59-67 BibTeX
- Baruch Awerbuch, Yossi Azar, Yair Bartal:
On-line Generalized Steiner Problem.
68-74 BibTeX
- Piotr Berman, Avrim Blum, Amos Fiat, Howard J. Karloff, Adi Rosén, Michael E. Saks:
Randomized Robot Navigation Algorithms.
75-84 BibTeX
- Sandy Irani, Vitus J. Leung:
Scheduling with Conflicts, and Applications to Traffic Signal Control.
85-94 BibTeX
- Yair Bartal, Stefano Leonardi, Alberto Marchetti-Spaccamela, Jiri Sgall, Leen Stougie:
Multiprocessor Scheduling with Rejection.
95-103 BibTeX
- Tetsuo Asano, Danny Z. Chen, Naoki Katoh, Takeshi Tokuyama:
Polynomial-Time Solutions to Image Segmentation.
104-113 BibTeX
- Matthew Dickerson, Daniel Scharstein:
Optimal Placement of Convex Polygons to Maximize Point Containment.
114-121 BibTeX
- Pankaj K. Agarwal, Mark de Berg, Dan Halperin, Micha Sharir:
Efficient Generation of k-Directional Assembly Sequences.
122-131 BibTeX
- Michael T. Goodrich:
Fixed-Dimensional Parallel Linesr Programming via epsilon-Relative-Approximations.
132-141 BibTeX
- Leslie A. Hall, David B. Shmoys, Joel Wein:
Scheduling to Minimize Average Completion Time: Off-line and On-line Algorithms.
142-151 BibTeX
- Michel X. Goemans, Jon M. Kleinberg:
An Improved Approximation Ratio for the Minimum Latency Problem.
152-158 BibTeX
- Xiaotie Deng, Nian Gu, Tim Brecht, KaiCheng Lu:
Preemptive Scheduling of Parallel Jobs on Multiprocessors.
159-167 BibTeX
- Eric Rémila:
Tiling a Figure Using a Height in a Tree.
168-174 BibTeX
- Marshall W. Bern, Barry Hayes:
The Complexity of Flat Origami.
175-183 BibTeX
- Marco Pellegrini:
Electrostatic Fields without Singularities: Theory and Algorithms.
184-191 BibTeX
- David Alberts, Giuseppe Cattaneo, Giuseppe F. Italiano:
An Empirical Study of Dynamic Graph Algorithms (Extended Abstract).
192-201 BibTeX
- Siu-Wing Cheng, Moon-Pun Ng:
Isomorphism Testing and Display of Symmetries in Dynamic Trees.
202-211 BibTeX
- Daniele Frigioni, Alberto Marchetti-Spaccamela, Umberto Nanni:
Fully Dynamic Output Bounded Single Source Shortest Path Problem (Extended Abstract).
212-221 BibTeX
- Sanjeev Khanna, Rajeev Motwani, Randall H. Wilson:
On Certificates and Lookahead in Dynamic Graph Problems.
222-231 BibTeX
- János Komlós, Yuan Ma, Endre Szemerédi:
Matching Nuts and Bolts in O(n log n) Time (Extended Abstract).
232-241 BibTeX
- Marek Piotrów:
Depth Optimal Sorting Networks Resistant to k Passive Faults.
242-251 BibTeX
- Mordecai J. Golin:
Limit Theorems for Minimum-Weight Triangulations, Other Euclidean Functionals, and Probabilistic Recurrence Relations (Extended Abstract).
252-260 BibTeX
- Andrei Z. Broder, Alan M. Frieze, Stephen Suen, Eli Upfal:
An Efficient Algorithm for the Vertex-Disjoint Paths Problem in Random Graphs.
261-268 BibTeX
- Anil Kamath, Omri Palmon, Serge A. Plotkin:
Routing and Admission Control in General Topology Networks with Poisson Arrivals.
269-278 BibTeX
- Milena Mihail, David Shallcross, Nate Dean, Marco Mostrel:
A Commercial Application of Survivable Network Design: ITP/INPLANS CCS Network Topology Analyzer.
279-287 BibTeX
- Adam L. Buchsbaum, Jan P. H. van Santen:
Selecting Training Inputs via Greedy Rank Covering.
288-295 BibTeX
- Robert Lupton, F. Miller Maley, Neal E. Young:
Data Collection for the Sloan Digital Sky Survey - A Network-Flow Heuristic.
296-303 BibTeX
- Sridhar Hannenhalli, Pavel A. Pevzner:
To Cut... or Not to Cut (Applications of Comparative Physical Maps in Molecular Evolution).
304-313 BibTeX
- Tandy Warnow, Donald Ringe, Ann Taylor:
Reconstructing the Evolutionary History of Natural Languages.
314-322 BibTeX
- Richard Cole, Ramesh Hariharan:
An O(n log n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees.
323-332 BibTeX
- Monika Rauch Henzinger, Valerie King, Tandy Warnow:
Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.
333-340 BibTeX
- David S. Johnson, Lyle A. McGeoch, Edward E. Rothberg:
Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound.
341-350 BibTeX
- Claire Kenyon, Yuval Rabani, Alistair Sinclair:
Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing (Preliminary Version).
351-358 BibTeX
- Claire Kenyon:
Best-Fit Bin-Packing with Random Order.
359-364 BibTeX
- Richa Agarwala, Vineet Bafna, Martin Farach, Babu O. Narayanan, Mike Paterson, Mikkel Thorup:
On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics).
365-372 BibTeX
- Paolo Ferragina, Roberto Grossi:
Fast String Searching in Secondary Storage: Theoretical Developments And Experimental Results.
373-382 BibTeX
- David R. Clark, J. Ian Munro:
Efficient Suffix Trees on Secondary Storage (extended Abstract).
383-391 BibTeX
- Christos Levcopoulos, Drago Krznaric:
Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation.
392-401 BibTeX
- Joseph S. B. Mitchell:
Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple New Method for the Geometric k-MST Problem.
402-408 BibTeX
- Hongyan Wang, Pankaj K. Agarwal:
Approximation Algorithms for Curvature-Constrained Shortest Paths.
409-418 BibTeX
- Esther M. Arkin, Martin Held, Christopher L. Smith:
Optimization Problems Related to Zigzag Pocket Machining (Extended Abstract).
419-428 BibTeX
- Michele Zito, Ida Pu, Martyn Amos, Alan Gibbons:
RNC Algorithms for the Uniform Generation of Combinatorial Structures.
429-437 BibTeX
- Shay Halperin, Uri Zwick:
Optimal randomized EREW PRAM Algorithms for Finding Spanning Forests and for other Basic Graph Connectivity Problems.
438-447 BibTeX
- David Bruce Wilson, James Gary Propp:
How to Get an Exact Sample From a Generic Markov Chain and Sample a Random Spanning Tree From a Directed Graph, Both Within the Cover Time.
448-457 BibTeX
- Richard M. Karp, Claire Kenyon, Orli Waarts:
Error-Resilient DNA Computation.
458-467 BibTeX
- Ehud Kalai:
Games, Computers, and O.R.
468-473 BibTeX
- James B. Orlin:
A Polynomial Time Primal Network Simplex Algorithm for Minimum Cost Flows (An Extended Abstract).
474-481 BibTeX
- Satoru Iwata:
A Capacity Scaling Algorithm for Convex Cost Submodular Flows.
482-489 BibTeX
- S. Thomas McCormick:
A Polynomial Algorithm for Abstract Maximum Flow.
490-497 BibTeX
- László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, Eugene M. Luks:
Multiplicative Equations over Commuting Matrices.
498-507 BibTeX
- Ming-Deh A. Huang, Ashwin J. Rao:
Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications.
508-517 BibTeX
- Victor Y. Pan:
A New Approach to Parallel Computation of Polynomial GCD and to Related Parallel Computations over Fields and Integer Rings.
518-527 BibTeX
- Harold N. Gabow:
Perfect Arborescence Packing in Preflow Mincut Graphs.
528-538 BibTeX
- Greg N. Frederickson, Roberto Solis-Oba:
Increasing the Weight of Minimum Spanning Trees.
539-546 BibTeX
- Donald Aingworth, Chandra Chekuri, Rajeev Motwani:
Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication).
547-553 BibTeX
- Leslie Ann Goldberg, Philip D. MacKenzie:
Analysis of Practical Backoff Protocols for Contention Resolution with Multiple Servers.
554-563 BibTeX
- Alain J. Mayer, Rafail Ostrovsky, Moti Yung:
Self-Stabilizing Algorithms for Synchronous Unidirectional Rings.
564-573 BibTeX
- Baruch Awerbuch, Yair Bartal, Amos Fiat:
Distributed Paging for General Networks.
574-583 BibTeX
Copyright © Wed Jun 4 18:56:12 2008
by Michael Ley (ley@uni-trier.de)
