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: Lectures on Proof Verification and Approximation Algorithms
  name:
    name part: Mayr, Ernst W.
    role:
      role term: editor.
    role:
      role term: edt
    role:
      role term: http://id.loc.gov/vocabulary/relators/edt
  name:
    name part: Prömel, Hans Jürgen.
    role:
      role term: editor.
    role:
      role term: edt
    role:
      role term: http://id.loc.gov/vocabulary/relators/edt
  name:
    name part: Steger, Angelika.
    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: 1998
    edition: 1st ed. 1998.
    issuance: monographic
  language:
    language term: eng
  physical description:
    form: electronic
    form: electronic resource
    reformatting quality: access
    form: remote
    extent: XII, 348 p. online resource.
  abstract: During the last few years, we have seen quite spectacular progress in the area of approximation algorithms: for several fundamental optimization problems we now actually know matching upper and lower bounds for their approximability. This textbook-like tutorial is a coherent and essentially self-contained presentation of the enormous recent progress facilitated by the interplay between the theory of probabilistically checkable proofs and aproximation algorithms. The basic concepts, methods, and results are presented in a unified way to provide a smooth introduction for newcomers. These lectures are particularly useful for advanced courses or reading groups on the topic.
  table of contents: to the theory of complexity and approximation algorithms -- to randomized algorithms -- Derandomization -- Proof checking and non-approximability -- Proving the PCP-Theorem -- Parallel repetition of MIP(2,1) systems -- Bounds for approximating MaxLinEq3-2 and MaxEkSat -- Deriving non-approximability results by reductions -- Optimal non-approximability of MaxClique -- The hardness of approximating set cover -- Semidefinite programming and its applications to approximation algorithms -- Dense instances of hard optimization problems -- Polynomial time approximation schemes for geometric optimization problems in euclidean metric spaces.
  note: edited by Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger.
  subject:
    topic: Computers
  subject:
    topic: Algorithms
  subject:
    topic: Computer science-Mathematics
  subject:
    topic: Combinatorics
  subject:
    topic: Calculus of variations
  subject:
    topic: Theory of Computation
  subject:
    topic: Algorithm Analysis and Problem Complexity
  subject:
    topic: Discrete Mathematics in Computer Science
  subject:
    topic: Computation by Abstract Devices
  subject:
    topic: Combinatorics
  subject:
    topic: Calculus of Variations and Optimal Control; Optimization
  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, 1367
  identifier: 9783540697015
  identifier: https://doi.org/10.1007/BFb0053010
  record info:
    record creation date: 121227
    record change date: 20191022082331.0
    record identifier: 978-3-540-69701-5