Coverart for item
The Resource Complexity and Approximation : Combinatorial Optimization Problems and Their Approximability Properties, by Giorgio Ausiello, Alberto Marchetti-Spaccamela, Pierluigi Crescenzi, Giorgio Gambosi, Marco Protasi, Viggo Kann, (electronic resource)

Complexity and Approximation : Combinatorial Optimization Problems and Their Approximability Properties, by Giorgio Ausiello, Alberto Marchetti-Spaccamela, Pierluigi Crescenzi, Giorgio Gambosi, Marco Protasi, Viggo Kann, (electronic resource)

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
by Giorgio Ausiello, Alberto Marchetti-Spaccamela, Pierluigi Crescenzi, Giorgio Gambosi, Marco Protasi, Viggo Kann
Creator
Contributor
Subject
Genre
Language
eng
Summary
This book is an up-to-date documentation of the state of the art in combinatorial optimization, presenting approximate solutions of virtually all relevant classes of NP-hard optimization problems. The well-structured wealth of problems, algorithms, results, and techniques introduced systematically will make the book an indispensable source of reference for professionals. The smooth integration of numerous illustrations, examples, and exercises make this monograph an ideal textbook
Cataloging source
Nz
http://library.link/vocab/creatorDate
1941-
http://library.link/vocab/creatorName
Ausiello, G.
Dewey number
005.1
Illustrations
illustrations
Image bit depth
0
Index
no index present
LC call number
QA76.9.A43
Literary form
non fiction
Nature of contents
dictionaries
http://library.link/vocab/relatedWorkOrContributorName
  • Marchetti-Spaccamela, Alberto
  • Crescenzi, Pierluigi
  • Gambosi, Giorgio
  • Protasi, Marco
  • Kann, Viggo
http://library.link/vocab/subjectName
  • Computer science
  • Computer software
  • Electronic data processing
  • Computational complexity
  • Computer science
  • Management information systems
  • Computational complexity
  • Computer science
  • Computer science
  • Computer software
  • Electronic data processing
  • Management information systems
  • Computational complexity
  • Computer science
  • Computer science_xMathematics
  • Computer software
  • Management information systems
  • Operations research
Label
Complexity and Approximation : Combinatorial Optimization Problems and Their Approximability Properties, by Giorgio Ausiello, Alberto Marchetti-Spaccamela, Pierluigi Crescenzi, Giorgio Gambosi, Marco Protasi, Viggo Kann, (electronic resource)
Link
http://dx.doi.org/10.1007/978-3-642-58412-1
Instantiates
Publication
Antecedent source
mixed
Carrier category
online resource
Carrier category code
cr
Carrier MARC source
rdacarrier
Color
not applicable
Content category
text
Content type code
txt
Content type MARC source
rdacontent
Contents
1 The Complexity of Optimization Problems -- 1.1 Analysis of algorithms and complexity of problems -- 1.2 Complexity classes of decision problems -- 1.3 Reducibility among problems -- 1.4 Complexity of optimization problems -- 1.5 Exercises -- 1.6 Bibliographical notes -- 2 Design Techniques for Approximation Algorithms -- 2.1 The greedy method -- 2.2 Sequential algorithms for partitioning problems -- 2.3 Local search -- 2.4 Linear programming based algorithms -- 2.5 Dynamic programming -- 2.6 Randomized algorithms -- 2.7 Approaches to the approximate solution of problems -- 2.8 Exercises -- 2.9 Bibliographical notes -- 3 Approximation Classes -- 3.1 Approximate solutions with guaranteed performance -- 3.2 Polynomial-time approximation schemes -- 3.3 Fully polynomial-time approximation schemes -- 3.4 Exercises -- 3.5 Bibliographical notes -- 4 Input-Dependent and Asymptotic Approximation -- 4.1 Between APX and NPO -- 4.2 Between APX and PTAS -- 4.3 Exercises -- 4.4 Bibliographical notes -- 5 Approximation through Randomization -- 5.1 Randomized algorithms for weighted vertex cover -- 5.2 Randomized algorithms for weighted satisfiability -- 5.3 Algorithms based on semidefinite programming -- 5.4 The method of the conditional probabilities -- 5.5 Exercises -- 5.6 Bibliographical notes -- 6 NP, PCP and Non-approximability Results -- 6.1 Formal complexity theory -- 6.2 Oracles -- 6.3 The PCP model -- 6.4 Using PCP to prove non-approximability results -- 6.5 Exercises -- 6.6 Bibliographical notes -- 7 The PCP theorem -- 7.1 Transparent long proofs -- 7.2 Almost transparent short proofs -- 7.3 The final proof -- 7.4 Exercises -- 7.5 Bibliographical notes -- 8 Approximation Preserving Reductions -- 8.1 The World of NPO Problems -- 8.2 AP-reducibility -- 8.3 NPO-completeness -- 8.4 APX-completeness -- 8.5 Exercises -- 8.6 Bibliographical notes -- 9 Probabilistic analysis of approximation algorithms -- 9.1 Introduction -- 9.2 Techniques for the probabilistic analysis of algorithms -- 9.3 Probabilistic analysis and multiprocessor scheduling -- 9.4 Probabilistic analysis and bin packing -- 9.5 Probabilistic analysis and maximum clique -- 9.6 Probabilistic analysis and graph coloring -- 9.7 Probabilistic analysis and Euclidean TSP -- 9.8 Exercises -- 9.9 Bibliographical notes -- 10 Heuristic methods -- 10.1 Types of heuristics -- 10.2 Construction heuristics -- 10.3 Local search heuristics -- 10.4 Heuristics based on local search -- 10.5 Exercises -- 10.6 Bibliographical notes -- A Mathematical preliminaries -- A.1 Sets -- A.1.1 Sequences, tuples and matrices -- A.2 Functions and relations -- A.3 Graphs -- A.4 Strings and languages -- A.5 Boolean logic -- A.6 Probability -- A.6.1 Random variables -- A.7 Linear programming -- A.8 Two famous formulas -- B A List of NP Optimization Problems
Dimensions
unknown
Extent
1 online resource (XIX, 524 pages 69 illustrations)
File format
multiple file formats
Form of item
online
Isbn
9783642635816
Isbn Type
(print)
Level of compression
uncompressed
Media category
computer
Media MARC source
rdamedia
Media type code
c
Other control number
10.1007/978-3-642-58412-1
Quality assurance targets
absent
Reformatting quality
access
Specific material designation
remote
System control number
  • (OCoLC)858928709
  • (OCoLC)ocn858928709
Label
Complexity and Approximation : Combinatorial Optimization Problems and Their Approximability Properties, by Giorgio Ausiello, Alberto Marchetti-Spaccamela, Pierluigi Crescenzi, Giorgio Gambosi, Marco Protasi, Viggo Kann, (electronic resource)
Link
http://dx.doi.org/10.1007/978-3-642-58412-1
Publication
Antecedent source
mixed
Carrier category
online resource
Carrier category code
cr
Carrier MARC source
rdacarrier
Color
not applicable
Content category
text
Content type code
txt
Content type MARC source
rdacontent
Contents
1 The Complexity of Optimization Problems -- 1.1 Analysis of algorithms and complexity of problems -- 1.2 Complexity classes of decision problems -- 1.3 Reducibility among problems -- 1.4 Complexity of optimization problems -- 1.5 Exercises -- 1.6 Bibliographical notes -- 2 Design Techniques for Approximation Algorithms -- 2.1 The greedy method -- 2.2 Sequential algorithms for partitioning problems -- 2.3 Local search -- 2.4 Linear programming based algorithms -- 2.5 Dynamic programming -- 2.6 Randomized algorithms -- 2.7 Approaches to the approximate solution of problems -- 2.8 Exercises -- 2.9 Bibliographical notes -- 3 Approximation Classes -- 3.1 Approximate solutions with guaranteed performance -- 3.2 Polynomial-time approximation schemes -- 3.3 Fully polynomial-time approximation schemes -- 3.4 Exercises -- 3.5 Bibliographical notes -- 4 Input-Dependent and Asymptotic Approximation -- 4.1 Between APX and NPO -- 4.2 Between APX and PTAS -- 4.3 Exercises -- 4.4 Bibliographical notes -- 5 Approximation through Randomization -- 5.1 Randomized algorithms for weighted vertex cover -- 5.2 Randomized algorithms for weighted satisfiability -- 5.3 Algorithms based on semidefinite programming -- 5.4 The method of the conditional probabilities -- 5.5 Exercises -- 5.6 Bibliographical notes -- 6 NP, PCP and Non-approximability Results -- 6.1 Formal complexity theory -- 6.2 Oracles -- 6.3 The PCP model -- 6.4 Using PCP to prove non-approximability results -- 6.5 Exercises -- 6.6 Bibliographical notes -- 7 The PCP theorem -- 7.1 Transparent long proofs -- 7.2 Almost transparent short proofs -- 7.3 The final proof -- 7.4 Exercises -- 7.5 Bibliographical notes -- 8 Approximation Preserving Reductions -- 8.1 The World of NPO Problems -- 8.2 AP-reducibility -- 8.3 NPO-completeness -- 8.4 APX-completeness -- 8.5 Exercises -- 8.6 Bibliographical notes -- 9 Probabilistic analysis of approximation algorithms -- 9.1 Introduction -- 9.2 Techniques for the probabilistic analysis of algorithms -- 9.3 Probabilistic analysis and multiprocessor scheduling -- 9.4 Probabilistic analysis and bin packing -- 9.5 Probabilistic analysis and maximum clique -- 9.6 Probabilistic analysis and graph coloring -- 9.7 Probabilistic analysis and Euclidean TSP -- 9.8 Exercises -- 9.9 Bibliographical notes -- 10 Heuristic methods -- 10.1 Types of heuristics -- 10.2 Construction heuristics -- 10.3 Local search heuristics -- 10.4 Heuristics based on local search -- 10.5 Exercises -- 10.6 Bibliographical notes -- A Mathematical preliminaries -- A.1 Sets -- A.1.1 Sequences, tuples and matrices -- A.2 Functions and relations -- A.3 Graphs -- A.4 Strings and languages -- A.5 Boolean logic -- A.6 Probability -- A.6.1 Random variables -- A.7 Linear programming -- A.8 Two famous formulas -- B A List of NP Optimization Problems
Dimensions
unknown
Extent
1 online resource (XIX, 524 pages 69 illustrations)
File format
multiple file formats
Form of item
online
Isbn
9783642635816
Isbn Type
(print)
Level of compression
uncompressed
Media category
computer
Media MARC source
rdamedia
Media type code
c
Other control number
10.1007/978-3-642-58412-1
Quality assurance targets
absent
Reformatting quality
access
Specific material designation
remote
System control number
  • (OCoLC)858928709
  • (OCoLC)ocn858928709

Library Locations

  • Architecture LibraryBorrow it
    Gould Hall 830 Van Vleet Oval Rm. 105, Norman, OK, 73019, US
    35.205706 -97.445050
  • Bizzell Memorial LibraryBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Boorstin CollectionBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Chinese Literature Translation ArchiveBorrow it
    401 W. Brooks St., RM 414, Norman, OK, 73019, US
    35.207487 -97.447906
  • Engineering LibraryBorrow it
    Felgar Hall 865 Asp Avenue, Rm. 222, Norman, OK, 73019, US
    35.205706 -97.445050
  • Fine Arts LibraryBorrow it
    Catlett Music Center 500 West Boyd Street, Rm. 20, Norman, OK, 73019, US
    35.210371 -97.448244
  • Harry W. Bass Business History CollectionBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • History of Science CollectionsBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • John and Mary Nichols Rare Books and Special CollectionsBorrow it
    401 W. Brooks St., Rm. 509NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • Library Service CenterBorrow it
    2601 Technology Place, Norman, OK, 73019, US
    35.185561 -97.398361
  • Price College Digital LibraryBorrow it
    Adams Hall 102 307 West Brooks St., Norman, OK, 73019, US
    35.210371 -97.448244
  • Western History CollectionsBorrow it
    Monnet Hall 630 Parrington Oval, Rm. 300, Norman, OK, 73019, US
    35.209584 -97.445414
Processing Feedback ...