sponsored by the Computer Society of the IEEE Technical Committee on Mathematical Foundations of Computing in cooperation with ACM SIGACT, Association for Symbolic Logic, European Association for Theoretical Computer Science
出版情報:
Washington, D.C. : Computer Society Press of the IEEE , Los Angeles, CA : Order from Computer Society of the IEEE, c1987 xi, 361 p. ; 28 cm
sponsored by the Association for Computing Machinery Special Interest Group on Automata and Computability Theory, with the cooperation of the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing and Computer Science Department, University of California, Los Angeles, California
sponsored by the Association for Computing Machinery, Special Interest Group on Automata and Computability Theory, with the cooperation of the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing and Department of Electrical Engineering and Computer Science, University of Wisconsin, Milwaukee, Wisconsin
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：
edited by Hermann Hellwagner ; held in conjunction with and sponsored by the 11th International Parallel Processing Symposium in cooperation with IEEE Computer Society Technical Committee on Parallel Processing, ACM SIGARCH
出版情報:
Los Alamitos, Calif. : IEEE Computer Society Press, c1997 viii, 135 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, c1998 xii, 704 p. ; 28 cm
Logic Programming and Model Checking / Baoqiu Cui ; Yifei Dong ; Xiaoqun Du ; K. Narayan Kumar ; C. R. Ramakrishnan ; I. V. Ramakrishnan ; Abhik Roychoudhury ; Scott A. Smolka ; David S. Warren
Logic Programming I
CAT: The Copying Approach to Tabling / Bart Demoen ; Konstantinos Sagonas
SICStus MT - A Multithreaded Execution Environment for SICStus Prolog / Jesper Eskilson ; Mats Carlsson
A Framework for Bottom Up Specialisation of Logic Programs / Wim Vanhoof ; Danny De Schreye ; Bern Martens
Termination of Logic Programs with block Declarations Running in Several Modes / Jan-Georg Smaus ; Pat Hill ; Andy King
Static Analysis
The Boolean Logic of Set Sharing Analysis / Michael Codish ; Harald Søndergaard
Derivation of Proof Methods by Abstract Interpretation / Giorgio Levi ; Paolo Volpe
Detecting Unsolvable Queries for Definite Logic Programs / Maurice Bruynooghe ; Henk Vandecasteele ; D. Andre de Waal ; Marc Denecker
Staging Static Analyses Using Abstraction-Based Program Specialization / John Hatcliff ; Matthew Dwyer ; Shawn Laubach
An Experiment in Domain Refinement: Type Domains and Type Representations for Logic Programs / Fausto Spoto
Software Methodologies: Invited Paper Architecturing Software Using: A Methodology for Language Development / Charles Consel ; Renaud Marlet
Object Oriented Programming
Explicit Substitutions for Objects and Functions / Delia Kesner ; Pablo E. Mart'inez Lopez
The Complexity of Late-Binding in Dynamic Object-Oriented Languages / Enrico Pontelli ; Desh Ranjan ; Gopal Gupta
Operational Versus Denotational Methods in the Semantics of Higher Order Languages / Andrew M. Pitts
Functional Programming
Functional Implementations of Continuous Modeled Animation / Conal Elliott
Compiling Erlang to Scheme / Marc Feeley ; Martin Larose
From (Sequential) Haskell to (Parallel) Eden: An Implementation Point of View / Silvia Breitinger ; Ulrike Klusik ; Rita Loogen
Mobile Haskell: Compiling Lazy Functional Programs for the Java Virtual Machine / David Wakeling
Metaprogramming: Tutorial
Program Analysis in ?Prolog / John Hannan
Logic Programming II
A Game Semantics Foundation for Logic Programming / Roberto Di Cosmo ; Jean-Vincent Loddo ; Stephane Nicolet
Controlling Search in Declarative Programs / Michael Hanus ; Frank Steiner
Encapsulating Data in Logic Programming via Categorical Constraints / James Lipton ; Robert McGrail
Constructive Negation Using Typed Existence Properties / John G. Cleary ; Lunjin Lu
Optimal Evaluation: Tutorial
Optimal Reduction of Functional Expressions / Andrea Asperti
Integration
Embedding Multiset Constraints into a Lazy Functional Logic Language / P. Arenas-Sánchez ; F.J. López-Fraguas ; M. Rodr'iguez-Artalejo
A Hidden Herbrand Theorem / Joseph Goguen ; Grant Malcolm ; Tom Kemp
Constraint Solving
Integrating Constraint Propagation in Complete Solving of Linear
Diophantine Systems / Farid Ajili ; Hendrik C.R. Lock
Approaches to the Incremental Detection of Implicit Equalities with the Revised Simplex Method / Philippe Refalo
Author Index
Verification: Invited Paper
Logic Programming and Model Checking / Baoqiu Cui ; Yifei Dong ; Xiaoqun Du ; K. Narayan Kumar ; C. R. Ramakrishnan ; I. V. Ramakrishnan ; Abhik Roychoudhury ; Scott A. Smolka ; David S. Warren
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
organized by Warsaw University ; sponsored by IEEE Computer Society Technical Committee on Mathematical Foundations of Computing ; in cooperation with The Special Interest Group on Automata and Computability Theory of the Association for Computing Machinery, The Association for Symbolic Logic, The European Association for Theoretical Computer Science ; with support from BRICS, University of Aarhus ... [et. al]
出版情報:
Los Alamitos, Calif. ; Tokyo : IEEE Computer Society Press, c1997 xiv, 447 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
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
edited by Dexter Kozen ; sponsored by IEEE Computer Society Technical Committee on Mathematical Foundations of Computing ; in cooperation with Special Interest Group on Automata and Computability Theory of the ACM Association for Symbolic Logic, European Association for Theoretical Computer Science ; with support from AT & T Bell Laboratories IBM Almaden Research Center Rice University, University of California, San Diego
出版情報:
Los Alamitos, CA. ; Tokyo : IEEE Computer Society Press, c1995 xiii, 518 p. ; 28 cm
Amsterdam ; New York : North-Holand , New York, N.Y., U.S.A. : Sole distributors for the U.S.A. and Canada, Elsevier Science Pub. Co., 1985 xi, 243 p. ; 23 cm.
sponsored by IEEE Computer Society, Technical Committee on VLSI, in cooperation with Centre National de la Recherche Scientifique (CNRS), Institut d'Informatique et de Mathématiques Appliquées de Grenoble (IMAG) ; edited by Peter Kornerup, David W. Matula
出版情報:
Washington, D.C. ; Tokyo : IEEE Computer Society Press, c1991 xiii, 282 p. ; 29 cm
sponsored by the Association for Computing Machinery, Special Interest Group on Automata and Computability Theory [and] Special Interest Group on Programming Languages
sponsored by IEEE Technical Committee on Mathematical Foundations of Computing, CWI, Amsterdam, Vrije Universiteit, Amsterdam ; in cooperation with Association for Computing Machinery, Association for Symbolic Logic, European Association for Theoretical Computer Science
出版情報:
Los Alamitos, CA. ; Tokyo : IEEE Computer Society Press, c1991 xvii, 417 p. ; 28 cm
Amsterdam ; Tokyo : North-Holland , New York, N.Y., U.S.A. : Distributors for the U.S. and Canada, Elsevier Science Pub. Co., 1992 xiii, 405 p. ; 23 cm
Amsterdam ; New York : North-Holland , New York, N.Y., U.S.A. : Elsevier Science Pub. Co., distributors for the U.S. and Canada, c1990 viii, 581 p. ; 24 cm
sponsored by the IEEE Technical Committee on Mathematical Foundations of Computing ; in cooperation with Association for Computing Machinery-SIGACT, Association for Symbolic Logic, European Association for Theoretical Computer Science
出版情報:
Los Alamitos, CA. ; Tokyo : IEEE Computer Society Press, c1990 xvi, 509 p. ; 28 cm
Dordrecht, Holland ; Boston, U.S.A. : D. Reidel Pub. Co. , Hingham, MA : Distributed in the U.S.A. and Canada by Kluwer Boston Inc., c1983 ix, 374 p. ; 25 cm
sponsored by IEEE Computer Society, Technical Committee on Computer Architecture, Technical Committee on VLSI, in cooperation with Computer Science Department, University of California at Los Angeles and IFIP Working Group 2.5 ; editors, Miloš D. Ercegovac, Earl Swartzlander
出版情報:
Washington, D.C. ; Tokyo : IEEE Computer Society Press, c1989 xv, 247 p. ; 28 cm
Amsterdam ; New York : North-Holland Pub. Co. , New York : sole distributors for the U.S.A. and Canada, Elsevier North-Holland, 1979 ix, 297 p. ; 23 cm
sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing in cooperation with ACM SIGACT, Association for Symbolic Logic, European Association for Theoretical Computer Science
出版情報:
Washington, D.C. : IEEE Computer Society Press , Los Angeles, CA : Order from IEEE Computer Society, c1986 xi, 383 p. ; 28 cm
図書
雑誌
