Randomization and approximation techniques in computer science
Subtitle: international workshop RANDOM '97, Bologna, Italy, July 11-12, 1997 : proceedings
By: José Rolim, (ed.).
Contributors: Rolim, José D. P.
Series: Lecture notes in computer science -- 1269
Publisher: Springer
Published: 1997
Place of publication: Berlin; New York
Language: eng
Number of pages: 225
Subjects: Computer science -- Statistical methods -- Congresses
Description: This book constitutes the refereed proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97, held as a satelite meeting of ICALP'97, in Bologna, Italy, in July 1997. The volume presents 14 thoroughly revised full papers selected from 37 submissions; also included are four invited contributions by leading researchers. The book focuses on algorithms and complexity aspects arising in the development of efficient randomized solutions to computationally difficult problems. The papers are organized in sections on approximation, randomness, algorithms, and complexity.
Notes: Includes bibliographical references and index.
Table of contents: title: Polynomial time approximation schemes for some dense instances of NP-hard optimization problems / Marek Karpinski; title: Average-case complexity of shortest-paths problems in the vertex-potential model / Colin Cooper ... [et al.]; title: Approximation algorithms for covering polygons with squares and similar problems / Christos Levcopoulos and Joachim Gudmundsson; title: Greedily approximating the r-independent set and k-center problems on random instances / Bernd Kreuter and Till Nierhoff; title: Nearly linear time approximation schemes for Euclidean TSP and other geometric problems / Sanjeev Arora; title: Random sampling of Euler tours / Prasad Tetali and Santosh Vempala; title: A combinatorial consistency lemma with application to proving the PCP theorem / Oded Goldreich and Shmuel Safra; title: Super-bits, demi-bits, and NP̃/qpoly-natural proofs / Steven Rudich; title: Sample spaces with small bias on neighborhoods and error-correcting communication protocols / Michael Saks and Shiyu Zhou; title: Approximation on the Web : a compendium of NP optimization problems / Pierluigi Crescenzi and Viggo Kann; title: Random-based scheduling : new approximations and LP lower bounds / Andreas S. Schulz and Martin Skutella; title: 'Go with the winners' generators with applications to molecular modeling / Marcus Peinado and Thomas Lengauer; title: Probabilistic approximation of some NP optimization problems by finite-state machines / Dawei Hong and Jean-Camille Birget; title: Using hard problems to derandomize algorithms : an incomplete survey / Russell Impagliazzo; title: Weak and strong recognition by 2-way randomized automata / Andris Ambainis, Rūsiņs̆ Freivalds and Marek Karpinski; title: Tally languages accepted by Monte Carlo pushdown automata / Jānis Kaņeps, Dainis Geidmanis and Rūsiņs Freivalds; title: Resources-bounded randomness and compressibility with respect to nonuniform measures / Steven M. Kautz; title: Randomness, stochasticity, and approximations / Yongge Wang.