The Resource Approximation Algorithms and Semidefinite Programming, by Bernd Gärtner, Jiri Matousek, (electronic resource)

Approximation Algorithms and Semidefinite Programming, by Bernd Gärtner, Jiri Matousek, (electronic resource)

Label
Approximation Algorithms and Semidefinite Programming
Title
Approximation Algorithms and Semidefinite Programming
Statement of responsibility
by Bernd Gärtner, Jiri Matousek
Creator
Contributor
Author
Author
Subject
Language
  • eng
  • 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
http://library.link/vocab/creatorName
Gärtner, Bernd
Dewey number
519.7
http://bibfra.me/vocab/relation/httpidlocgovvocabularyrelatorsaut
  • CscK4PN64rE
  • 7uSK_0dMiwU
Language note
English
LC call number
T57-57.97
Literary form
non fiction
Nature of contents
dictionaries
http://library.link/vocab/relatedWorkOrContributorName
Matousek, Jiri.
http://library.link/vocab/subjectName
  • Mathematics
  • Information theory
  • Computer software
  • Computational complexity
  • Algorithms
  • Mathematical optimization
  • Applications of Mathematics
  • Theory of Computation
  • Algorithm Analysis and Problem Complexity
  • Discrete Mathematics in Computer Science
  • Algorithms
  • Optimization
Label
Approximation Algorithms and Semidefinite Programming, by Bernd Gärtner, Jiri Matousek, (electronic resource)
Instantiates
Publication
Note
Description based upon print version of record
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
cr
Content category
text
Content type code
txt
Contents
Part I (by Bernd Gärtner): 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 Compositive Programming.- Part II (by Jiri Matousek): 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 -- Summary -- References -- Index
Dimensions
unknown
Edition
1st ed. 2012.
Extent
1 online resource (252 p.)
Form of item
online
Isbn
9783642220159
Media category
computer
Media type code
c
Other control number
10.1007/978-3-642-22015-9
Specific material designation
remote
System control number
  • (CKB)3390000000021897
  • (EBL)3070547
  • (SSID)ssj0000609175
  • (PQKBManifestationID)11973902
  • (PQKBTitleCode)TC0000609175
  • (PQKBWorkID)10609401
  • (PQKB)11669835
  • (DE-He213)978-3-642-22015-9
  • (MiAaPQ)EBC3070547
  • (EXLCZ)993390000000021897
Label
Approximation Algorithms and Semidefinite Programming, by Bernd Gärtner, Jiri Matousek, (electronic resource)
Publication
Note
Description based upon print version of record
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
cr
Content category
text
Content type code
txt
Contents
Part I (by Bernd Gärtner): 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 Compositive Programming.- Part II (by Jiri Matousek): 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 -- Summary -- References -- Index
Dimensions
unknown
Edition
1st ed. 2012.
Extent
1 online resource (252 p.)
Form of item
online
Isbn
9783642220159
Media category
computer
Media type code
c
Other control number
10.1007/978-3-642-22015-9
Specific material designation
remote
System control number
  • (CKB)3390000000021897
  • (EBL)3070547
  • (SSID)ssj0000609175
  • (PQKBManifestationID)11973902
  • (PQKBTitleCode)TC0000609175
  • (PQKBWorkID)10609401
  • (PQKB)11669835
  • (DE-He213)978-3-642-22015-9
  • (MiAaPQ)EBC3070547
  • (EXLCZ)993390000000021897

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 ...