Coverart for item
The Resource Approximation algorithms and semidefinite programming, Bernd Gärtner, Jiří Matoušek

Approximation algorithms and semidefinite programming, Bernd Gärtner, Jiří Matoušek

Label
Approximation algorithms and semidefinite programming
Title
Approximation algorithms and semidefinite programming
Statement of responsibility
Bernd Gärtner, Jiří Matoušek
Creator
Contributor
Subject
Genre
Language
eng
Summary
Semidefinite programs constitute one of the largest classes of optimization problems that can be solved with reasonable efficiency - both in theory and practice. They play a key role in a variety of research areas, such as combinatorial optimization, approximation algorithms, computational complexity, graph theory, geometry, real algebraic geometry and quantum computing. This book is an introduction to selected aspects of semidefinite programming and its use in approximation algorithms. It covers the basics but also a significant amount of recent and more advanced material. There are many computational problems, such as MAXCUT, for which one cannot reasonably expect to obtain an exact solution efficiently, and in such case, one has to settle for approximate solutions. For MAXCUT and its relatives, exciting recent results suggest that semidefinite programming is probably the ultimate tool. Indeed, assuming the Unique Games Conjecture, a plausible but as yet unproven hypothesis, it was shown that for these problems, known algorithms based on semidefinite programming deliver the best possible approximation ratios among all polynomial-time algorithms. This book follows the "semidefinite side" of these developments, presenting some of the main ideas behind approximation algorithms based on semidefinite programming. It develops the basic theory of semidefinite programming, presents one of the known efficient algorithms in detail, and describes the principles of some others. It also includes applications, focusing on approximation algorithms
Cataloging source
GW5XE
http://library.link/vocab/creatorName
Gärtner, Bernd
Dewey number
518/.1
Illustrations
illustrations
Index
index present
LC call number
QA76.9.A43
LC item number
G37 2012
Literary form
non fiction
Nature of contents
  • dictionaries
  • bibliography
NLM call number
Online Book
http://library.link/vocab/relatedWorkOrContributorDate
1963-
http://library.link/vocab/relatedWorkOrContributorName
Matoušek, Jiří
http://library.link/vocab/subjectName
  • Approximation algorithms
  • Semidefinite programming
  • Algorithms
  • Approximation algorithms
  • Semidefinite programming
Label
Approximation algorithms and semidefinite programming, Bernd Gärtner, Jiří Matoušek
Instantiates
Publication
Antecedent source
unknown
Bibliography note
Includes bibliographical references (pages 239-244) and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
1. Introduction: MaxCut via semidefinite programming -- 2. Semidefinite programming -- 3. Shannon capacity and Lovász Theta -- 4. Duality and cone programming -- 5. Approximately solving semidefinite programs -- 6. An interior-point algorithm for semidefinite programming -- 7. Copositive programming -- 8. Lower bounds for the Goemans-Williamson MaxCut algorithm -- 9. Coloring 3-chromatic graphs -- 10. Maximizing a quadratic form on a graph -- 11. Colorings with low discrepancy -- 12. Constraint satisfaction problems, and relaxing them semidefinitely -- 13. Rounding via miniatures
Control code
773812724
Dimensions
unknown
Extent
1 online resource (xi, 251 pages)
File format
unknown
Form of item
online
Isbn
9783642220159
Level of compression
unknown
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
10.1007/978-3-642-22015-9
Other physical details
illustrations
Quality assurance targets
not applicable
Reformatting quality
unknown
Sound
unknown sound
Specific material designation
remote
System control number
(OCoLC)773812724
Label
Approximation algorithms and semidefinite programming, Bernd Gärtner, Jiří Matoušek
Publication
Antecedent source
unknown
Bibliography note
Includes bibliographical references (pages 239-244) and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
1. Introduction: MaxCut via semidefinite programming -- 2. Semidefinite programming -- 3. Shannon capacity and Lovász Theta -- 4. Duality and cone programming -- 5. Approximately solving semidefinite programs -- 6. An interior-point algorithm for semidefinite programming -- 7. Copositive programming -- 8. Lower bounds for the Goemans-Williamson MaxCut algorithm -- 9. Coloring 3-chromatic graphs -- 10. Maximizing a quadratic form on a graph -- 11. Colorings with low discrepancy -- 12. Constraint satisfaction problems, and relaxing them semidefinitely -- 13. Rounding via miniatures
Control code
773812724
Dimensions
unknown
Extent
1 online resource (xi, 251 pages)
File format
unknown
Form of item
online
Isbn
9783642220159
Level of compression
unknown
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
10.1007/978-3-642-22015-9
Other physical details
illustrations
Quality assurance targets
not applicable
Reformatting quality
unknown
Sound
unknown sound
Specific material designation
remote
System control number
(OCoLC)773812724

Library Locations

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