10. SODA 1999: Baltimore, Maryland, USA

• Ran Adler, Yossi Azar:
  Beating the Logarithmic Lower Bound: Randomized Preemptive Disjoint Paths and Call Control Algorithms. 1-10
  
• Pankaj K. Agarwal, Lars Arge, Gerth Stølting Brodal, Jeffrey Scott Vitter:
  I/O-Efficient Dynamic Point Location in Monotone Planar Subdivisions. 11-20
  
• Pankaj K. Agarwal, Micha Sharir:
  Motion Planning of a Ball Amid Segments in Three Dimensions. 21-30
  
• Susanne Albers, Sanjeev Arora, Sanjeev Khanna:
  Page Replacement for General Caching Problems. 31-40
  
• Gunnar Andersson, Lars Engebretsen, Johan Håstad:
  A New Way to Use Semidefinite Programming with Applications to Linear Equations mod p. 41-50
  
• Javed A. Aslam, Katya Pelekhov, Daniela Rus:
  A Practical Clustering Algorithm for Static and Dynamic Information Organization. 51-60
  
• Yonatan Aumann, Avivit Kapah-Levy:
  Cooperative Sharing and Asynchronous Consensus Using Single-Reader Single-Writer Registers. 61-70
  
• Reuven Bar-Yehuda:
  Using Homogenous Weights for Approximating the Partial Cover Problem. 71-75
  
• Gill Barequet:
  A Lower Bound for Hellbronn's Triangle Problem in d Dimensions. 76-81
  
• Gill Barequet, Sariel Har-Peled:
  Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions. 82-91
  
• Yair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang:
  Fast, Fair, and Frugal Bandwidth Allocation in ATM Networks. 92-101
  
• Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang:
  Kinetic Collision Detection Between Two Simple Polygons. 102-111
  
• Petra Berenbrink, Christian Scheideler:
  Locally Efficient On-Line Strategies for Routing Packets Along Fixed Paths. 112-121
  
• Sergei Bespamyatnikh, Jack Snoeyink:
  Queries with Segments in Voronoi Diagrams. 122-129
  
• Therese C. Biedl, Prosenjit Bose, Erik D. Demaine, Anna Lubiw:
  Efficient Algorithms for Petersen's Matching Theorem. 130-139
  
• John M. Boyer, Wendy J. Myrvold:
  Stop Minding Your p's and q's: A Simplified O(n) Planar Embedding Algorithm. 140-146
  
• David Bryant, Mike A. Steel:
  Fast Algorithms for Constructing Optimal Trees from Quartets. 147-155
  
• Michael R. Capalbo:
  A Small Universal Graph for Bounded-degree Planar Graphs. 156-160
  
• Timothy M. Chan:
  A Near-Linear Area Bound for Drawing Binary Trees. 161-168
  
• Barun Chandra, Magnús M. Halldórsson:
  Greedy Local Improvement and Weighted Set Packing Approximation. 169-176
  
• Moses Charikar, Jon M. Kleinberg, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai, Andrew Tomkins:
  Minimizing Wirelength in Zero and Bounded Skew Clock Trees. 177-184
  
• Chandra Chekuri, Sanjeev Khanna:
  On Multi-Dimensional Packing Problems. 185-194
  
• Zhi-Zhong Chen, Xin He, Ming-Yang Kao:
  Nonplanar Topological Inference and Political-Map Graphs. 195-204
  
• Siu-Wing Cheng, Tamal K. Dey:
  Approximate Minimum Weight Steiner Triangulation in Three Dimensions. 205-214
  
• Yi-Jen Chiang, Joseph S. B. Mitchell:
  Two-Point Euclidean Shortest Path Queries in the Plane. 215-224
  
• Ka Wong Chong, Yijie Han, Tak Wah Lam:
  On the Parallel Time Complexity of Undirected Connectivity and Minimum Spanning Trees. 225-234
  
• Richard Cole, Ramesh Hariharan:
  Dynamic LCA Queries on Trees. 235-244
  
• Richard Cole, Ramesh Hariharan, Piotr Indyk:
  Tree Pattern Matching and Subset Matching in Deterministic O(n log³ n)-time. 245-254
  
• Lenore Cowen:
  Compact Routing with Minimum Stretch. 255-260
  
• Miklós Csürös, Ming-Yang Kao:
  Recovering Evolutionary Trees Through Harmonic Greedy Triplets. 261-270
  
• Artur Czumaj, Przemyslawa Kanarek, Miroslaw Kutylowski, Krzysztof Lorys:
  Delayed Path Coupling and Generating Random Permutations via Distributed Stochastic Processes. 271-280
  
• Artur Czumaj, Andrzej Lingas:
  On Approximability of the Minimum-Cost k-Connected Spanning Subgraph Problem. 281-290
  
• Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh Vempala, V. Vinay:
  Clustering in Large Graphs and Matrices. 291-299
  
• Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov:
  Balanced Aspect Ratio Trees: Combining the Advantages of k-d Trees and Octrees. 300-309
  
• David Eppstein, David Hart:
  Shortest Paths in an Arrangement with k Line Orientations. 310-316
  
• Leah Epstein, John Noga, Steven S. Seiden, Jiri Sgall, Gerhard J. Woeginger:
  Randomized Online Scheduling on Two Uniform Machines. 317-326
  
• Jeff Erickson, Leonidas J. Guibas, Jorge Stolfi, Li Zhang:
  Separation-Sensitive Collision Detection for Convex Objects. 327-336
  
• Sándor P. Fekete:
  Simplicity and Hardness of the Maximum Traveling Salesman Problem Under Geometric Distances. 337-345
  
• Alan M. Frieze, Lei Zhao:
  Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs. 346-355
  
• Harold N. Gabow, Tibor Jordán:
  How to Make a Square Grid Framework with Cables Rigid. 356-365
  
• Michel X. Goemans, David P. Williamson:
  Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. 366-375
  
• Andrew V. Goldberg, Kostas Tsioutsiouliklis:
  Cut Tree Algorithms. 376-385
  
• Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson, Pavel A. Pevzner, Süleyman Cenk Sahinalp, Elizabeth Sweedyk:
  The Complexity of Gene Placement. 386-395
  
• Michael H. Goldwasser:
  Patience is a Virtue: The Effect of Slack on Competitiveness for Admission Control. 396-405
  
• Stephen Guattery, Gary L. Miller, Noel Walkington:
  Estimating Interpolation Error: A Combinatorial Approach. 406-413
  
• Torben Hagerup:
  Fast Deterministic Construction of Static Dictionaries. 414-418
  
• Yijie Han, Xiaojun Shen:
  Parallel Integer Sorting is More Efficient than Parallel Comparison Sorting on Exclusive Write PRAMs. 419-428
  
• Lenwood S. Heath, Nicholas A. Loehr:
  New Algorithms for Generating Conway Polynomials Over Finite Fields. 429-437
  
• Monika Rauch Henzinger, Stefano Leonardi:
  Scheduling Multicasts on Unit-Capacity Trees and Meshes. 438-447
  
• Stefan Hougardy, Hans Jürgen Prömel:
  A 1.598 Approximation Algorithm for the Steiner Problem in Graphs. 448-453
  
• Piotr Indyk:
  A Small Approximately min-wise Independent Family of Hash Functions. 454-456
  
• Piotr Indyk, Rajeev Motwani, Suresh Venkatasubramanian:
  Geometric Matching Under Noise: Combinatorial Bounds and Algorithms. 457-465
  
• Kazuo Iwama, Eiji Miyano:
  An O(N) Oblivious Routing Algorithm for 2-D Meshes of Constant Queue-Size. 466-475
  
• Satoru Iwata:
  Computing the Maximum Degree of Minors in Matrix Pencils via Combinatorial Relaxation. 476-483
  
• Kamal Jain, Ion I. Mandoiu, Vijay V. Vazirani, David P. Williamson:
  A Primal-Dual Schema Based Approximation Algorithm for the Element Connectivity Problem. 484-489
  
• Klaus Jansen, Lorant Porkolab:
  Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks. 490-498
  
• Bala Kalyanasundaram, Kirk Pruhs:
  Eliminating Migration in Multi-Processor Scheduling. 499-506
  
• Haim Kaplan, Mario Szegedy:
  On-line Complexity of Monotone Set Systems. 507-516
  
• Naoki Katoh, Hisao Tamaki, Takeshi Tokuyama:
  Parametric Polymatroid Optimization and Its Geometric Applications. 517-526
  
• Hiroshi Kawazoe, Tetsuo Shibuya, Takeshi Tokuyama:
  Optimal On-line Algorithms for an Electronic Commerce Money Distribution System. 527-536
  
• Paul E. Kearney, Ming Li, John Tsang, Tao Jiang:
  Recovering Branches on the Tree of Life: An Approximation Algorithm. 537-546
  
• Claire Kenyon, Nicolas Schabanel:
  The Data Broadcast Problem with Non-Uniform Transmission Rimes. 547-556
  
• Tracy Kimbrel:
  Interleaved Prefetching. 557-565
  
• Jon M. Kleinberg, Amit Kumar:
  Wavelength Conversion in Optical Networks. 566-575
  
• Anton J. Kleywegt, Vijay S. Nori, Martin W. P. Savelsbergh, Craig A. Tovey:
  Online Resource Minimization. 576-585
  
• Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman:
  Placement Algorithms for Hierarchical Cooperative Caching. 586-595
  
• Elias Koutsoupias, David Scot Taylor:
  Indexing Schemes for Random Points. 596-602
  
• Ravi Kumar, D. Sivakumar:
  Roundness Estimation via Random Sampling. 603-612
  
• Richard E. Ladner, James D. Fix, Anthony LaMarca:
  Cache Performance Analysis of Traversals and Random Accesses. 613-622
  
• Tak Wah Lam, Kar-Keung To:
  Trade-offs Between Speed and Processor in Hard-Deadline Scheduling. 623-632
  
• J. Kevin Lanctot, Ming Li, Bin Ma, Shaojiu Wang, Louxin Zhang:
  Distinguishing String Selection Problems. 633-642
  
• Frank Thomson Leighton, Satish Rao, Aravind Srinivasan:
  New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning. 643-652
  
• Vincenzo Liberatore:
  Empirical Investigation of the Markov Reference Model. 653-662
  
• Chi-Jen Lu:
  A Deterministic Approximation Algorithm for a Minmax Integer Programming Problem. 663-668
  
• Giovanni Manzini:
  An Analysis of the Burrows-Wheeler Transform. 669-677
  
• Waleed Meleis, Edward S. Davidson:
  Dual-Issue Scheduling with Spills for Binary Trees. 678-686
  
• Kamesh Munagala, Abhiram G. Ranade:
  I/O-Complexity of Graph Algorithms. 687-694
  
• Lata Narayanan, Jaroslav Opatrny, Dominique Sotteau:
  All-to-All Optical Routing in Optimal Chordal Rings of Degree Four. 695-703
  
• Jeffrey D. Oldham:
  Combinatorial Approximation Algorithms for Generalized Flow Problems. 704-714
  
• Victor Y. Pan, Yanqiang Yu:
  Certified Computation of the Sign of a Matrix Determinant. 715-724
  
• Marco Pellegrini:
  Rendering Equation Revisited: How to Avoid Explicit Visibility Computations. 725-733
  
• Balaji Raghavachari, Jeyakesavan Veerasamy:
  Approximation Algorithms for the Asymmetric Postman Problem. 734-741
  
• Sridhar Rajagopalan, Vijay V. Vazirani:
  On the Bidirected Cut Relaxation for the Metric Steiner Tree Problem. 742-751
  
• Joe Sawada, Frank Ruskey:
  An Efficient Algorithm for Generating Necklaces with Fixed Density. 752-758
  
• Petra Schuurman, Gerhard J. Woeginger:
  Preemptive Scheduling with Job-Dependent Setup Times. 759-767
  
• Jeffrey Shallit, David Swart:
  An Efficient Algorithm for Computing the ith letter of 4ⁿa. 768-775
  
• Alan Siegel:
  Median Bounds and Their Application. 776-785
  
• Adam Smith, Subhash Suri:
  Rectangular Tiling in Multi-dimensional Arrays. 786-794
  
• C. R. Subramanian:
  A Generalization of Janson Inequalities and its Application to Finding Shortest Paths. 795-804
  
• Kasturi R. Varadarajan, Pankaj K. Agarwal:
  Approximation Algorithms for Bipartite and Non-Bipartite Matching in the Plane. 805-814
  
• Kevin D. Wayne:
  A New Property and a Faster Algorithm for Baseball Elimination. 815-819
  
• Gerhard J. Woeginger:
  When Does a Dynamic Programming Formulation Guarantee the Existence of an FPTAS? 820-829
  
• Yunhong Zhou, Subhash Suri:
  Analysis of a Bounding Box Heuristic for Object Intersection. 830-839
  
• Richa Agarwala, Leslie G. Biesecker, Alejandro A. Schäffer:
  Inverse Inbreeding Coefficient Problems with an Application to Linkage Analysis of Recessive Diseases in Inbred Populations. 840-841
  
• Susanne Albers, Klaus Kursawe, Sven Schuierer:
  Exploring Unknown Environments with Obstacles. 842-843
  
• Andris Ambainis, Stephen A. Bloch, David L. Schweizer:
  Playing Twenty Questions with a Procrastinator. 844-845
  
• Javed A. Aslam, April Rasala, Clifford Stein, Neal E. Young:
  Improved Bicriteria Existence Theorems for Scheduling. 846-847
  
• Giuseppe Ateniese, Gene Tsudik:
  Group Signatures Á la carte. 848-849
  
• Ulrike Axen:
  Computing Morse Functions on Triangulated Manifolds. 850-851
  
• Ivan D. Baev, Waleed Meleis, Alexandre E. Eichenberger:
  Algorithms for Total Weighted Completion Time Scheduling. 852-853
  
• Brenda S. Baker:
  Parameterized diff. 854-855
  
• Richard Beigel:
  Finding Maximum Independent Sets in Sparse and General Graphs. 856-857
  
• Tanya Y. Berger-Wolf, Edward M. Reingold:
  Optimal Multichannel Communication Under Failure. 858-859
  
• Anne Berry:
  A Wide-Range Efficient Algorithm for Minimal Triangulation. 860-861
  
• Gill Barequet, Sariel Har-Peled:
  Polygon-containment and Translational min-Hausdorff-Distance between segment Sets are 3SUM-hard. 862-863
  
• Randeep Bhatia, Samir Khuller, Robert Pless, Yoram J. Sussmann:
  The Full Degree Spanning Tree Problem. 864-865
  
• Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark H. Overmars, Steve Robbins, Ileana Streinu, Godfried T. Toussaint, Sue Whitesides:
  Locked and Unlocked Polygonal Chains in 3D. 866-867
  
• Matt Blaze, Joan Feigenbaum, Moni Naor:
  A Formal Treatment of Remotely Keyed Encryption. 868-869
  
• Andrei Z. Broder, Michael Mitzenmacher, Laurent Moll:
  Unscrambling Address Lines. 870-871
  
• Kathie Cameron, Jack Edmonds:
  Some Graphic Uses of an Even Number of Odd Nodes. 872
  
• Chandra Chekuri, Rajeev Motwani:
  Minimizing Weighted Completion Time on a Single Machine. 873-874
  
• Fabián A. Chudak, David B. Shmoys:
  Improved Approximation Algorithms for a Capacitated Facility Location Problem. 875-876
  
• Edward G. Coffman Jr., Alexander L. Stolyar:
  Fluid Limits, Bin Packing, and Stochastic Analysis of Algorithms. 877-878
  
• Edith Cohen, Haim Kaplan:
  LP-based Analysis of Greedy-dual-size. 879-880
  
• Johanne Cohen, Pierre Fraigniaud, Margarida Mitjana:
  Scheduling Calls for Multicasting in Tree-Networks. 881-882
  
• Derek G. Corneil, Stephan Olariu, Lorna Stewart:
  LBFS Orderings and Cocomparability Graphs. 883-884
  
• Lenore Cowen, Christopher G. Wagner:
  Compact Roundtrip Routing for Digraphs. 885-886
  
• Celina M. Herrera de Figueiredo, Luerbio Faria, Candido Ferreira Xavier de Mendonça Neto:
  Optimal Node-Degree Bounds for the Complexity of Nonplanarity Parameters. 887-888
  
• Frank K. H. A. Dehne, Wolfgang Dittrich, David A. Hutchinson, Anil Maheshwari:
  Parallel Virtual Memory. 889-890
  
• Erik D. Demaine, Martin L. Demaine, Anna Lubiw:
  Folding and One Straight Cut Suffice. 891-892
  
• Tamal K. Dey, Piyush Kumar:
  A Simple Provable Algorithm for Curve Reconstruction. 893-894
  
• Giovanni Di Crescenzo, Yair Frankel:
  Existence of Multiplicative Secret Sharing Schemes with Polynomial Share Expansion. 895-896
  
• Yevgeniy Dodis, Venkatesan Guruswami, Sanjeev Khanna:
  The 2-Catalog Segmentation Problem. 897-898
  
• David Eppstein:
  Incremental and Decremental Maintenance of Planar Width. 899-900
  
• Ulrich Finkler, Kurt Mehlhorn:
  Checking Priority Queues. 901-902
  
• Martin Fürer:
  Randomized Splay Trees. 903-904
  
• Leszek Gasieniec, Jesper Jansson, Andrzej Lingas:
  Efficient Approximation Algorithms for the Hamming Center Problem. 905-906
  
• Jordan Gergov:
  Algorithms for Compile-Time Memory Optimization. 907-908
  
• Phillip B. Gibbons, Yossi Matias:
  Synopsis Data Structures for Massive Data Sets. 909-910
  
• Ashish Goel:
  Stability of Networks and Protocols in the Adversarial Queueing Model for Packet Routing. 911-912
  
• Andrew V. Goldberg, Bernard M. E. Moret:
  Combinatorial Algorithms Test Sets [CATS]: The ACM/EATCS Platform for Experimental Research. 913-914
  
• Vladimir Grebinski, Gregory Kucherov:
  Reconstructing Set Partitions. 915-916
  
• Magnús M. Halldórsson:
  Online Coloring Known Graphs. 917-918
  
• Gregory L. Heileman, Chaouki T. Abdallah, Bernard M. E. Moret, Bradley J. Smith:
  Dynamical System Representation of Open Address Hash Functions. 919-920
  
• Mark Huber:
  Efficient Exact Sampling from the Ising Model Using Swendsen-Wang. 921-922
  
• Louis Ibarra:
  Fully Dynamic Algorithms for Chordal Graphs. 923-924
  
• Gabriel Istrate:
  The Phase Transition in Random Horn Satisfiability and Its Algorithmic Implications. 925-926
  
• David S. Johnson, Mario Szegedy:
  What are the Least Tractable Instances of max Tndependent Set? 927-928
  
• Anna M. Johnston:
  A Generalized q^th Root Algorithm. 929-930
  
• Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, Angela Y. Wu:
  Computing Nearest Neighbors for Moving Points and Applications to Clustering. 931-932
  
• Ming-Yang Kao, Stephen R. Tate:
  Designing Proxies for Stock Market Indices is Computationally Hard. 933-934
  
• Haim Kaplan, Martin Strauss, Mario Szegedy:
  Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data. 935-936
  
• Samir Khuller, Balaji Raghavachari, An Zhu:
  A Uniform Framework for Approximating Weighted Connectivity Problems. 937-938
  
• Gang Li, Frank Ruskey:
  The Advantages of Forward Thinking in Generating Rooted and Free Trees. 939-940
  
• Luis-Miguel Lopez, Philippe Narbel:
  An Algorithm to Symbolically Describe Flows on Surfaces. 941-942
  
• Yossi Matias, Süleyman Cenk Sahinalp:
  On the Optimality of Parsing in Dynamic Dictionary Based Data Compression. 943-944
  
• Giancarlo Mauri, Giulio Pavesi, Antonio Piccolboni:
  Approximation Algorithms for Protein Folding Prediction. 945-946
  
• Jacques Mazoyer, Codrin M. Nichitiu, Eric Rémila:
  Compass Permits Leader Election. 947-948
  
• Matthias Müller-Hannemann:
  Combinatorics Helps for Hexahedral Mesh Generation in CAD. 949-950
  
• Zeev Nutov:
  Approximating Multiroot 3-Outconnected Subgraphs. 951-952
  
• Igor Pak:
  Using Stopping Times to Bound Mixing Times. 953-954
  
• Allon G. Percus, David C. Torney:
  Greedy Algorithms for Optimized DNA Sequencing. 955-956
  
• Vijaya Ramachandran, Brian Grayson, Michael Dahlin:
  Emulations Between QSM, BSP, and LogP: A Framework for General-Purpose Parallel Algorithm Design. 957-958
  
• Dana Randall, David Wilson:
  Sampling Spin Configurations of an Ising System. 959-960
  
• Mark Scharbrodt, Angelika Steger, Horst Weisser:
  Approximability of Scheduling with Fixed Jobs. 961-962
  
• Jay Sethuraman, Mark S. Squillante:
  Optimal Scheduling of Multiclass Parallel Machines. 963-964
  
• Ingo Schiermeyer, Bert Randerath:
  Colouring Graphs with Prescribed Induced Cycle Lengths. 965-966
  
• Andreas S. Schulz, Robert Weismantel:
  An Oracle-Polynomial Time Augmentation Algorithm for Integer Programming. 967-968
  
• Subhash Suri, George Varghese:
  Packet Filtering in High Speed Networks. 969-970
  
• Mario Szegedy:
  A Slique Size Bounding Technique with Application to Non-Linear Codes. 971-972
  
• Eric Torng, Patchrawat Uthaisombut:
  Lower Bounds for SRPT-Subsequence Algorithms for Nonpreemptive Scheduling. 973-974
  
• Santosh Vempala, Mihalis Yannakakis:
  A Convex Relaxation for the Asymmetric TSP. 975-976
  
• Narayan Vikas:
  Computational Complexity of Compaction to Cycles. 977-978
  
• David M. Warme, Pawel Winter, Martin Zachariasen:
  Exact Solutions to Large-scale Plane Steiner Tree Problems. 979-980
  
• Kevin D. Wayne, Lisa Fleischer:
  Faster Approximation Algorithms for Generalized Flow. 981-982
  
• Rebecca N. Wright, Sara Spalding:
  Experimental Performance of Shared RSA Modulus Generation. 983-984
  
• Xinyu Xiang, Martin Held, Joseph S. B. Mitchell:
  Fast and Effective Stripification of Polygonal Surface Models. 985-986
  

Last update Tue May 21 18:04:29 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page