Информатика и вычислительная техника
  • формат pdf
  • размер 5.17 МБ
  • добавлен 08 декабря 2011 г.
Mayr E.W., Pr?mel H.J., Steger A. (eds.) Lectures on Proof Verification and Approximation Algorithms
Издательство Springer, 1998, -337 pp.

Proof Verification and Approximation Algorithms - Hardly any area in theoretical computer science has been more lively and flourishing during the last few years. Different lines of research which had been developed independently of each other over the years culminated in a new and unexpected characterization of the well-known complexity class NP, based on probabilistically checking certain kinds of proofs. This characterization not only sheds new light on the class NP itself, it also allows proof of non-approximability results for optimization problems which, for a long time, had seemed to be out of reach. This connection, in tu, has motivated scientists to take a new look at approximating NP-hard problems as well - with quite surprising success. And apparently, these exciting developments are far from being finished.
We therefore judged "Proof Verification and Approximation Algorithms" an ideal topic for the first in a new series of research seminars for young scientists, to be held at the Inteational Conference and Research Center for Computer Science at Schloi] Dagstuhl in Germany. This new series of seminars was established by the German Society for Computer Science (Gesellschaft f?r Informatik, GI) with the aim of introducing students and young scientists to important new research areas and results not yet accessible in text books or covered in the literature in a comprehensive way.
When we announced our seminar we encountered considerable interest and received numerous responses. We were able to select 21 qualified doctoral students and postdocs. Each participant then was requested to give a lecture, usually based on several research articles or technical reports, and to submit, in preliminary form and before the workshop began, an exposition of the topic assigned to him/her. The actual workshop then took place April 21-25, 1997 at Schlo? Dagstuhl. All participants were very well prepared and highly motivated. We heard excellent talks and had many interesting and stimulating discussions, in the regular sessions as well as over coffee or some enlightening glass of wine after dinner.
This volume contains revised versions of the papers submitted by the participants. The process of revision involved, among other things, unifying notation, removing overlapping parts, adding missing links, and even combining some of the papers into single chapters. The resulting text should now be a coherent and essentially self-contained presentation of the enormous recent progress facilitated by the interplay between the theory of probabilistically checkable proofs and approximation algorithms. While it is certainly not a textbook in the usual sense, we nevertheless believe that it can be helpful for all those who are just starting out to lea about these subjects, and hopefully even to those looking for a coherent treatment of the subject for teaching purposes.

Introduction to the Theory of Complexity and Approximation
Introduction t o Randomized Algorithms
Derandomization
Proof Checking and Non-Approximability
Proving the PCP-Theorem
. Parallel Repetition o f MIP(2,1) Systems
Bounds for Approximating MaxLinEq3-2 and MaxEkSat
Deriving Non-Approximabillty 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
Читать онлайн
Похожие разделы
Смотрите также

Atallah M.J., Blanton M. (eds.) Algorithms and Theory of Computation Handbook. General Concepts and Techniques

Справочник
  • формат pdf
  • размер 8.46 МБ
  • добавлен 30 января 2012 г.
Издательство Chapman&Hall/CRC Press, 2010, -990 pp. The design and analysis of algorithms and data structures form the foundation of computer science. As current algorithms and data structures are improved and new methods are introduced, it becomes increasingly important to present the latest research and applications to professionals in the field. This series aims to capture new developments and applications in the design and analysis of al...

Atallah M.J., Blanton M. Algorithms and Theory of Computation Handbook: Special Topics and Techniques

  • формат pdf
  • размер 10.74 МБ
  • добавлен 22 августа 2011 г.
Chapman and Hall/CRC, 2009. - 950 pages. Algorithms and Theory of Computation Handbook, Second Edition: Special Topics and Techniques provides an up-to-date compendium of fundamental computer science topics and techniques. It also illustrates how the topics and techniques come together to deliver efficient solutions to important practical problems. Along with updating and revising many of the existing chapters, this second edition contains mo...

Bogdanov A., Trevisan L. Average-Case Complexity

  • формат pdf
  • размер 737.3 КБ
  • добавлен 05 октября 2011 г.
Computing Research Repository, 2008, -81 pp. We survey the average-case complexity of problems in NP. We discuss various notions of good-on-average algorithms, and present completeness results due to Impagliazzo and Levin. Such completeness results establish the fact that if a certain specific (but somewhat artificial) NP problem is easy-on-average with respect to the uniform distribution, then all problems in NP are easy-on-average with respect...

Cormen T.H. Introduction to algorithms

  • формат chm
  • размер 17.81 МБ
  • добавлен 12 июня 2009 г.
This book provides a comprehensive introduction to the modern study of computer algorithms. It presents many algorithms and covers them in considerable depth, yet makes their design and analysis accessible to all levels of readers. We have tried to keep explanations elementary without sacrificing depth of coverage or mathematical rigor.Each chapter presents an algorithm, a design technique, an application area, or a related topic. Algorithms are...

Flum J., Grohe M. Parameterized Complexity Theory

  • формат pdf
  • размер 3.68 МБ
  • добавлен 08 февраля 2012 г.
Издательство Springer, 2006, -494 pp. Parameterized complexity theory provides a framework for a refined analysis of hard algorithmic problems. Classical complexity theory analyzes and classifies problems by the amount of a resource, usually time or space, that is required by algorithms solving them. It was a fundamental idea, going back to the work of Hartmanis and Stearns in the early 1960s, to measure the required amount of the resource as a...

Geddes K., Czapor S., Labahn G. Algorithms for Computer Algebra

  • формат djvu
  • размер 4.69 МБ
  • добавлен 04 января 2011 г.
Kluwer Academic Publishers, 1992. - 585 pages. Algorithms for Computer Algebra is the first comprehensive textbook to be published on the topic of computational symbolic mathematics. The book first develops the foundational material from modern algebra that is required for subsequent topics. It then presents a thorough development of modern computational algorithms for such problems as multivariate polynomial arithmetic and greatest common divis...

Goldreich O. Computational Complexity. A Conceptual Perspective

  • формат pdf
  • размер 3.3 МБ
  • добавлен 31 октября 2011 г.
Издательство Cambridge University Press, 2008, -632 pp. The quest for efficiency is ancient and universal, as time and other resources are always in shortage. Thus, the question of which tasks can be performed efficiently is central to the human experience. A key step toward the systematic study of the aforementioned question is a rigorous definition of the notion of a task and of procedures for solving tasks. These definitions were provided by...

Kannan R., Vempala S. Spectral Algorithms

  • формат pdf
  • размер 566.5 КБ
  • добавлен 07 октября 2011 г.
Из серии Foundations and Trends in Theoretical Computer Science издательства NOWPress, 2009, -110 pp. Spectral methods refer to the use of eigenvalues, eigenvectors, singular values, and singular vectors. They are widely used in Engineering, Applied Mathematics, and Statistics. More recently, spectral methods have found numerous applications in Computer Science to discrete as well as continuous problems. This monograph describes modern applicati...

Van Leeuwen J. (ed.) Handbook of Theoretical Computer Science. Volume A. Algorithms and Complexity

  • формат djvu
  • размер 12.2 МБ
  • добавлен 11 мая 2011 г.
Издательсто Elsiever/MIT Press, 1990, -1010 pp. Всеобъемлющий справочник о различных типах сложности алгоритмов и вычислений Machine Models and Simulations A Catalog of Complexity Classes Machine-Independent Complexity Theory Kolmogorov Complexity and its Applications Data Structures Computational Geometry Algorithmic Motion Planning in Robotics Average-Case Analysis of Algorithms and Data Structures Graph Algorithms Algorithms in Number Theory...

Wegener I. Complexity Theory. Exploring the Limits of Efficient Algorithms

  • формат pdf
  • размер 2.31 МБ
  • добавлен 20 сентября 2011 г.
Издательство Springer, 2005, -306 pp. Complexity theory – is it a discipline for theoreticians who have no concern for the real world or a central topic of modern computer science? In this introductory text, complexity theory is presented as an active area of computer science with results that have implications for the development and use of algorithms. Our study will lead to insights into the structure of important optimization problems and wil...