Coverart for item
The Resource Lectures on proof verification and approximation algorithms, Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger (eds.)

Lectures on proof verification and approximation algorithms, Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger (eds.)

Label
Lectures on proof verification and approximation algorithms
Title
Lectures on proof verification and approximation algorithms
Statement of responsibility
Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger (eds.)
Contributor
Subject
Language
eng
Summary
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
Member of
Cataloging source
YNG
Dewey number
005.1/4
Illustrations
illustrations
Index
index present
LC call number
QA76.9.A96
LC item number
L43 1998
Literary form
non fiction
Nature of contents
  • dictionaries
  • bibliography
http://library.link/vocab/relatedWorkOrContributorName
  • Mayr, Ernst
  • Prömel, H. J
  • Steger, Angelika
Series statement
Lecture notes in computer science,
Series volume
1367
http://library.link/vocab/subjectName
  • Automatic theorem proving
  • Computer algorithms
  • Approximation theory
  • Approximation theory
  • Automatic theorem proving
  • Computer algorithms
Target audience
adult
Label
Lectures on proof verification and approximation algorithms, Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger (eds.)
Instantiates
Publication
Antecedent source
unknown
Bibliography note
Includes bibliographical references (pages 325-334) and indexes
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
black and white
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
Introduction to the theory of complexity and approximation algorithms / Thomas Jansen -- Introduction to randomized algorithms / Artur Andrzejak -- Derandomization / Detlef Sieling -- Proof checking and non-approximability / Stefan Hougardy -- Proving the PCP-theorem / Volker Heun, Wolfgang Merkle, Ulrich Weigand -- Parallel repetition of MIP(2,1) systems / Clemens Gröpl, Martin Skutella -- Bounds for approximating MAXLINEQ3-2 and MAXEkSAT / Sebastian Seibert, Thomas Wilke -- Deriving non-approximability results by reductions / Claus Rick, Hein Röhrig -- Optimal non-approximability of MAXCLIQUE / Martin Mundhenk, Anna Slobodová -- The hardness of approximating set cover / Alexander Wolff -- Semidefinite programming and its applications to approximation algorithms / Thomas Hofmeister, Martin Hühne -- Dense instances of hard optimization problems / Katja Wolf -- Polynomial time approximation schemes for geometric optimization problems in Euclidean metric spaces / Richard Mayr, Annette Schelten
Control code
234237955
Dimensions
unknown
Extent
1 online resource (xii, 344 pages)
File format
multiple file formats
Form of item
online
Isbn
9783540697015
Level of compression
unknown
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
10.1007/BFb0053010
Other physical details
illustrations.
Quality assurance targets
unknown
Reformatting quality
access
Specific material designation
remote
System control number
(OCoLC)234237955
Label
Lectures on proof verification and approximation algorithms, Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger (eds.)
Publication
Antecedent source
unknown
Bibliography note
Includes bibliographical references (pages 325-334) and indexes
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
black and white
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
Introduction to the theory of complexity and approximation algorithms / Thomas Jansen -- Introduction to randomized algorithms / Artur Andrzejak -- Derandomization / Detlef Sieling -- Proof checking and non-approximability / Stefan Hougardy -- Proving the PCP-theorem / Volker Heun, Wolfgang Merkle, Ulrich Weigand -- Parallel repetition of MIP(2,1) systems / Clemens Gröpl, Martin Skutella -- Bounds for approximating MAXLINEQ3-2 and MAXEkSAT / Sebastian Seibert, Thomas Wilke -- Deriving non-approximability results by reductions / Claus Rick, Hein Röhrig -- Optimal non-approximability of MAXCLIQUE / Martin Mundhenk, Anna Slobodová -- The hardness of approximating set cover / Alexander Wolff -- Semidefinite programming and its applications to approximation algorithms / Thomas Hofmeister, Martin Hühne -- Dense instances of hard optimization problems / Katja Wolf -- Polynomial time approximation schemes for geometric optimization problems in Euclidean metric spaces / Richard Mayr, Annette Schelten
Control code
234237955
Dimensions
unknown
Extent
1 online resource (xii, 344 pages)
File format
multiple file formats
Form of item
online
Isbn
9783540697015
Level of compression
unknown
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
10.1007/BFb0053010
Other physical details
illustrations.
Quality assurance targets
unknown
Reformatting quality
access
Specific material designation
remote
System control number
(OCoLC)234237955

Library Locations

    • Ellis LibraryBorrow it
      1020 Lowry Street, Columbia, MO, 65201, US
      38.944491 -92.326012
Processing Feedback ...