5. SODA 1994: Arlington, Virginia

• Daniel P. Huttenlocher, Jon M. Kleinberg:
  Comparing Point Sets Under Projection. 1-7
  
• Jon M. Kleinberg:
  On-line Search in a Simple Polygon. 8-15
  
• Christoph Burnikel, Kurt Mehlhorn, Stefan Schirra:
  On Degeneracy in Geometric Computations. 16-23
  
• Pankaj K. Agarwal, Subhash Suri:
  Surface Approximation and Geometric Partitions. 24-33
  
• Sigal Ar, Jin-yi Cai:
  Reliable Benchmarks Using Numerical Instability. 34-43
  
• Mihail N. Kolountzakis:
  An Effective Additive Basis for the Integers. 44-47
  
• Eric Bach:
  Exact Analysis of a Priority Queue Algorithm for Random Variate Generation. 48-56
  
• Katalin Friedl, Zsolt Hátsági, Alexander Shen:
  Low-degree Tests. 57-64
  
• Samuel R. Buss, Peter N. Yianilos:
  Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours. 65-76
  
• David Eppstein:
  Average Case Analysis of Dynamic Geometric Optimization. 77-86
  
• Alon Efrat, Micha Sharir:
  A Near-Linear Algorithm for the Planar Segment Center Problem. 87-97
  
• Rex A. Dwyer, William F. Eddy:
  Maximal Empty Ellipsoids. 98-102
  
• Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, Kristina Vuskovic:
  Recognizing Balanced 0, +/- Matrices. 103-111
  
• John Turek, Uwe Schwiegelshohn, Joel L. Wolf, Philip S. Yu:
  Scheduling Parallel Tasks to Minimize Average Response Time. 112-121
  
• David S. Johnson, Andrea S. LaPaugh, Ron Y. Pinter:
  Minimizing Channel Density by Lateral Shifting of Components. 122-131
  
• David R. Karger, Steven J. Phillips, Eric Torng:
  A Better Algorithm for an Ancient Scheduling Problem. 132-140
  
• Jonathan Aronson, Martin E. Dyer, Alan M. Frieze, Stephen Suen:
  On the Greedy Heuristic for Matchings. 141-149
  
• Barun Chandra, Howard J. Karloff, Craig A. Tovey:
  New Results on the Old k-Opt Algorithm for the TSP. 150-159
  
• David Eppstein:
  Clustering for Faster Network Simplex Pivots. 160-166
  
• Walter Ludwig, Prasoon Tiwari:
  Scheduling Malleable and Nonmalleable Parallel Tasks. 167-176
  
• Samir Khuller, Balaji Raghavachari, Neal E. Young:
  Approximating the Minimum Equivalent Diagraph. 177-186
  
• Yossi Matias, Jeffrey Scott Vitter, Neal E. Young:
  Approximate Data Structures with Applications. 187-194
  
• S. Rao Kosaraju:
  An Optimal RAM Implementation of Catenable Min Double-ended Queues. 195-203
  
• Johannes A. La Poutré, Jeffery Westbrook:
  Dynamic Two-Connectivity with Backtracking. 204-212
  
• Kurt Mehlhorn, R. Sundar, Christian Uhrig:
  Maintaining Dynamic Sequences Under Equality-Tests in Polylogarithmic Time. 213-222
  
• Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, David P. Williamson:
  Improved Approximation Algorithms for Network Design Problems. 223-232
  
• Manica Aggarwal, Naveen Garg:
  A Scaling Technique for Better Network Design. 233-240
  
• Michael T. Goodrich, Yossi Matias, Uzi Vishkin:
  Optimal Parallel Approximation for Prefix Sums and Integer Sorting. 241-250
  
• Danny Dolev, Yuval Harari, Nathan Linial, Noam Nisan, Michal Parnas:
  Neighborhood Preserving Hashing and Approximate Queries. 251-259
  
• Victor Y. Pan:
  New Techniques for Approximating Complex Polynomial Zeros. 260-270
  
• Don Coppersmith, C. Andrew Neff:
  Roots of a Polynomial and its Derivatives. 271-279
  
• Giovanni Gallo, Bhubaneswar Mishra:
  The Complexity of Resolvent Resolved. 280-289
  
• John H. Reif, Stephen R. Tate:
  Dynamic Algebraic Algorithms. 290-301
  
• Richard J. Lipton, Andrew Tomkins:
  Online Interval Scheduling. 302-311
  
• Baruch Awerbuch, Yair Bartal, Amos Fiat, Adi Rosén:
  Competitive Non-Preemptive Call Control. 312-320
  
• Baruch Awerbuch, Yossi Azar, Serge A. Plotkin, Orli Waarts:
  Competitive Routing of Virtual Circuits with Unknown Duration. 321-327
  
• Lisa Hellerstein, Collette R. Coullard:
  Learning Binary Matroid Ports. 328-335
  
• Martin E. Dyer, Alan M. Frieze, Mark Jerrum:
  Approximately Counting Hamilton Cycles in Dense Graphs. 336-343
  
• Reuven Bar-Yehuda, Dan Geiger, Joseph Naor, Ron M. Roth:
  Approximation Algorithms for the Vertex Feedback Set Problem with Applications to Constraint Satisfaction and Bayesian Inference. 344-354
  
• David P. Williamson, Michel X. Goemans:
  Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. 355-364
  
• Piotr Berman, Martin Fürer:
  Approximating Maximum Independent Set in Bounded Degree Graphs. 365-371
  
• Ming-Yang Kao, Yuan Ma, Michael Sipser, Yiqun Lisa Yin:
  Optimal Constructions of Hybrid Algorithms. 372-381
  
• Carsten Lund, Nick Reingold:
  Linear Programs for Randomized On-Line Algorithms. 382-391
  
• P. Krishnan, Jeffrey Scott Vitter:
  Optimal Prediction for Prefetching in the Worst Case. 392-401
  
• Prasad Tetali:
  Design of On-line Algorithms Using Hitting Times. 402-411
  
• Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan:
  Efficient Routing and Scheduling Algorithms for Optical Networks. 412-423
  
• David R. Karger:
  Using Randomized Sparsification to Approximate Minimum Cuts. 424-432
  
• Bruce Hoppe, Éva Tardos:
  Polynomial Time Algorithms for Some Evacuation Problems. 433-441
  
• Joseph Cheriyan:
  A Las Vegas O(n^2.38) Algorithm for the Cardinality of a Maximum Matching. 442-451
  
• Keith D. Gremban, Gary L. Miller, Shang-Hua Teng:
  Moments of Inertia and Graph Separators. 452-461
  
• Serge A. Plotkin, Satish Rao, Warren D. Smith:
  Shallow Excluded Minors and Improved Graph Decompositions. 462-470
  
• John D. Kececioglu, Dan Gusfield:
  Reconstructing a History of Recombinations from a Set of Sequences. 471-480
  
• Martin Farach, Mikkel Thorup:
  Fast Comparison of Evolutionary Trees. 481-488
  
• Farid Alizadeh, Richard M. Karp, Deborah K. Weisser, Geoffrey Zweig:
  Physical Mapping of Chromosomes Using Unique Probes. 489-500
  
• Amir M. Ben-Amram, Omer Berkman, Costas S. Iliopoulos, Kunsoo Park:
  The Subtree Max Gap Problem with Application to Parallel String Covering. 501-510
  
• Dennis Moore, William F. Smyth:
  Computing the Covers of a String in Linear Time. 511-515
  
• Boris V. Cherkassky, Andrew V. Goldberg, Tomasz Radzik:
  Shortest Paths Algorithms: Theory and Experimental Evaluation. 516-525
  
• Andrew V. Goldberg, Alexander V. Karzanov:
  Path Problems in Skew-Symmetric Graphs. 526-535
  
• Ross M. McConnell, Jeremy Spinrad:
  Linear-Time Modular Decomposition and Efficient Transitive Orientation of Comparability Graphs. 536-545
  
• R. Ravi, Ravi Sundaram, Madhav V. Marathe, Daniel J. Rosenkrantz, S. S. Ravi:
  Spanning Trees Short or Small. 546-555
  
• Guy Kortsarz, David Peleg:
  Generating Low-Degree 2-Spanners. 556-563
  
• Micah Adler, Peter Gemmell, Mor Harchol-Balter, Richard M. Karp, Claire Kenyon:
  Selection in the Presence of Noise: The Design of Playoff Systems. 564-572
  
• Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, Angela Y. Wu:
  An Optimal Algorithm for Approximate Nearest Neighbor Searching. 573-582
  
• Mor Harchol-Balter, Paul E. Black:
  Queueing Analysis of Oblivious Packet-Routing Networks. 583-592
  
• Dana Randall, Alistair Sinclair:
  Testable Algorithms for Self-Avoiding Walks. 593-602
  
• Andrei Z. Broder, Alan M. Frieze, Stephen Suen, Eli Upfal:
  Optimal Construction of Edge-Disjoint Paths in Random Graphs. 603-612
  
• Rajeev Raman, Uzi Vishkin:
  Optimal Randomized Parallel Algorithms for Computing the Row Maxima of a Totally Monotone Matrix. 613-621
  
• Vijaya Ramachandran, Honghua Yang:
  An Efficient Parallel Algorithm for the General Planar Monotone Circuit Value Problem. 622-631
  
• Tomás Feder, Nimrod Megiddo, Serge A. Plotkin:
  A Sublinear Parallel Algorithm for Stable Matching. 632-637
  
• Phillip B. Gibbons, Yossi Matias, Vijaya Ramachandran:
  The QRQW PRAM: Accounting for Contention in Parallel Algorithms. 638-648
  
• Victor Y. Pan, Isdor Sobze, Antoine Atinkpahoun:
  Optimum Parallel Computations with Banded Matrices. 649-658
  
• Alok Aggarwal, C. Greg Plaxton:
  Optimal Parallel Sorting in Multi-Level Storage. 659-668
  
• Michael Kaufmann, Jop F. Sibeyn, Torsten Suel:
  Derandomizing Algorithms for Routing and Sorting on Meshes. 669-679
  
• S. Muthukrishnan:
  On Optimal Strategies for Searching in Presence of Errors. 680-689
  
• Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky:
  Matching Nuts and Bolts. 690-696
  
• Ming Gu, Martin Farach, Richard Beigel:
  An Efficient Algorithm for Dynamic Text Indexing. 697-704
  
• Amihood Amir, Gary Benson, Martin Farach:
  Let Sleeping Files Lie: Pattern Matching in Z-compressed Files. 705-714
  
• Juha Kärkkäinen, Esko Ukkonen:
  Two and Higher Dimensional Pattern Matching in Optimal Expected Time. 715-723
  
• Michael Luby, Joseph Naor, Ariel Orda:
  Tight Bounds for Dynamic Storage Allocation. 724-732
  

Last update Tue Feb 14 04:11:29 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page