7. SODA 1996: Atlanta, Georgia

• 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
  

Last update Sat May 18 19:48:52 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page