close
1.

図書
図書
1. Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms ; ACM Special Interest Group on Algorithms and Computation Theory ; SIAM Activity Group on Discrete Mathematics
出版情報: New York : Association for Computing Machinery , Philadelphia : Society for Industrial and Applied Mathematics, c2000  xvi, 965 p. ; 28 cm
所蔵情報: loading…
目次情報: 続きを見る
Preface
Acknowledgments
[varepsilon]-Approximate Linear Progams: New Bounds and Computation / Daniel BienstockSession 1A：
Orthogonal Graph Drawing with Constraints / Markus Eiglsperger ; Ulrich Fo[sz ligature]meier ; Michael Kaufmann
Fast Practical Solution of Sorting by Reversals / Alberto Caprara ; Giuseppe Lancia ; See Kiong Ng
Commuting with Delay Prone Buses / Mayur Datar ; Abhiram Ranade
Coloring Non-Uniform Hypergraphs: A New Algorithmic Approach to the General Lovasz Local Lemma / Artur Czumaj ; Christian ScheidelerSession 1B：
On the Complexity of Bicoloring Clique Hypergraphs of Graphs / J. Kratochvil ; Zs. Tuza
Weakly Chordal Graph Algorithms via Handles / Ryan B. Hayward ; Jeremy Spinrad ; R. Sritharan
Recognizing Dart-Free Perfect Graphs / V. Chvatal ; J. Fonlupt ; L. Sun ; A. Zemirline
An Optimal Algorithm for Hyperplane Depth in the Plane / Stefan Langerman ; William SteigerSession 1C：
On Heilbronn's Problem in Higher Dimension / Hanno Lefmann
Finding Minimal Triangulations of Convex 3-Polytopes Is NP-Hard / Alexander Below ; Jesus A. De Loera ; Jurgen Richter-Gebert
A Point-Placement Strategy for Conforming Delaunay Tetrahedralization / Michael Murphy ; David M. Mount ; Carl W. Gable
Digraph Minors and Algorithms / Robin ThomasSession 2：
Cooperative Facility Location Games / Michel X. Goemans ; Martin SkutellaSession 3A：
K-Medians, Facility Location, and the Chernoff-Wald Bound / Neal E. Young
Improved Approximation Algorithms for MAX SAT / Takao Asano ; David P. Williamson
Strengthening Integrality Gaps for Capacitated Network Design and Covering Problems / Robert D. Carr ; Lisa K. Fleischer ; Vitus J. Leung ; Cynthia A. Phillips
Towards a 4/3 Approximation for the Asymmetric Traveling Salesman Problem / Robert Carr ; Santosh Vempala
Typical Random 3-SAT Formulae and the Satisfiability Threshold / Olivier Dubois ; Yacine Boufkhad ; Jacques MandlerSession 3B：
A Lower Bound for DLL Algorithms for k-SAT / Pavel Pudlak ; Russell Impagliazzo
On Permutations with Limited Independence / Toshiya Itoh ; Yoshinori Takei ; Jun Tarui
Min-Wise Versus Linear Independence / Andrei Z. Broder ; Uriel Feige
Hamiltonicity and Colorings of Arrangement Graphs / Stefan Felsner ; Ferran Hurtado ; Marc Noy ; Ileana Streinu
Testing and Spot-Checking of Data Streams / J. Feigenbaum ; S. Kannan ; M. Strauss ; M. ViswanathanSession 3C：
Engineering the Compression of Massive Tables: An Experimental Approach / Adam L. Buchsbaum ; Donald F. Caldwell ; Kenneth W. Church ; Glenn S. Fowler ; S. Muthukrishnan
On the Temporal HZY Compression Scheme / Z. Cohen ; Y. Matias ; S. C. Sahinalp ; J. Ziv
Height in a Digital Search Tree and the Longest Phrase of the Lempel-Ziv Scheme / Charles Knessl ; Wojciech Szpankowski
Communication Complexity of Document Exchange / Graham Cormode ; Mike Paterson ; Suleyman Cenk Sahinalp ; Uzi Vishkin
Scheduling a Pipelined Operator Graph / Petra Schuurman ; Gerhard J. WoegingerSession 4A：
A PTAS for the Multiple Knapsack Problem / Chandra Chekuri ; Sanjeev Khanna
Approximation Algorithms for Data Placement on Parallel Disks / L. Golubchik ; S. Khanna ; S. Khuller ; R. Thurimella ; A. Zhu
Movement Minimization in Conveyor Flow Shop Processing / W. Espelage ; E. Wanke
Forcing Relations for AND/OR Precedence Constraints / Rolf H. Mohring ; Frederik Stork
The Interlace Polynomial: A New Graph Polynomial / Richard Arratia ; Bela Bollobas ; Gregory B. SorkinSession 4B：
The Complexity of Counting Graph Homomorphisms / Martin Dyer ; Catherine Greenhill
A Fast Algorithm to Generate Unlabeled Necklaces / Frank Ruskey ; Joe Sawada
Construction of Visual Secret Sharing Schemes with Almost Optimal Contrast / Christian Kuhlmann ; Hans Ulrich Simon
Sharing One Secret vs. Sharing Many Secrets: Tight Bounds on the Average Improvement Ratio / Giovanni Di Crescenzo
Algorithmic Strategies in Combinatorial Chemistry / Deborah Goldman ; Sorin Istrail ; Antonio Piccolboni ; Brian WalenzSession 4C：
Computing the Quartet Distance Between Evolutionary Trees / David Bryant ; John Tsang ; Paul Kearney ; Ming Li
A Practical Algorithm for Recovering the Best Supported Edges of an Evolutionary Tree / Vincent Berry ; Tao Jiang ; Todd Wareham ; Haoyong Zhang
Pattern Discovery on Character Sets and Real-Valued Data: Linear Bound on Irredundant Motifs and an Efficient Polynomial Time Algorithm / Laxmi Parida ; Isidore Rigoutsos ; Aris Floratos ; Dan Platt ; Yuan Gao
Improved Bounds on the Sample Complexity of Learning / Yi Li ; Philip M. Long ; Aravind Srinivasan
On Local Search and Placement of Meters in Networks / Samir Khuller ; Randeep Bhatia ; Robert PlessSession 5A：
Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs / Eran Halperin
An Approximation Algorithm for the Covering Steiner Problem / Goran Konjevod ; R. Ravi
On the Red-Blue Set Cover Problem / Srinivas Doddi ; Madhav Marathe
Approximate Congruence In Nearly Linear Time / Piotr Indyk ; Suresh VenkatasubramanianSession 5B：
Locally Lifting the Curse of Dimensionality for Nearest Neighbor Search / Peter N. Yianilos
Dimensionality Reduction Techniques for Proximity Problems
Expected-Case Complexity of Approximate Nearest Neighbor Searching / Sunil Arya ; Ho-Yam Addy Fu
A Dynamic Programming Approach to De Novo Peptide Sequencing via Tandem Mass Spectrometry / Ting Chen ; Ming-Yang Kao ; Matthew Tepel ; John Rush ; George M. ChurchSession 5C：
Algorithms for Optimizing Production DNA Sequencing / Eva Czabarka ; Madhav V. Marathe ; Allon G. Percus ; David C. Torney
Estimating DNA Sequence Entropy / J. Kevin Lanctot ; En-hui Yang
Selective Mapping: A Discrete Optimization Approach to Selecting a Population Subset for Use in a High-Density Genetic Mapping Project / Daniel G. Brown ; Todd J. Vision ; Steven D. Tanksley
Cutting Planes and the Traveling Salesman Problem / D. Applegate ; R. Bixby ; W. CookSession 6：
Caching in Networks / Friedhelm Meyer auf der Heide ; Berthold Vocking ; Matthias WestermannSession 7A：
Instability of FIFO in Session-Oriented Networks / Matthew Andrews
The Effects of Temporary Sessions on Network Performance / Lisa Zhang
Randomized Greedy Hot-Potato Routing / Costas Busch ; Maurice Herlihy ; Roger Wattenhofer
On Deciding Stability of Scheduling Policies in Queueing Systems / David Gamarnik
Restructuring Ordered Binary Trees / William Evans ; David KirkpatrickSession 7B：
Faster Deterministic Dictionaries / Rasmus Pagh
Competitive Tree-Structured Dictionaries / Michael T. Goodrich
Even Strongly Universal Hashing Is Pretty Fast / Mikkel Thorup
Word Encoding Tree Connectivity Works / Stephen Alstrup ; Jens Peter Secher
Algorithms for Minimum Volume Enclosing Simplex in R[superscript 3] / Yunhong Zhou ; Subhash SuriSession 7C：
Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells / Pankaj K. Agarwal ; Boris Aronov ; Micha Sharir
Evaluating the Cylindricity of a Nominally Cylindrical Point Set / Olivier Devillers ; Franco P. Preparata
Approximation Algorithms for Layered Manufacturing / Pavan K. Desikan
Approximation Algorithms for Projective Clustering / Cecilia M. Procopiuc
Scheduling to Minimize Average Stretch Without Migration / Luca Becchetti ; Stefano LeonardiSession 8A：
Minimizing Maximum Response Time in Scheduling Broadcasts / Yair Bartal
Applying Extra-Resource Analysis to Load Balancing / Mark Brehob ; Eric Torng ; Patchrawat Uthaisombut
Balancing Steiner Trees and Shortest Path Trees Online / Ashish Goel ; Kamesh Munagala
Generating Adversaries for Request-Answer Games / Todd Gormley ; Nicholas Reingold ; Jeffery Westbrook
Maintaining Hierarchical Graph Views / Jeffrey R. WestbrookSession 8B：
Improved Classification via Connectivity Information / Robert Krauthgamer ; Michael Mitzenmacher
Efficient Dynamic Traitor Tracing / Omer Berkman ; Michal Parnas ; Jiri Sgall
Watermarking Maps: Hiding Information in Structured Data / Francis Zane
Strictly Non-Blocking WDM Cross-Connects / April Rasala ; Gordon Wilfong
An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colourings / Leslie Ann Goldberg ; Mark JerrumSession 8C：
A Faster Method for Sampling Independent Sets / Mark Huber
Strong Bias of Group Generators: An Obstacle to the "Product Replacement Algorithm" / Laszlo Babai ; Igor Pak
Random Three-Dimensional Tilings of Aztec Octahedra and Tetrahedra: An Extension of Domino Tilings / Dana Randall ; Gary Yngve
An Algebraic Method to Compute a Shortest Path of Local Flips Between Two Tilings / Eric Remila
Coloring Powers of Planar Graphs / Geir Agnarsson ; Magnus M. HalldorssonSession 9A：
Directed Network Design with Orientation Constraints / Joseph (Seffi) Naor ; F. Bruce Shepherd
A (2 + [varepsilon])-Approximation Scheme for Minimum Domination on Circle Graphs / Mirela Damian-lordache ; Sriram V. Pemmaraju
An Approximation Algorithm for Finding a Long Path in Hamiltonian Graphs / Sundar Vishwanathan
TSP-Based Curve Reconstruction in Polynomial Time / Ernst Althaus ; Kurt MehlhornSession 9B：
A Tree-Edit-Distance Algorithm for Comparing Simple, Closed Shapes / Philip Klein ; Srikanta Tirthapura ; Daniel Sharvit ; Ben Kimia
Computing the Arrangement of Curve Segments: Divide-and-Conquer Algorithms via Sampling / Nancy M. Amato ; Edgar A. Ramos
Optimizing the Sum of Linear Fractional Functions and Applications / Danny Z. Chen ; Ovidiu Daescu ; Yang Dai ; Naoki Katoh ; Xiaodong Wu ; Jinhui Xu
Edge-Disjoint Paths in Expander Graphs / Alan M. FriezeSession 9C：
Escaping a Grid by Edge-Disjoint Paths / Wun-Tat Chan ; Francis Y. L. Chin ; Hing-Fung Ting
Fast Randomized Algorithms for Computing Minimum (3,4,5,6)-Way Cuts / Matthew S. Levine
Adaptive Set Intersections, Unions, and Differences / Erik D. Demaine ; Alejandro Lopez-Ortiz ; J. Ian Munro
The Whole Genome Assembly of Drosophila / Gene MyersSession 10：
A 2 + [varepsilon] Approximation Algorithm for the k-MST Problem / Sanjeev Arora ; George KarakostasSession 11A：
The Prize Collecting Steiner Tree Problem: Theory and Practice / David S. Johnson ; Maria Minkoff ; Steven Phillips
Improved Steiner Tree Approximation in Graphs / Gabriel Robins ; Alexander Zelikovsky
The Rectilinear Steiner Arborescence Problem Is NP-Complete / Weiping Shi ; Chen Su
Improved Bandwidth Approximation for Trees / Anupam Gupta
Faster Algorithms for String Matching with k Mismatches / Amihood Amir ; Moshe Lewenstein ; Ely PoratSession 11B：
On the Shared Substring Alignment Problem / Gad M. Landau ; Michal Ziv-Ukelson
Real Scaled Matching / Ayelet Butman
Inplace Run-Length 2d Compressed Search / Dina Sokol
Pattern Matching in Dynamic Texts / Gerth Stolting Brodal ; Theis Rauhe
Towards a Theory of Cache-Efficient Algorithms / Sandeep Sen ; Siddhartha ChatterjeeSession 11C：
Efficient Bundle Sorting / Yossi Matias ; Eran Segal ; Jeffrey Scott Vitter
Fast Concurrent Access to Parallel Disks / Peter Sanders ; Sebastian Egner ; Jan Korst
On External Memory Graph Traversal / Michael Goldwasser ; Jeffery R. Westbrook
Deterministic Broadcasting in Unknown Radio Networks / Bogdan S. Chlebus ; Leszek Gasieniec ; Alan Gibbons ; Andrzej Pelc ; Wojciech Rytter
New and Improved Algorithms for Minsum Shop Scheduling / Maurice Queyranne ; Maxim SviridenkoSession 12A：
Off-Line Admission Control for General Scheduling Problems / R. N. Uma ; Joel Wein
Approximating the Maximum Quadratic Assignment Problem / Esther M. Arkin ; Refael Hassin
Accurate Approximations for Asian Options / Donald Aingworth ; Rajeev Motwani ; Jeffrey D. Oldham
Finite-Resolution Hidden Surface Removal / Jeff EricksonSession 12B：
On Incremental Rendering of Silhousette Maps of a Polyhedral Scene / Alon Efrat ; Leonidas J. Guibas ; Olaf A. Hall-Holt ; Li Zhang
Computing Contour Trees in All Dimensions / Hamish Carr ; Jack Snoeyink ; Ulrike Axen
Sweeping Simple Polygons with a Chain of Guards / Sariel Har-Peled ; David C. Lin ; Joseph S. B. Mitchell ; T. M. Murali
Finding the Closest Lattice Vector When It's Unusually Close / Session 12C：
A New Bound for the Caratheodory Rank of the Bases of a Matroid / J. C. de Pina ; J. Soares
Minimum Ratio Canceling Is Oracle Polynomial for Linear Programming, But Not Strongly Polynomial, Even for Networks / S. Thomas McCormick ; Akiyoshi Shioura
Nearly Optimal Computations with Structured Matrices / Victor Y. Pan
Author Index
Preface
Acknowledgments
[varepsilon]-Approximate Linear Progams: New Bounds and Computation / Daniel BienstockSession 1A：
2.

図書
図書
2. Proceedings of the ninth annual ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms ; ACM Special Interest Group on Algorithms and Computation Theory ; SIAM Activity Group on Discrete Mathematics
出版情報: New York : Association for Computing Machinery , Philadelphia : Society for Industrial and Applied Mathematics, c1998  xii, 704 p. ; 28 cm
所蔵情報: loading…
3.

図書
図書
3. Proceedings of the tenth annual ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms ; ACM Special Interest Group on Algorithms and Computation Theory ; SIAM Activity Group on Discrete Mathematics
出版情報: New York : Association for Computing Machinery , Philadelphia : Society for Industrial and Applied Mathematics, c1999  xvii, 992 p. ; 28 cm
所蔵情報: loading…
4.

図書
図書
4. Proceedings of the eighth annual ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms ; ACM Special Interest Group on Algorithms and Computation Theory ; SIAM Activity Group on Discrete Mathematics
出版情報: New York : Association for Computing Machinery , Philadelphia : Society for Industrial and Applied Mathematics, c1997  x, 788 p. ; 28 cm
所蔵情報: loading…
5.

図書
図書
5. Proceedings of the sixth annual ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms ; ACM Special Interest Group for Automata and Computability Theory ; SIAM Activity Group on Discrete Mathematics
出版情報: New York : Association for Computing Machinery , Philadelphia : Society for Industrial and Applied Mathematics, c1995  654 p. ; 28 cm
所蔵情報: loading…
6.

図書
図書
6. Proceedings of the seventh annual ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms ; ACM Special Interest Group on Algorithms and Computation Theory ; SIAM Activity Group on Discrete Mathematics
出版情報: New York : Association for Computing Machinery , Philadelphia : Society for Industrial and Applied Mathematics, c1996  586 p. ; 28 cm
所蔵情報: loading…
7.

雑誌
雑誌
7. Proceedings of the ... annual ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms ; ACM Special Interest Group for Automata and Computability Theory ; SIAM Activity Group on Discrete Mathematics
出版情報: New York : Association for Computing Machinery , Philadelphia : Society for Industrial and Applied Mathematics  v. ; 28 cm
所蔵情報: loading…
8.

図書
図書
8. Proceedings of the fifth annual ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms ; ACM Special Interest Group for Automata and Computability Theory ; SIAM Activity Group on Discrete Mathematics
出版情報: New York : Association for Computing Machinery , Philadelphia : Society for Industrial and Applied Mathematics, c1994  735 p. ; 28 cm
所蔵情報: loading…
9.

図書
図書
9. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms ; ACM Special Interest Group on Algorithms and Computation Theory ; SIAM Activity Group on Discrete Mathematics
出版情報: New York : Association for Computing Machinery , Philadelphia : Society for Industrial and Applied Mathematics, c2003  xvi, 874 p. ; 28 cm
所蔵情報: loading…
目次情報: 続きを見る
Preface
Acknowledgments
In Memoriam
Optimal Parallel Selection / Yijie HanSession 1A：
Selection with Monotone Comparison Costs / Sampath Kannan ; Sanjeev Khanna
Property Testing of Data Dimensionality / Robert Krauthgamer ; Ori Sasson
Comparing Top K Lists / Ronald Fagin ; Ravi Kumar ; D. Sivakumar
Algorithms for Power Savings / Sandy Irani ; Sandeep Shukla ; Rajesh GuptaSession 1B：
Dynamic TCP Acknowledgement: Penalizing Long Delays / Susanne Albers ; Helge Bals
Approximately Optimal Control of Fluid Networks / Lisa Fleischer ; Jay Sethuraman
Minimum Cost Flows over Time without Intermediate Storage / Martin Skutella
Sublogarithmic Approximation for Telephone Multicast: Path out of Jungle / Michael Elkin ; Guy KortsarzSession 1C：
On the Performance of User Equilibria in Traffic Networks / Andreas S. Schulz ; Nicolas Stier Moses
Faster Approximation Algorithms for the Minimum Latency Problem / Aaron Archer ; David P. Williamson
Data Migration to Minimize the Average Completion Time / Yoo-Ah Kim
Invited Plenary Abstract / Session 2：
Browsing around a Digital Library / Ian H. Witten
Binary Space Partitions for 3D Subdivisions / John Hershberger ; Subhash SuriSession 3A：
Allocating Vertex [pi]-Guards in Simple Polygons via Pseudo-triangulations / Bettina Speckmann ; Csaba D. Toth
Straight-Skeleton Based Contour Interpolation / Gill Barequet ; Michael T. Goodrich ; Aya Levi-Steiner ; Dvir Steiner
Mobius-Invariant Natural Neighbor Interpolation / Marshall Bern ; David Eppstein
Improved Bounds on the Average Length of Longest Common Subsequences / George S. LuekerSession 3B：
Directed Scale-Free Graphs / Bela Bollobas ; Christian Borgs ; Jennifer Chayes ; Oliver Riordan
The Cover Time of Sparse Random Graphs / Colin Cooper ; Alan Frieze
Perfect Matchings in Random Graphs with Prescribed Minimal Degree / Boris Pittel
Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs / Dieter Kratsch ; Ross M. McConnell ; Kurt Mehlhorn ; Jeremy P. SpinradSession 3C：
Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-up / Fedor V. Fomin ; Dimitrios M. Thilikos
Quick and Good Facility Location / Mikkel Thorup
Chain Decompositions and Independent Trees in 4-Connected Graphs / Sean Curran ; Orlando Lee ; Xingxing Yu
Optimizing Misdirection / Piotr Berman ; Piotr KrystaSession 4A：
Online Learning in Online Auctions / Avrim Blum ; Vijay Kumar ; Atri Rudra ; Felix Wu
An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents / Christos Papadimitriou ; Kunal Talwar ; Eva Tardos
Competitiveness via Consensus / Andrew V. Goldberg ; Jason D. Hartline
Pass Efficient Algorithms for Approximating Large Matrices / Petros Drineas ; Ravi KannanSession 4B：
Rangesum Histograms / S. Muthukrishnan ; Martin Strauss
Approximation of Functions over Redundant Dictionaries Using Coherence / Anna C. Gilbert ; Martin J. Strauss
Counting Inversions in Lists / Anupam Gupta ; Francis X. Zane
Certifying and Repairing Solutions to Large LPs: How Good Are LP-Solvers? / Marcel Dhiflaoui ; Stefan Funke ; Carsten Kwappik ; Michael Seel ; Elmar Schomer ; Ralph Schulte ; Dennis WeberSession 4C：
An Improved Approximation Algorithm for the O-Extension Problem / Jittat Fakcharoenphol ; Chris Harrelson ; Satish Rao
Packing Steiner Trees / Kamal Jain ; Mohammad Mahdian ; Mohammad R. Salavatipour
Integrality Ratio for Group Steiner Trees and Directed Steiner Trees / Eran Halperin ; Aravind Srinivasan ; Nan Wang
The Flow Complex: A Data Structure for Geometric Modeling / Joachim Giesen ; Matthias JohnSession 5A：
Graded Conforming Delaunay Tetrahedralization with Bounded Radius-Edge Ratio / Siu-Wing Cheng ; Sheung-Hung Poon
On the Combinatorial Complexity of Euclidean Voronoi Cells and Convex Hulls of d-Dimensional Spheres / Jean-Daniel Boissonnat ; Menelaos I. Karavelas
Perturbations and Vertex Removal in a 3D Delaunay Triangulation / Olivier Devillers ; Monique Teillaud
Root Comparison Techniques Applied to Computing the Additively Weighted Voronoi Diagram / Ioannis Z. Emiris
Random Walks on the Vertices of Transportation Polytopes with Constant Number of Sources / Mary Cryan ; Martin Dyer ; Haiko Muller ; Leen StougieSession 5B：
Smaller Explicit Superconcentrators / N. Alon ; M. Capalbo
A (1 + [epsilon])-Approximation Algorithm for Partitioning Hypergraphs Using a New Algorithmic Version of the Lovasz Local Lemma
A Spectral Technique for Random Satisfiable 3CNF Formulas / Abraham Flaxman
Random MAX SAT, Random MAX CUT, and Their Phase Transitions / Don Coppersmith ; David Gamarnik ; Mohammad Hajiaghayi ; Gregory B. Sorkin
Space-Efficient Finger Search on Degree-Balanced Search Trees / Guy E. Blelloch ; Bruce M. Maggs ; Shan Leung Maverick WooSession 5C：
Skip Graphs / James Aspnes ; Gauri Shah
Maintaining All-Pairs Approximate Shortest Paths under Deletion of Edges / Surender Baswana ; Ramesh Hariharan ; Sandeep Sen
A Faster and Simpler Fully Dynamic Transitive Closure / Liam Roditty
Data Streams: Algorithms and Applications / Session 6：
Sparse Distance Preservers and Additive Spanners / Session 7A：
Multi-Embedding and Path Approximation of Metric Spaces / Yair Bartal ; Manor Mendel
Approximation Algorithm for Embedding Metrics into a Two-Dimensional Space / Mihai Badoiu
On the Complexity of Distance-Based Evolutionary Tree Reconstruction / Valerie King ; Li Zhang ; Yunhong Zhou
Improved Results for Directed Multicut / Session 7B：
Algorithms for k-Colouring and Finding Maximal Independent Sets / Jesper Makholm Byskov
Equitable Colorings with Constant Number of Colors / S. V. Pemmaraju ; K. Nakprasit ; A. V. Kostochka
Better Performance Bounds for Finding the Smallest k-Edge Connected Spanning Subgraph of a Multigraph / Harold N. Gabow
A Note on the Set Systems Used for Broadcast Encryption / Alexander RussellSession 7C：
Lower Bounds for Collusion-Secure Fingerprinting / Chris Peikert ; Abhi Shelat ; Adam Smith
Quantum Property Testing / Harry Burhman ; Lance Fortnow ; Ilan Newman ; Hein Rohrig
Quantum Algorithms for Some Hidden Shift Problems / Wim van Dam ; Sean Hallgren ; Lawrence Ip
Simulataneous Optimization for Concave Costs: Single Sink Aggregation or Single Source Buy-at-Bulk / Ashish Goel ; Deborah EstrinSession 8A：
Non-independent Randomized Rounding / Benjamin Doerr
Minimizing Weighted Flow Time / N. Bansal ; K. Dhamdhere
A Combinatorial Algorithm for Computing a Maximum Independent Set in a t-Perfect Graph / Friedrich Eisenbrand ; Naveen Garg ; Jochen Konemann
Lower Bounds for Embedding Edit Distance into Normed Spaces / A. Andoni ; M. Deza ; A. Gupta ; P. Indyk ; S. RaskhodnikovaSession 8B：
Embedding k-Outerplanar Graphs into l[subscript 1] / Chandra Chekuri ; Yuri Rabinovich ; Alistair Sinclair
Embeddings and Non-approximability of Geometric Problems / Venkatesan Guruswami ; Piotr Indyk
Better Algorithms for High-Dimensional Proximity Problems via Asymmetric Embeddings / Session 8C：
Lower Bounds for External Memory Dictionaries / Gerth Stolting Brodal ; Rolf Fagerberg
Online Paging with Arbitrary Associativity / Enoch Peserico
The Set-Associative Cache Performance of Search Trees / James D. Fix
Computing Strongly Connected Components in a Linear Number of Symbolic Steps / Raffaella Gentilini ; Carla Piazza ; Alberto Policriti
On the Rectilinear Crossing Number of Complete Graphs / Uli WagnerSession 9A：
Matching Planar Maps / Helmut Alt ; Alon Efrat ; Gunter Rote ; Carola Wenk
Dynamic Generators of Topologically Embedded Graphs
Computing Homotopic Shortest Paths in the Plane / Sergei Bespamyatnikh
Fully-Dynamic Two Dimensional Orthogonal Range and Line Segment Intersection Reporting in Logarithmic Time / Christian Worm Mortensen
Edge Disjoint Paths Revisited / Session 9B：
A New Approximation Algorithm for the Asymmetric TSP with Triangle Inequality / Markus Blaser
Approximating Asymmetric Maximum TSP / Moshe Lewenstein ; Maxim Sviridenko
The k-Traveling Repairman Problem
Directed Graphs Requiring Large Numbers of Shortcuts / William Hesse
Implicit Dictionaries Supporting Searches and Amortized Updates in O(log n log log n) Time / Gianni Franceschini ; Roberto GrossiSession 9C：
Compact Representations of Separable Graphs / Daniel K. Blandford ; Ian A. Kash
Labeling Schemes for Small Distances in Trees / Stephen Alstrup ; Philip Bille ; Theis Rauhe
On AC[superscript 0] Implementations of Fusion Trees and Atomic Heaps
Who Cares about Permanents? / Persi DiaconisSession 10：
Between O(nm) and O(n[superscript alpha]) / Jeremy SpinradSession 11A：
Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons / Devdatt Dubhashi ; Alessandro Mei ; Alessandro Panconesi ; Jaikumar Radhakrishnan
A 5/4-Approximation Algorithm for Minimum 2-Edge-Connectivity / Raja Jothi ; Balaji Raghavachari ; Subramanian Varadarajan
Fault-Tolerant Facility Location / Chaitanya Swamy ; David B. Shmoys
Efficient Sequences of Trials / Edith Cohen ; Amos Fiat ; Haim KaplanSession 11B：
Pursuit-Evasion with Imprecise Target Location / Gunther Rote
Unconditional Proof of Tightness of Johnson Bound / Vendatesan Guruswami ; Igor Shparlinski
Deterministic Identity Testing for Multivariate Polynomials / Richard Lipton ; Nisheeth Vishnoi
Competitive Queueing Policies for QoS Switches / Nir Andelman ; Yishay Mansour ; An ZhuSession 11C：
Dynamic Routing on Networks with Fixed-Size Buffers / William Aiello ; Rafail Ostrovsky ; Eyal Kushilevitz ; Adi Rosen
Dynamic Construction of Bluetooth Scatternets of Fixed Degree and Low Diameter / Lali Barriere ; Pierre Fraigniaud ; Lata Narayanan ; Jaroslav Opatrny
Scheduling Techniques for Media-on-Demand / Amotz Bar-Noy ; Richard E. Ladner ; Tami Tamir
Smaller Core-Sets for Balls / Mihal Badoiu ; Kenneth L. ClarksonSession 12A：
Zonotopes as Bounding Volumes / Leonidas J. Guibas ; An Nguyen
Sublinear-Time Approximation of Euclidean Minimum Spanning Tree / Artur Czumaj ; Funda Ergun ; Avner Magen ; Ronitt Rubinfeld ; Christian Sohler
An Approximation Algorithm for Cutting Out Convex Polygons / Adrian Dumitrescu
Inferring Tree Topologies Using Flow Tests / Torsten Suel ; Radek VingralekSession 12B：
Wavelength Assignment and Generalized Interval Graph Coloring / Peter Winkler ; Lisa Zhang
An Improved Approximation Algorithm for the Partial Latin Square Extension Problem / Carla P. Gomes ; Rommel G. Regis
Multirate Rearrangeable Clos Networks and a Generalized Edge Coloring Problem on Bipartite Graphs / Hung Q. Ngo ; Van H. Vu
High-Order Entropy-Compressed Text Indexes / Ankur Gupta ; Jeffrey Scott VitterSession 12C：
Multidimensional Matching and Fast Search in Suffix Trees / Richard Cole
Inplace 2D Matching in Compressed Images / Amihood Amir ; Gad M. Landau ; Dina Sokol
The Similarity Metric / Ming Li ; Xin Chen ; Xin Li ; Bin Ma ; Paul Vitanyi
Author Index
Preface
Acknowledgments
In Memoriam
10.

図書
図書
10. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms ; ACM Special Interest Group on Algorithms and Computation Theory ; SIAM Activity Group on Discrete Mathematics
出版情報: New York : Association for Computing Machinery , Philadelphia : Society for Industrial and Applied Mathematics, c2004  xvi, 1132 p. ; 28 cm
所蔵情報: loading…
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼