Approximation algorithms

Vijay-V Vazirani

Note moyenne 
Vijay-V Vazirani - Approximation algorithms.
The field of approximation algorithms, perhaps the most active area of algorithmic research today, combines a rich and deep mathematical theory with the... Lire la suite
74,90 €
Expédié sous 6 à 12 jours
Livré chez vous entre le 4 avril et le 10 avril
En librairie

Résumé

The field of approximation algorithms, perhaps the most active area of algorithmic research today, combines a rich and deep mathematical theory with the promise of profound practical impact. Most computational problems arising across a very broad spectrum of application areas, such as VLSI design, design and operation of networks, web-related problems, scheduling, manufacturing, game theory, biology, and number theory, are NP-hard, hence making their exact solution prohibitively time-consuming. This challenge has motivated the growth of an impressive literature, providing approximation algorithms for this very diverse collection of problems. A slew of spectacular results in the last decade has revolutionized the field. The challenge met by this book is to capture the beauty and excitement of work in this thriving field and to convey in a lucid manner the underlying theory and methodology. Many of the research results presented have been simplified, and new insights provided Perhaps the most important aspect of the book is that it shows simple ways of talking about complex, powerful algorithmic ideas by giving intuitive proofs, by writing algorithms in plain English, and by providing numerous critical examples and illustrations. This book will be of interest to the scientific community at large and, in particular, to students and researchers in Computer Science, Operations Research, and Discrete Mathematics. It can be used both as a text in a graduate course on approximation algorithms and as a supplementary text in basic undergraduate and graduate courses on algorithms.

Sommaire

  • COMBINATORIAL ALGORITHMS
    • Set cover
    • Steiner tree and TSP
    • Multiway cut and k-cut
    • K-center
    • Feedback vertex set
    • Shortest superstring
    • Knapsack
    • Bin packing
    • Minimum makespan scheduling
    • Euclidean TSP
  • LP-BASED ALGORITHMS
    • Introduction to LP-duality
    • Set cover via dual fitting
    • Rounding applied to set cover
    • Set cover via the primal-dual shema
    • Maximum satisfiability
    • Scheduling on unrealated parallel machines
    • Multicut and integer multicommodity flow in trees
    • Multiway cut
    • Multicut in general graphs
    • Sparset cut
    • Steiner forest
    • Steiner network
    • Facility location
    • K-median
    • Semidefinite programming
  • OTHER TOPICS
    • Shortest vector
    • Counting problems
    • Hardness of approximation
    • Open problems.

Caractéristiques

  • Date de parution
    01/01/2001
  • Editeur
  • ISBN
    3-540-65367-8
  • EAN
    9783540653677
  • Présentation
    Relié
  • Nb. de pages
    378 pages
  • Poids
    0.695 Kg
  • Dimensions
    16,3 cm × 24,1 cm × 2,8 cm

Avis libraires et clients

Avis audio

Écoutez ce qu'en disent nos libraires !

À propos de l'auteur

Biographie de Vijay-V Vazirani

Vijay Vazirani got his Bachelors degree in Computer Science from MIT in 1979, and his Ph.D. from U.C. Berkeley in 1983. His research career, which spans over twenty years, has been centred around the design of algorithms, together with work on complexity theory, cryptography, coding theory, and game theory. During the first ten years, he made seminal contributions to the classical maximum matching problem which has historically played a central role in the development of the theory of algorithms. Over the last ten years he has had much influence on the emerging theory of approximation algorithms through work on several of its fundamental problems. Besides his academic duties as Professor of Computer Science at Georgia Tech, he serves on the Board of Directors of Primitive Root, Inc., an Internet security company, of which he is also a co-founder.

Derniers produits consultés

74,90 €