Download Free Proceedings Of The Twelfth Annual Acm Siam Symposium On Discrete Algorithms Soda Washington Dc 07 09012001 Book in PDF and EPUB Free Download. You can read online Proceedings Of The Twelfth Annual Acm Siam Symposium On Discrete Algorithms Soda Washington Dc 07 09012001 and write the review.

Annotation Contains 130 papers, which were selected based on originality, technical contribution, and relevance. Although the papers were not formally refereed, every attempt was made to verify the main claims. It is expected that most will appear in more complete form in scientific journals. The proceedings also includes the paper presented by invited plenary speaker Ronald Graham, as well as a portion of the papers presented by invited plenary speakers Udi Manber and Christos Papadimitriou.
Symposium held in Miami, Florida, January 22–24, 2006.This symposium is jointly sponsored by the ACM Special Interest Group on Algorithms and Computation Theory and the SIAM Activity Group on Discrete Mathematics.Contents Preface; Acknowledgments; Session 1A: Confronting Hardness Using a Hybrid Approach, Virginia Vassilevska, Ryan Williams, and Shan Leung Maverick Woo; A New Approach to Proving Upper Bounds for MAX-2-SAT, Arist Kojevnikov and Alexander S. Kulikov, Measure and Conquer: A Simple O(20.288n) Independent Set Algorithm, Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch; A Polynomial Algorithm to Find an Independent Set of Maximum Weight in a Fork-Free Graph, Vadim V. Lozin and Martin Milanic; The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total-Monotonicity, Wolfgang W. Bein, Mordecai J. Golin, Larry L. Larmore, and Yan Zhang; Session 1B: Local Versus Global Properties of Metric Spaces, Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, and Santosh Vempala; Directed Metrics and Directed Graph Partitioning Problems, Moses Charikar, Konstantin Makarychev, and Yury Makarychev; Improved Embeddings of Graph Metrics into Random Trees, Kedar Dhamdhere, Anupam Gupta, and Harald Räcke; Small Hop-diameter Sparse Spanners for Doubling Metrics, T-H. Hubert Chan and Anupam Gupta; Metric Cotype, Manor Mendel and Assaf Naor; Session 1C: On Nash Equilibria for a Network Creation Game, Susanne Albers, Stefan Eilts, Eyal Even-Dar, Yishay Mansour, and Liam Roditty; Approximating Unique Games, Anupam Gupta and Kunal Talwar; Computing Sequential Equilibria for Two-Player Games, Peter Bro Miltersen and Troels Bjerre Sørensen; A Deterministic Subexponential Algorithm for Solving Parity Games, Marcin Jurdzinski, Mike Paterson, and Uri Zwick; Finding Nucleolus of Flow Game, Xiaotie Deng, Qizhi Fang, and Xiaoxun Sun, Session 2: Invited Plenary Abstract: Predicting the “Unpredictable”, Rakesh V. Vohra, Northwestern University; Session 3A: A Near-Tight Approximation Lower Bound and Algorithm for the Kidnapped Robot Problem, Sven Koenig, Apurva Mudgal, and Craig Tovey; An Asymptotic Approximation Algorithm for 3D-Strip Packing, Klaus Jansen and Roberto Solis-Oba; Facility Location with Hierarchical Facility Costs, Zoya Svitkina and Éva Tardos; Combination Can Be Hard: Approximability of the Unique Coverage Problem, Erik D. Demaine, Uriel Feige, Mohammad Taghi Hajiaghayi, and Mohammad R. Salavatipour; Computing Steiner Minimum Trees in Hamming Metric, Ernst Althaus and Rouven Naujoks; Session 3B: Robust Shape Fitting via Peeling and Grating Coresets, Pankaj K. Agarwal, Sariel Har-Peled, and Hai Yu; Tightening Non-Simple Paths and Cycles on Surfaces, Éric Colin de Verdière and Jeff Erickson; Anisotropic Surface Meshing, Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, and Rephael Wenger; Simultaneous Diagonal Flips in Plane Triangulations, Prosenjit Bose, Jurek Czyzowicz, Zhicheng Gao, Pat Morin, and David R. Wood; Morphing Orthogonal Planar Graph Drawings, Anna Lubiw, Mark Petrick, and Michael Spriggs; Session 3C: Overhang, Mike Paterson and Uri Zwick; On the Capacity of Information Networks, Micah Adler, Nicholas J. A. Harvey, Kamal Jain, Robert Kleinberg, and April Rasala Lehman; Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding, Micah Adler, Erik D. Demaine, Nicholas J. A. Harvey, and Mihai Patrascu; Self-Improving Algorithms, Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu; Cake Cutting Really is Not a Piece of Cake, Jeff Edmonds and Kirk Pruhs; Session 4A: Testing Triangle-Freeness in General Graphs, Noga Alon, Tali Kaufman, Michael Krivelevich, and Dana Ron; Constraint Solving via Fractional Edge Covers, Martin Grohe and Dániel Marx; Testing Graph Isomorphism, Eldar Fischer and Arie Matsliah; Efficient Construction of Unit Circular-Arc Models, Min Chih Lin and Jayme L. Szwarcfiter, On The Chromatic Number of Some Geometric Hypergraphs, Shakhar Smorodinsky; Session 4B: A Robust Maximum Completion Time Measure for Scheduling, Moses Charikar and Samir Khuller; Extra Unit-Speed Machines are Almost as Powerful as Speedy Machines for Competitive Flow Time Scheduling, Ho-Leung Chan, Tak-Wah Lam, and Kin-Shing Liu; Improved Approximation Algorithms for Broadcast Scheduling, Nikhil Bansal, Don Coppersmith, and Maxim Sviridenko; Distributed Selfish Load Balancing, Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul Goldberg, Zengjian Hu, and Russell Martin; Scheduling Unit Tasks to Minimize the Number of Idle Periods: A Polynomial Time Algorithm for Offline Dynamic Power Management, Philippe Baptiste; Session 4C: Rank/Select Operations on Large Alphabets: A Tool for Text Indexing, Alexander Golynski, J. Ian Munro, and S. Srinivasa Rao; O(log log n)-Competitive Dynamic Binary Search Trees, Chengwen Chris Wang, Jonathan Derryberry, and Daniel Dominic Sleator; The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree Distributed Data Structure, Michael T. Goodrich, Michael J. Nelson, and Jonathan Z. Sun; Design of Data Structures for Mergeable Trees, Loukas Georgiadis, Robert E. Tarjan, and Renato F. Werneck; Implicit Dictionaries with O(1) Modifications per Update and Fast Search, Gianni Franceschini and J. Ian Munro; Session 5A: Sampling Binary Contingency Tables with a Greedy Start, Ivona Bezáková, Nayantara Bhatnagar, and Eric Vigoda; Asymmetric Balanced Allocation with Simple Hash Functions, Philipp Woelfel; Balanced Allocation on Graphs, Krishnaram Kenthapadi and Rina Panigrahy; Superiority and Complexity of the Spaced Seeds, Ming Li, Bin Ma, and Louxin Zhang; Solving Random Satisfiable 3CNF Formulas in Expected Polynomial Time, Michael Krivelevich and Dan Vilenchik; Session 5B: Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem, Jie Gao, Michael Langberg, and Leonard J. Schulman; Finding Large Sticks and Potatoes in Polygons, Olaf Hall-Holt, Matthew J. Katz, Piyush Kumar, Joseph S. B. Mitchell, and Arik Sityon; Randomized Incremental Construction of Three-Dimensional Convex Hulls and Planar Voronoi Diagrams, and Approximate Range Counting, Haim Kaplan and Micha Sharir; Vertical Ray Shooting and Computing Depth Orders for Fat Objects, Mark de Berg and Chris Gray; On the Number of Plane Graphs, Oswin Aichholzer, Thomas Hackl, Birgit Vogtenhuber, Clemens Huemer, Ferran Hurtado, and Hannes Krasser; Session 5C: All-Pairs Shortest Paths for Unweighted Undirected Graphs in o(mn) Time, Timothy M. Chan; An O(n log n) Algorithm for Maximum st-Flow in a Directed Planar Graph, Glencora Borradaile and Philip Klein; A Simple GAP-Canceling Algorithm for the Generalized Maximum Flow Problem, Mateo Restrepo and David P. Williamson; Four Point Conditions and Exponential Neighborhoods for Symmetric TSP, Vladimir Deineko, Bettina Klinz, and Gerhard J. Woeginger; Upper Degree-Constrained Partial Orientations, Harold N. Gabow; Session 7A: On the Tandem Duplication-Random Loss Model of Genome Rearrangement, Kamalika Chaudhuri, Kevin Chen, Radu Mihaescu, and Satish Rao; Reducing Tile Complexity for Self-Assembly Through Temperature Programming, Ming-Yang Kao and Robert Schweller; Cache-Oblivious String Dictionaries, Gerth Stølting Brodal and Rolf Fagerberg; Cache-Oblivious Dynamic Programming, Rezaul Alam Chowdhury and Vijaya Ramachandran; A Computational Study of External-Memory BFS Algorithms, Deepak Ajwani, Roman Dementiev, and Ulrich Meyer; Session 7B: Tight Approximation Algorithms for Maximum General Assignment Problems, Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, and Maxim Sviridenko; Approximating the k-Multicut Problem, Daniel Golovin, Viswanath Nagarajan, and Mohit Singh; The Prize-Collecting Generalized Steiner Tree Problem Via A New Approach Of Primal-Dual Schema, Mohammad Taghi Hajiaghayi and Kamal Jain; 8/7-Approximation Algorithm for (1,2)-TSP, Piotr Berman and Marek Karpinski; Improved Lower and Upper Bounds for Universal TSP in Planar Metrics, Mohammad T. Hajiaghayi, Robert Kleinberg, and Tom Leighton; Session 7C: Leontief Economies Encode NonZero Sum Two-Player Games, B. Codenotti, A. Saberi, K. Varadarajan, and Y. Ye; Bottleneck Links, Variable Demand, and the Tragedy of the Commons, Richard Cole, Yevgeniy Dodis, and Tim Roughgarden; The Complexity of Quantitative Concurrent Parity Games, Krishnendu Chatterjee, Luca de Alfaro, and Thomas A. Henzinger; Equilibria for Economies with Production: Constant-Returns Technologies and Production Planning Constraints, Kamal Jain and Kasturi Varadarajan; Session 8A: Approximation Algorithms for Wavelet Transform Coding of Data Streams, Sudipto Guha and Boulos Harb; Simpler Algorithm for Estimating Frequency Moments of Data Streams, Lakshimath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, and Chandan Saha; Trading Off Space for Passes in Graph Streaming Problems, Camil Demetrescu, Irene Finocchi, and Andrea Ribichini; Maintaining Significant Stream Statistics over Sliding Windows, L.K. Lee and H.F. Ting; Streaming and Sublinear Approximation of Entropy and Information Distances, Sudipto Guha, Andrew McGregor, and Suresh Venkatasubramanian; Session 8B: FPTAS for Mixed-Integer Polynomial Optimization with a Fixed Number of Variables, J. A. De Loera, R. Hemmecke, M. Köppe, and R. Weismantel; Linear Programming and Unique Sink Orientations, Bernd Gärtner and Ingo Schurr; Generating All Vertices of a Polyhedron is Hard, Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, and Vladimir Gurvich; A Semidefinite Programming Approach to Tensegrity Theory and Realizability of Graphs, Anthony Man-Cho So and Yinyu Ye; Ordering by Weighted Number of Wins Gives a Good Ranking for Weighted Tournaments, Don Coppersmith, Lisa Fleischer, and Atri Rudra; Session 8C: Weighted Isotonic Regression under L1 Norm, Stanislav Angelov, Boulos Harb, Sampath Kannan, and Li-San Wang; Oblivious String Embeddings and Edit Distance Approximations, Tugkan Batu, Funda Ergun, and Cenk Sahinalp0898716012\\This comprehensive book not only introduces the C and C++ programming languages but also shows how to use them in the numerical solution of partial differential equations (PDEs). It leads the reader through the entire solution process, from the original PDE, through the discretization stage, to the numerical solution of the resulting algebraic system. The well-debugged and tested code segments implement the numerical methods efficiently and transparently. Basic and advanced numerical methods are introduced and implemented easily and efficiently in a unified object-oriented approach.
This text covers the proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, which was held in Atlanta, Georgia, in January 1996.
Discrete mathematics and graph theory, including combinatorics, combinatorial optimization and networks Preface Acknowledgments Region-Fault Tolerant Geometric Spanners, M. A. Abam, M. de Berg, M. Farshi, and J. Gudmundsson A PTAS for TSP with Neighborhoods among Fat Regions in the Plane, Joseph S. B. Mitchell Optimal Dynamic Vertical Ray Shooting in Rectilinear Planar Subdivisions, Yoav Giyora and Haim Kaplan Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition, David Eppstein A Near Linear Time Constant Factor Approximation for Euclidean Bichromatic Matching (Cost), Piotr Indyk Compacting Cuts: A New Linear Formulation for Minimum Cut, Robert D. Carr, Goran Konjevod, Greg Little, Venkatesh Natarajan, and Ojas Parekh Linear Programming Relaxations of Maxcut, Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems, Moses Charikar, Konstantin Makarychev, and Yury Makarychev Improved Bounds for the Symmetric Rendezvous Value on the Line, Qiaoming Han, Donglei Du, Juan Vera, and Luis F. Zuluaga Efficient Solutions to Relaxations of Combinatorial Problems with Submodular Penalties via the Lovász Extension and Non-smooth Convex Optimization, Fabián A. Chudak and Kiyohito Nagano Multiple Source Shortest Paths in a Genus g Graph, Sergio Cabello and Erin W. Chambers Obnoxious Centers in Graphs, Sergio Cabello and Günter Rote Maximum Matching in Graphs with an Excluded Minor, Raphael Yuster and Uri Zwick Faster Dynamic Matchings and Vertex Connectivity, Piotr Sankowski Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related Problems, Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi Analytic Combinatorics—A Calculus of Discrete Structures, Philippe Flajolet Equilibria in Online Games,Roee Engelberg and Joseph (Seffi) Naor The Approximation Complexity of Win-Lose Games, Xi Chen, Shang-Hua Teng, and Paul Valiant Convergence to Approximate Nash Equilibria in Congestion Games, Steve Chien and Alistair Sinclair Efficient Contention Resolution Protocols for Selfish Agents, Amos Fiat, Yishay Mansour, and Uri Nadav Strong Price of Anarchy,Nir Andelman, Michal Feldman, and Yishay Mansour Better Online Buffer Management , Fei Li, Jay Sethuraman, and Clifford Stein Considering Suppressed Packets Improves Buffer Management in QoS Switches, Matthias Englert and Matthias Westermann Instability of FIFO in the Permanent Sessions Model at Arbitrarily Small Network Loads, Matthew Andrews On the Separation and Equivalence of Paging Strategies,Spyros Angelopoulos, Reza Dorrigiv, and Alejandro López-Ortiz Pull-Based Data Broadcast with Dependencies: Be Fair to Users, Not to Items,Julien Robert and Nicolas Schabanel Improved Bounds for the Online Steiner Tree Problem in Graphs of Bounded Edge-Asymmetry, Spyros Angelopoulos Minimizing Movement, Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveisgharan, and Morteza Zadimoghaddam Optimization Problems in Multiple-Interval Graphs, Ayelet Butman, Danny Hermelin, Moshe Lewenstein, and Dror Rawitz Approximation Algorithms via Contraction Decomposition, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Bojan Mohar A 1.875–Approximation Algorithm for the Stable Marriage Problem, Kazuo Iwama, Shuichi Miyazaki, and Naoya Yamauchi Improved Algorithms for Path, Matching, and Packing Problems, Jianer Chen, Songjian Lu, Sing-Hoi Sze, and Fenghui Zhang Model-Driven Optimization Using Adaptive Probes, Sudipto Guha and Kamesh Munagala Estimating the Sortedness of a Data Stream, Parikshit Gopalan, T.S. Jayram, Robert Krauthgamer, and Ravi Kumar A Near-Optimal Algorithm for Computing the Entropy of a Stream, Amit Chakrabarti, Graham Cormode, and Andrew McGregor The Communication and Streaming Complexity of Computing the Longest Common and Increasing Subsequences, Xiaoming Sun and David P. Woodruff Efficient Aggregation Algorithms for Probabilistic Data, T.S. Jayram, Satyen Kale, and Erik Vee An Unbiased Pointing Operator for Unlabeled Structures, with Applications to Counting and Sampling, Manuel Bodirsky, Eric Fusy, Mihyun Kang, and Stefan Vigerske Approximating Entropy from Sublinear Samples, Mickey Brautbar and Alex Samorodnitsky Torpid Mixing of Local Markov Chains on 3-Colorings of the Discrete Torus, David Galvin and Dana Randall Probabilistic Analysis of Linear Programming Decoding, Constantinos Daskalakis, Alexandros G. Dimakis, Richard M. Karp, and Martin J. Wainwright Scrambling Adversarial Errors Using Few Random Bits, Optimal Information Reconciliation, and Better Private Codes, Adam Smith Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems, Anke van Zuylen, Rajneesh Hegde, Kamal Jain, and David P. Williamson Aggregation of Partial Rankings, p-Ratings and Top-m Lists, Nir Ailon Algorithms and Incentives for Robust Ranking, Rajat Bhattacharjee and Ashish Goel Matroids, Secretary Problems, and Online Mechanisms, Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg An Algebraic Algorithm for Weighted Linear Matroid Intersection, Nicholas J. A. Harvey An Elementary Construction of Constant-Degree Expanders, Noga Alon, Oded Schwartz, and Asaf Shapira The k-Orientability Thresholds for G_{n,p}, Daniel Fernholz and Vijaya Ramachandran The Random Graph Threshold for k-Orientiability and a Fast Algorithm for Optimal Multiple-Choice Allocation, Julie Anne Cain, Peter Sanders, and Nick Wormald On Extremal Subgraphs of Random Graphs, Graham Brightwell, Konstantinos Panagiotou, and Angelika Steger Online Vertex Colorings of Random Graphs without Monochromatic Subgraphs, Martin Marciniszyn and Reto Spöhel On Testable Properties in Bounded Degree Graphs, Artur Czumaj and Christian Sohler Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion, Ittai Abraham, Yair Bartal, and Ofer Neiman Approximation Algorithms for Embedding General Metrics into Trees, Mihai Badoiu, Piotr Indyk, and Anastasios Sidiropoulos Embedding into $l^2_{infty}$ Is Easy, Embedding into $l^3_{infty}$ Is NP-Complete, Jeff Edmonds Efficient Subspace Approximation Algorithms, Nariankadu D. Shyamalkumar and Kasturi Varadarajan A Divide and Conquer Algorithm for d-Dimensional Arrangement, Moses Charikar, Konstantin Makarychev, and Yury Makarychev Resilient Search Trees, Irene Finocchi, Fabrizio Grandoni, and Giuseppe F. Italiano Randomization Does Not Help Searching Predecessors, Mihai Patrascu and Mikkel Thorup Dynamic Weighted Ancestors, Tsvi Kopelowitz and Moshe Lewenstein Ultra-succinct Representation of Ordered Trees, Jesper Jansson, Kunihiko Sadakane, and Wing-Kin Sung Tree Exploration with Logarithmic Memory, Leszek Gasieniec, Andrzej Pelc, Tomasz Radzik, and Xiaohui Zhang Testing for a Theta, Maria Chudnovsky and Paul Seymour Deterministic Rendezvous, Treasure Hunts and Strongly Universal Exploration Sequences, Amnon Ta-Shma and Uri Zwick Planar Graphs Are in 1-STRING, J. Chalopin, D. Gonçalves, and P. Ochem On the Bandwidth Conjecture for 3-Colourable Graphs, Julia Böttcher, Mathias Schacht, and Anusch Taraz Sandpile Transience on the Grid is Polynomially Bounded, László Babai and Igor Gorodezky Digraph Measures: Kelly Decompositions, Games, and Orderings, Paul Hunter and Stephan Kreutzer Approximating the Spanning Star Forest Problem and Its Applications to Genomic Sequence Alignment, C. Thach Nguyen, Jian Shen, Minmei Hou, Li Sheng, Webb Miller, and Louxin Zhang Fast Elimination of Redundant Linear Equations and Reconstruction of Recombination-Free Mendelian Inheritance on a Pedigree, Jing Xiao, Lan Liu, Lirong Xia, and Tao Jiang Whole Genome Duplications, Multi-break Rearrangements, and Genome Halving Problem, Max A. Alekseyev and Pavel A. Pevzner Succinct Indexes for Strings, Binary Relations and Multi-labeled Trees, Jérémy Barbay, Meng He, J. Ian Munro, and S. Srinivasa Rao A Simple Storage Scheme for Strings Achieving Entropy Bounds, Paolo Ferragina and Rossano Venturini A Network Formation Game for Bipartite Exchange Economies, Eyal Even-Dar, Michael Kerans, and Siddharth Suri Cheap Labor Can Be Expensive, Ning Chen and Anna R. Karlin Buying Cheap Is Expensive: Hardness of Non-parametric Multi-product Pricing, Patrick Briest and Piotr Krysta Dynamic Pricing for Impatient Bidders, Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, and Maxim Sviridenko Designing and Learning Optimal Finite Support Auctions, Edith Elkind On Bregman Voronoi Diagrams, Frank Nielsen, Jean-Daniel Boissonnat, and Richard Nock Zone Diagrams: Existence, Uniqueness, and Algorithmic Challenge, Tetsuo Asano, Jirí Matoušek, and Takeshi Tokuyama Approximate Shortest Paths in Anisotropic Regions, Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang On Bounded Leg Shortest Paths Problems, Liam Roditty and Michael Segal Counting Colors in Boxes, Haim Kaplan, Natan Rubin, Micha Sharir, and Elad Verbin Energy Efficient Online Deadline Scheduling, Ho-Leung Chan, Wun-Tat Chan, Tak-Wah Lam, Lap-Kei Lee, Kin-Sum Mak, and Prudence W. H. Wong Speed Scaling for Weighted Flow Time, Nikhil Bansal, Kirk Pruhs, and Cliff Stein Path-Independent Load Balancing with Unreliable Machines, James Aspnes, Yang Richard Yang, and Yitong Yin Layered Multicast Scheduling for the L_infinity Objective, Qingbo Cai and Vincenzo Liberatore Lower Bounds on Average-Case Delay for Video-on-Demand Broadcast Protocols, Wei-Lung Dustin Tseng and David Kirkpatrick Maximum s-t-Flow with k Crossings in $O(k^3 n log n)$ Time, Jan M. Hochstein and Karsten Weihe Matrix Scaling by Network Flow, Günter Rote and Martin Zachariasen Single Source Multiroute Flows and Cuts on Uniform Capacity Networks, Henning Bruhn, Jakub Cerný, Alexander Hall, and Petr Kolman Island Hopping and Path Colouring with Applications to WDM Network Design, Andrew McGregor and Bruce Shepherd Maximum Independent Sets in Graphs of Low Degree,
Annotation This volume contains 93 traditional papers and 74 short form abstracts presented at the January 1999 symposium, which encouraged increased participation from the discrete mathematics community this year. Topics of the longer papers include page replacement for general caching problems, queries with segments in Voronoi diagrams, clustering in large graphs and matrices, the complexity of gene placement, and indexing schemes for random points. Some of the short paper topics are locked and unlocked polygonal chains in 3D, compact roundtrip routing for digraphs, and sampling spin configurations on an Ising system. No subject index. Annotation copyrighted by Book News, Inc., Portland, OR.