rdf-syntax-grammar
mods:
  schema location: http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-2.xsd
  title info:
    title: Randomization and Approximation Techniques in Computer Science
    sub title: International Workshop RANDOM'97, Bologna, Italy, July 11-12, 1997 Proceedings
  name:
    name part: Rolim, Jose.
    role:
      role term: editor.
    role:
      role term: edt
    role:
      role term: http://id.loc.gov/vocabulary/relators/edt
  name:
    name part: SpringerLink (Online service)
  type of resource: text
  origin info:
    place:
      place term: gw
    date issued: 1997
    edition: 1st ed. 1997.
    issuance: monographic
  language:
    language term: eng
  physical description:
    form: electronic
    form: electronic resource
    reformatting quality: access
    form: remote
    extent: VIII, 236 p. online resource.
  abstract: 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.
  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.
  note: edited by Jose Rolim.
  subject:
    topic: Computers
  subject:
    topic: Algorithms
  subject:
    topic: Computer science-Mathematics
  subject:
    topic: Calculus of variations
  subject:
    topic: Combinatorics
  subject:
    topic: Mathematical statistics
  subject:
    topic: Theory of Computation
  subject:
    topic: Algorithm Analysis and Problem Complexity
  subject:
    topic: Discrete Mathematics in Computer Science
  subject:
    topic: Calculus of Variations and Optimal Control; Optimization
  subject:
    topic: Combinatorics
  subject:
    topic: Probability and Statistics in Computer Science
  classification: QA75.5-76.95
  classification: QA76.63
  classification: 004.0151
  related item:
    title info:
      title: Springer eBooks
  related item:
    title info:
      title: Lecture Notes in Computer Science, 1269
  identifier: 9783540692478
  identifier: https://doi.org/10.1007/3-540-63248-4
  record info:
    record creation date: 121227
    record change date: 20191028091435.0
    record identifier: 978-3-540-69247-8