Research Catalog

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

Holdings

Details

Additional Authors

• Rolim, José D. P.
• International Workshop on Randomization and Approximation Techniques in Computer Science (1997 : Bologna, Italy)

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