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