Coverart for item
The Resource Complexity and approximation : combinatorial optimization problems and their approximability properties, G. Ausiello ... [et al.]

Complexity and approximation : combinatorial optimization problems and their approximability properties, G. Ausiello ... [et al.]

Label
Complexity and approximation : combinatorial optimization problems and their approximability properties
Title
Complexity and approximation
Title remainder
combinatorial optimization problems and their approximability properties
Statement of responsibility
G. Ausiello ... [et al.]
Contributor
Subject
Language
eng
Summary
"In the last ten years the area concerned with the design of approximation algorithms and with the study of the approximability properties of NP-hard combinatorial optimization problems has been one of the most active in computer science, and its scientific developments have considerably enriched our understanding of problem complexity and our ability to cope with difficult applications." "This textbook features a compendium documenting the results on the approximability of more than 200 problems; thus the book is also a source of reference for professionals applying advanced optimization and approximation techniques in practice. The CD-ROM included contains a lot of valuable information, such as lecture slides in various data formats, the compendium in electronic version, and the algorithms visualization toolkit JAZ."--BOOK JACKET
Illustrations
illustrations
Index
index present
Literary form
non fiction
Nature of contents
bibliography
http://library.link/vocab/relatedWorkOrContributorDate
1941-
http://library.link/vocab/relatedWorkOrContributorName
Ausiello, G.
http://library.link/vocab/subjectName
  • Combinatorial optimization
  • Computational complexity
  • Computer algorithms
Label
Complexity and approximation : combinatorial optimization problems and their approximability properties, G. Ausiello ... [et al.]
Instantiates
Publication
Note
  • 1 CD-ROM in pocket at front of book
  • Reprint, with corrections, of edition originally published 1999
Accompanying material
1 computer laser optical disc (4 3/4)
Bibliography note
Includes bibliographical references and index
Contents
  • 1.
  • Complexity of Optimization Problems.
  • p. 1
  • 2.
  • Design Techniques for Approximation Algorithms.
  • p. 39
  • 3.
  • Approximation Classes.
  • p. 87
  • 4.
  • Input-Dependent and Asymptotic Approximation.
  • p. 123
  • 5.
  • Approximation through Randomization.
  • p. 153
  • 6.
  • NP, PCP and Non-approximability Results.
  • p. 175
  • 7.
  • PCP theorem.
  • p. 207
  • 8.
  • Approximation Preserving Reductions.
  • p. 253
  • 9.
  • Probabilistic analysis of approximation algorithms.
  • p. 287
  • 10.
  • Heuristic methods.
  • p. 321
  • A.
  • Mathematical preliminaries.
  • p. 353
  • B.
  • List of NP Optimization Problems.
  • p. 367
  • Bibliography.
  • p. 471
  • Index.
  • p. 515
Control code
l40019864267
Dimensions
25 cm. +
Extent
xix, 524 p.
Isbn
9783540654315
Lccn
lc99040936
Other physical details
ill.
Label
Complexity and approximation : combinatorial optimization problems and their approximability properties, G. Ausiello ... [et al.]
Publication
Note
  • 1 CD-ROM in pocket at front of book
  • Reprint, with corrections, of edition originally published 1999
Accompanying material
1 computer laser optical disc (4 3/4)
Bibliography note
Includes bibliographical references and index
Contents
  • 1.
  • Complexity of Optimization Problems.
  • p. 1
  • 2.
  • Design Techniques for Approximation Algorithms.
  • p. 39
  • 3.
  • Approximation Classes.
  • p. 87
  • 4.
  • Input-Dependent and Asymptotic Approximation.
  • p. 123
  • 5.
  • Approximation through Randomization.
  • p. 153
  • 6.
  • NP, PCP and Non-approximability Results.
  • p. 175
  • 7.
  • PCP theorem.
  • p. 207
  • 8.
  • Approximation Preserving Reductions.
  • p. 253
  • 9.
  • Probabilistic analysis of approximation algorithms.
  • p. 287
  • 10.
  • Heuristic methods.
  • p. 321
  • A.
  • Mathematical preliminaries.
  • p. 353
  • B.
  • List of NP Optimization Problems.
  • p. 367
  • Bibliography.
  • p. 471
  • Index.
  • p. 515
Control code
l40019864267
Dimensions
25 cm. +
Extent
xix, 524 p.
Isbn
9783540654315
Lccn
lc99040936
Other physical details
ill.

Library Locations

    • Harold Cohen LibraryBorrow it
      Ashton Street, Liverpool, L69 3DA, GB
      53.418074 -2.967913
Processing Feedback ...