Eric J. Donkor, Andrew R. Pirich, Howard E. Brandt, chairs/editors ; sponsored and published by SPIE--the International Society for Optical Engineering
出版情報:
Bellingham, Wash. : SPIE, c2006 1 v. (various pagings) ; 28 cm
Khan M. Iftekharuddin, Abdul Ahad S. Awwal, chairs/editors ; sponsored and published by SPIE--the International Society for Optical Engineering ; cooperating organizations, the Boeing Company
出版情報:
Bellingham, Washington : SPIE, c2002 x, 262 p. ; 28 cm
Edwin K. P. Chong, chair/editor ; sponsored ... by SPIE--the International Society for Optical Engineering ; cooperating organization, Colorado Photonics Industry Association
出版情報:
Bellingham, Wash. : SPIE, c2001 ix, 310 p. ; 28 cm
Belur V. Dasarathy, chair/editor ; sponsored and published by SPIE--the International Society for Optical Engineering ; cooperating organizations, Ball Aerospace & Technologies Corporation (USA) ... [et al.].
出版情報:
Bellingham, Wash. : SPIE, c2005 xi, 368 p. ; 28 cm
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
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
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:
Adaptively-Secure Distributed Public-Key Systems / Yair Frankel ; Moti Yung ; Philip MacKenzie
How Long Does a Bit Live in a Computer? / Bernhard Korte
Approximation Algorithms for the Traveling Purchaser Problem and Its Variants in Network Design / R. Ravi ; F. S. Salman
The Impact of Knowledge on Broadcasting Time in Radio Networks (Extended Abstract) / Krzysztof Diks ; Danny Krizanc ; Evangelos Kranakis ; Andrzej Pelc
Multipacket Routing on 2-D Meshes and Its Application to Fault-Tolerant Routing / Kazuo Iwama ; Eiji Miyano
IP Address Lookup Made Fast and Simple / Pierluigi Crescenzi ; Leandro Dardini ; Roberto Grossi
On-Line Load Balancing in a Hierarchical Server Topology / Amotz Bar-Noy ; Ari Freund ; Joseph Naor
Provably Good and Practical Strategies for Non-uniform Data Management in Networks / Friedhelm Meyer auf der Heide ; Matthias Westermann ; Berthold Vöcking
Approximation Algorithms for Restoration Capacity Planning / Steven J. Phillips ; JefferyR. Westbrook
Efficient Algorithms for Integer Programs with Two Variables per Constraint (Extended Abstract) / Reuven Bar-Yehuda ; Dror Rawitz
Convex Quadratic Programming Relaxations for Network Scheduling Problems / Martin Skutella
Resource-Constrained Project Scheduling: Computing Lower Bounds by Solving Minimum Cut Problems / RolfH. Möhring ; Frederik Stork ; Marc Uetz ; Andreas S. Schulz
Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines / Leah Epstein ; Jiří Sgall
Efficient Implementation of Lazy Suffix Trees / Robert Giegerich ; Stefan Kurtz ; Jens Stoye
Experiments with List Ranking for Explicit Multi-Threaded (XMT) Instruction Parallelism (Extended Abstract) / Shlomit Dascal ; Uzt Vishkin
Finding Minimum Congestion Spanning Trees / Renato Fonseca F. Werneck ; João Carlos Setubal ; Arlindo F. da Conceição
Evaluation of an Algorithm for the Transversal Hypergraph Problem / Dimitris J. Kavvadias ; Elias C. Stavropoulos
Construction Heuristics and Domination Analysis for the Asymmetrie TSP / Fred Glover ; Gregory Gutin ; Anders Yeo ; Alexey Zverovich
Counting in Mobile Networks: Theory and Experimentation / Kostas Hatzis ; George Pentaris ; Paul Spirakis ; Basil Tampakas
Dijkstra's Algorithm On-Line: An Empirical Case Study from Public Railroad Transport / Frank Schulz ; Dorothea Wagner ; Karsten Weihe
Implementation and Experimental Evaluation of Graph Connectivity Algorithms Using LEDA / Panagiota Fatourou ; Panagiotis Zarafidis ; Anna Zoura
On-Line Zone Construction in Arrangements of Lines in the Plane / Yuval Aharoni ; Dan Haiperin ; Iddo Hanniel ; Sariel Har-Peled ; Chaim Linhart
The Design and Implementation of Planar Maps in Cgal / Eyal Flato ; Dan Halperin ; Oren Nechushtan
An Easy to Use Implementation of Linear Perturbations within Cgal / Jochen Comes ; Mark Ziegelmann
Analysing Cache Effects in Distribution Sorting / Naila Rahman ; Rajeev Raman
Fast Regular Expression Search / Gonzalo Navarro ; Mathieu Raffinot
An Experimental Evaluation of Hybrid Data Structures for Searching / Maureen Korda
LEDA-SM: Extending LEDA to Secondary Memory / Andreas Crauser
A Priority Queue Transform / Michael L. Fredman
Implementation Issues and Experimental Study of a Wavelength Routing Algorithm for Irregular All-Optical Networks / Athanasios Bouganis ; Ioannis Caragiannis ; Christos Kaklamanis
Estimating Large Distances in Phylogenetic Reconstruction / Daniel H. Huson ; Kelly Ann Smith ; Tandy J. Warnow
The Performance of Concurrent Red-Black Tree Algorithms / Sabine Hanke
Performance Engineering Case Study: Heap Construction / Jesper Bojesen ; Jyrki Katajainen ; Maz Spork
A Fast and Simple Local Search for Graph Coloring / Massimiliano Caramia ; Paolo Dell'Olmo
BALL: Biochemical Algorithms Library / Nicolas Boghossian ; Oliver Kohlbacher ; Hans-Peter Lenhof
An Experimental Study of Priority Queues in External Memory / Klaus Brengel ; Paolo Ferragina ; Ulrich Meyer
Author Index
Invited Lectures
Selecting Problems for Algorithm Evaluation / Andrew V. Goldberg
BSP Algorithms - """"Write Once, Run Anywhere"""" / Bill McColl
Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots / Paola Flocchini ; Giuseppe Prencipe ; Nicola Santoro ; Peter Widmayer
Online Algorithm / Session 3(a):
On-Line Load Balancing of Temporary Tasks Revisited / Kar-Keung To ; Wai-Ha Wong
Online Routing in Triangulations / Prosenjit Bose ; Pat Morin
Complexity Theory I / Session 3(b):
The Query Complexity of Program Checking by Constant-Depth Circuits / V. Arvind ; K.V. Subrahmanyam ; N.V. Vinodchandran
Tree-Like Resolution Is Superpolynomially Slower Than DAG-LikeResolution for the Pigeonhole Principle / Kazuo Iwama ; Shuichi Miyazaki
Approximation Algorithms in Batch Processing / Xiaotie Deng ; Chung Keung Poon ; Yuzhong Zhang
Graph Algorithm I / Session 4(b):
LexBFS-Ordering in Asteroidal Triple-Free Graphs / Jou-Ming Chang ; Chin-Wen Ho ; Ming-Tat Ko
Parallel Algorithms for Shortest Paths and Related Problems on Trapezoid Graphs / F.R. Hsu ; Yaw-Ling Lin ; Yin-Te Tsai
Approximation Algorithms for Some Clustering and Classification Problems / Eva Tardos
Computational Geometry I / Session 5(a):
How Many People Can Hide in a Terrain? / Stephan Eidenbenz
Carrying Umbrellas: An Online Relocation Problem on Graphs / Jae-Ha Lee ; Chong-Dae Park ; Kyung-Yong Chwa
Parallel & Distributed Computing II / Session 5(b):
Survivable Networks with Bounded Delay: The Edge Failure Case / Serafino Cicerone ; Gabriele Di Stefano ; Dagmar Handke
Energy-Efficient Initialization Protocols for Ad-hoc Radio Networks / J.L. Bordim ; J. Cui ; T. Hayashi ; K. Nakano ; S. Olariu
Data Structure II / Session 6(a):
Constructing the Suffix Tree of a Tree with a Large Alphabet / Tetsuo Shibuya
An O(1) Time Algorithm for Generating Multiset Permutations / Tadao Takaoka
Complexity Theory II / Session 6(b):
Upper Bounds for MaxSat: Further Improved / Nikhil Bansal
A Linear Time Algorithm for Recognizing Regular Boolean Functions / Kazuhisa Makino
Computational Geometry II / Session 7(a):
Station Layouts in the Presence of Location Constraints / Christos Kaklamanis ; Lefteris M. Kirousis ; Evangelos Kranakis ; Danny Krizanc ; David Peleg
Reverse Center Location Problem / Jianzhong Zhang ; Xiaoguang Yang ; Mao-cheng Cai
Algorithms in Practice / Session 7(b):
Performance Comparison of Linear Sieve and Cubic Sieve Algorithms forDiscrete Logarithms over Prime Fields / Abhijit Das ; C.E. Veni Madhavan
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
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
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
jointly organized by IEEE Singapore Section, Computer Chapter, IEEE Singapore, and Department of Information Systems and Computer Science, National University of Singapore
出版情報:
[New York] : Institute of Electrical and Electronics Engineers , Piscataway, N.J. : IEEE Service Center, c1996 xix, 547 p. ; 31 cm
Connected components on distributed memory machines / A. Krishnamurthy ; S. S. Lumetta ; D. E. Culler ; K. Yelick
Parallel implementation of algorithms for finding connected components in graphs / T.-S. Hsu ; V. Ramachandran ; N. Dean
Connected components algorithms for mesh-connected parallel computers / S. Goddard ; S. Kumar ; J. F. Prins
Implementing parallel shortest-paths algorithms / M. Papaefthymiou ; J. Rodrigue
Finding friends-of-friends clusters quickly / B. Mumey
A practical comparison of $N$-body algorithms / G. Blelloch ; G. Narlikar
Parallel algorithms for geometric dominance problems / J. Petersson
The $\star$Socrates massively parallel chess program / C. F. Joerg ; B. C. Kuszmaul
Concurrent data structures and load balancing strategies for parallel branch-and-bound/A$^\ast$ algorithms / V.-D. Cung ; S. Dowaji ; B. LeCun ; T. Mautor ; C. Roucairol
Connected components on distributed memory machines / A. Krishnamurthy ; S. S. Lumetta ; D. E. Culler ; K. Yelick
Parallel implementation of algorithms for finding connected components in graphs / T.-S. Hsu ; V. Ramachandran ; N. Dean
Connected components algorithms for mesh-connected parallel computers / S. Goddard ; S. Kumar ; J. F. Prins
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
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