Randomization and Approximation Techniques in Computer Science International Workshop RANDOM'97, Bologna, Italy, July 11-12, 1997 Proceedings

Randomization and Approximation Techniques in Computer Science International Workshop RANDOM'97, Bologna, Italy, July 11-12, 1997 Proceedings / edited by Jose Rolim.

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...

Full description

Saved in:
Bibliographic Details
Corporate Author: SpringerLink (Online service)
Other Authors: Rolim, Jose (Editor)
Format: eBook
Language:English
Published: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1997.
Edition:1st ed. 1997.
Series:Lecture Notes in Computer Science, 1269
Springer eBook Collection.
Subjects:
Computers.
Algorithms.
Computer science—Mathematics.
Calculus of variations.
Combinatorics.
Mathematical statistics.
Electronic resources (E-books)
Online Access:Click to view e-book
Holy Cross Note:Loaded electronically.
Electronic access restricted to members of the Holy Cross Community.
Table of Contents:
  • Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
  • Average-case complexity of shortest-paths problems in the vertex-potential model
  • Approximation algorithms for covering polygons with squares and similar problems
  • Greedily approximating the r-independent set and k-center problems on random instances
  • Nearly linear time approximation schemes for Euclidean TSP and other geometric problems
  • Random sampling of Euler tours
  • A combinatorial consistency lemma with application to proving the PCP theorem
  • Super-bits, demi-bits, and NP/qpoly-natural proofs
  • Sample spaces with small bias on neighborhoods and error-correcting communication protocols
  • Approximation on the web: A compendium of NP optimization problems
  • Random-based scheduling new approximations and LP lower bounds
  • ‘Go with the winners’ generators with applications to molecular modeling
  • Probabilistic approximation of some NP optimization problems by finite-state machines
  • Using hard problems to derandomize algorithms: An incomplete survey
  • Weak and strong recognition by 2-way randomized automata
  • Tally languages accepted by Monte Carlo pushdown automata
  • Resource-bounded randomness and compressibility with respect to nonuniform measures
  • Randomness, stochasticity and approximations.

Similar Items