Research Catalog
Randomization and approximation techniques in computer science : international workshop RANDOM '97, Bologna, Italy, July 11-12,1997 : proceedings
- Title
- Randomization and approximation techniques in computer science : international workshop RANDOM '97, Bologna, Italy, July 11-12,1997 : proceedings / José Rolim, ed.
- Publication
- New York : Springer, 1997.
Items in the Library & Off-site
Filter by
1 Item
Status | Format | Access | Call Number | Item Location |
---|---|---|---|---|
Text | Request in advance | QA76 .R266 1997 | Off-site |
Holdings
Details
- Additional Authors
- Description
- viii, 225 pages : illustrations; 24 cm.
- Series Statement
- Lecture notes in computer science ; 1269
- Uniform Title
- Lecture notes in computer science ; 1269.
- Subject
- Computer science > Statistical methods > Congresses
- Note
- Proceedings of the Workshop on Randomzation adn Approximation Techniques in Computer Science held at the University of Bologna.
- Bibliography (note)
- Includes bibliographical references and index.
- Contents
- Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems / Marek Karpinski -- Average-Case Complexity of Shortest-Paths Problems in the Vertex-Potential Model / Colin Cooper, Alan Frieze and Kurt Mehlhorn [et al.] -- Approximation Algorithms for Covering Polygons with Squares and Similar Problems / Christos Levcopoulos and Joachim Gudmundsson -- Greedily Approximating the r-independent Set and k-center Problems on Random Instances / Bernd Kreuter and Till Nierhoff -- Nearly Linear Time Approximation Schemes for Euclidean TSP and Other Geometric Problems / Sanjeev Arora -- Random Sampling of Euler Tours / Prasad Tetali and Santosh Vempala -- A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem / Oded Goldreich and Shmuel Safra -- Super-bits, Demi-bits, and NP/̃qpoly-natural Proofs / Steven Rudich -- Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols / Michael Saks and Shiyu Zhou --
- Approximation on the Web: A Compendium of NP Optimization Problems / Pierluigi Crescenzi and Viggo Kann -- Random-Based Scheduling: New Approximations and LP Lower Bounds / Andreas S. Schulz and Martin Skutella -- 'Go with the winners' Generators with Applications to Molecular Modeling / Marcus Peinado and Thomas Lengauer -- Probabilistic Approximation of Some NP Optimization Problems by Finite-State Machines / Dawei Hong and Jean-Camille Birget -- Using Hard Problems to Derandomize Algorithms: An Incomplete Survey / Russell Impagliazzo -- Weak and Strong Recognition by 2-way Randomized Automata / Andris Ambainis, Rusins Freivalds and Marek Karpinski -- Tally Languages Accepted by Monte Carlo Pushdown Automata / Janis Kaneps, Dainis Geidmanis and Rusins Freivalds -- Resource-Bounded Randomness and Compressibility with Respect to Nonuniform Measures / Steven M. Kautz -- Randomness, Stochasticity and Approximations / Yongge Wang.
- ISBN
- 3540632484 (softcover : alk. paper)
- LCCN
- 97027556
- OCLC
- 37220997
- ocm37220997
- Owning Institutions
- Columbia University Libraries