3. SODA 1992: Orlando, Florida

• Mihalis Yannakakis:
  On the Approximation of Maximum Satisfiability. 1-9
  
• Boris Pittel:
  On Likely Solutions of a Stable Matching Problem. 10-15
  
• Aditi Dhagat, Péter Gács, Peter Winkler:
  On Playing "Twenty Questions" with a Liar. 16-22
  
• Ronitt Rubinfeld, Madhu Sudan:
  Self-Testing Polynomial Functions Efficiently and Over Rational Domains. 23-32
  
• László Babai:
  Deciding Finiteness of Matrix Groups in Las Vegas Polynomial Time. 33-40
  
• Joel Spencer:
  The Probabilistic Method. 41-47
  
• David Eppstein:
  Approximating the Minimum Weight Triangulation. 48-57
  
• Pankaj K. Agarwal, Jirí Matousek:
  Relative Neighborhood Graphs in Three Dimensions. 58-65
  
• Nina Amenta:
  Finding a Line Transversal of Axial Objects in Three Dimensions. 66-71
  
• Pankaj K. Agarwal, Micha Sharir, Sivan Toledo:
  Applications of Parametric Searching in Geometric Optimization. 72-82
  
• David Eppstein:
  New Algorithms for Minimum Area k-gons. 83-88
  
• Kurt Mehlhorn, Micha Sharir, Emo Welzl:
  Tail Estimates for the Space Complexity of Randomized Incremental Algorithms. 89-93
  
• Philip D. MacKenzie:
  Load Balancing Requires Omega(log^*n) Expected Time. 94-99
  
• Thomas R. Mathies:
  Percolation Theory and Computing with Faulty Arrays of Processors. 100-103
  
• Eran Aharonson, Hagit Attiya:
  Counting Networks with Arbitrary Fan-Out. 104-113
  
• Jyh-Jong Tsay:
  Searching Tree Structures on a Mesh of Processors. 114-123
  
• Yu Lin-Kriz, Victor Y. Pan:
  On Parallel Complexity of Integer Linear Programming, GCD and the Iterated mod Function. 124-137
  
• Milena Mihail, Peter Winkler:
  On the Number of Eularian Orientations of a Graph. 138-145
  
• Xiaofeng Han, Pierre Kelsen, Vijaya Ramachandran, Robert Endre Tarjan:
  Computing Minimal Spanning Subgraphs in Linear Time. 146-156
  
• V. King, S. Rao, Robert Endre Tarjan:
  A Faster Deterministic Maximum Flow Algorithm. 157-164
  
• Jianxiu Hao, James B. Orlin:
  A Faster Algorithm for Finding the Minimum Cut in a Graph. 165-174
  
• Takeshi Tokuyama, Jun Nakano:
  Efficient Algorithms for the Hitchcock Transportation Problem. 175-184
  
• Tomasz Radzik:
  Minimizing Capacity Violations in a Transshipment Network. 185-194
  
• Martin Grötschel:
  Theoretical and Practical Aspects of Combinatorial Problem Solving. 195
  
• Marek Chrobak, Lawrence L. Larmore:
  Generosity Helps, or an 11-Competitive Algorithm for Three Servers. 196-202
  
• Yossi Azar, Joseph Naor, Raphael Rom:
  The Competitiveness of On-Line Assignments. 203-210
  
• Magnús M. Halldórsson, Mario Szegedy:
  Lower Bounds for On-Line Graph Coloring. 211-216
  
• Lucas Chi Kwong Hui, Charles U. Martel:
  On Efficient Unsuccessful Search. 217-227
  
• Sandy Irani, Anna R. Karlin, Steven Phillips:
  Strongly Competitive Algorithms for Paging with Locality of Reference. 228-236
  
• Eldad Bar-Eli, Piotr Berman, Amos Fiat, Peiyuan Yan:
  On-Line Navigation in a Room. 237-249
  
• Hanna Baumgarten, Hermann Jung, Kurt Mehlhorn:
  Dynamic Point Location in General Subdivisions. 250-258
  
• Leonidas J. Guibas, Rajeev Motwani, Prabhakar Raghavan:
  The Robot Localization Problem in Two Dimensions. 259-268
  
• Esther M. Arkin, Joseph S. B. Mitchell, Subhash Suri:
  Optimal Link Path Queries in a Simple Polygon. 269-279
  
• Christian Schwarz, Michiel H. M. Smid:
  An O(n log n log log n) Algorithm for the On-Line Closest Pair Problem. 280-285
  
• Dan E. Willard:
  Applications of the Fusion Tree Method to Computational Geometry and Searching. 286-295
  
• Joseph S. B. Mitchell, Subhash Suri:
  Separation and Approximation of Polyhedral Objects. 296-306
  
• Michel X. Goemans, David P. Williamson:
  A General Approximation Technique for Constrained Forest Problems. 307-316
  
• Martin Fürer, Balaji Raghavachari:
  Approximating the Minimum Degree Spanning Tree to Within One from the Optimal Degree. 317-324
  
• Piotr Berman, Viswanathan Ramaiyer:
  Improved Approximations for the Steiner Tree Problem. 325-334
  
• Joseph Cheriyan, John H. Reif:
  Directed s-t Bumberings, Rubber Bands, and Testing Digraph k-Vertex Connectivity. 335-344
  
• André E. Kézdy, Patrick McGuinness:
  Sequential and Parallel Algorithms to Find a K₅ Minor. 345-356
  
• H. Narayanan, Huzur Saran, Vijay V. Vazirani:
  Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arboresences and Edge-Disjoint Spanning Trees. 357-366
  
• J. Ian Munro, Thomas Papadakis, Robert Sedgewick:
  Deterministic Skip Lists. 367-375
  
• Teofilo F. Gonzalez:
  The On-Line d-Dimensional Dictionary Problem. 376-385
  
• Daniel M. Yellin:
  Algorithms for Subset Testing and Finding Maximal Sets. 386-392
  
• Svante Carlsson, Jingsen Chen:
  The Complexity of Heaps. 393-402
  
• Noga Alon, Yossi Azar:
  Comparison-Sorting and Selecting in Totally Monotone Matrices. 403-408
  
• Andrew Stein, Michael Werman:
  Finding the Repeated Median Regression Line. 409-413
  
• Colin McDiarmid, Ryan Hayward:
  Strong Concentration for Quicksort. 414-421
  
• Wojciech Szpankowski:
  (Un)expected Behavior of Typical Suffix Trees. 422-431
  
• Dan Gusfield, K. Balasubramanian, Dalit Naor:
  Parametric Optimization of Sequence Alignment. 432-439
  
• Amihood Amir, Gary Benson:
  Two-Dimensional Periodicity and Its Applications. 440-452
  
• Gad M. Landau, Uzi Vishkin:
  Pattern Matching in a Digitized Image. 453-462
  
• Susanne Albers, Torben Hagerup:
  Improved Parallel Integer Sorting Without Concurrent Writing. 463-472