10. SODA 1999:
Baltimore, Maryland, USA
Robert Endre Tarjan, Tandy Warnow (Eds.):
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 17-19 January 1999, Baltimore, Maryland.
ACM/SIAM 1999, ISBN 0-89871-434-6
- 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 log3 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 4na.
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 qth 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