Borrow it
 Architecture Library
 Bizzell Memorial Library
 Boorstin Collection
 Chinese Literature Translation Archive
 Engineering Library
 Fine Arts Library
 Harry W. Bass Business History Collection
 History of Science Collections
 John and Mary Nichols Rare Books and Special Collections
 Library Service Center
 Price College Digital Library
 Western History Collections
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)
Resource Information
The item Approximation Algorithms and Semidefinite Programming, by Bernd Gärtner, Jiri Matousek, (electronic resource) represents a specific, individual, material embodiment of a distinct intellectual or artistic creation found in University of Oklahoma Libraries.This item is available to borrow from all library branches.
Resource Information
The item Approximation Algorithms and Semidefinite Programming, by Bernd Gärtner, Jiri Matousek, (electronic resource) represents a specific, individual, material embodiment of a distinct intellectual or artistic creation found in University of Oklahoma Libraries.
This item is available to borrow from all library branches.
 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 polynomialtime 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
 Language

 eng
 eng
 Edition
 1st ed. 2012.
 Extent
 1 online resource (252 p.)
 Note
 Description based upon print version of record
 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 InteriorPoint Algorithm for Semidefinite Programming
 7 Compositive Programming. Part II (by Jiri Matousek): 8 Lower Bounds for the Goemans–Williamson MAXCUT Algorithm
 9 Coloring 3Chromatic 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
 Isbn
 9783642220159
 Label
 Approximation Algorithms and Semidefinite Programming
 Title
 Approximation Algorithms and Semidefinite Programming
 Statement of responsibility
 by Bernd Gärtner, Jiri Matousek
 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 polynomialtime 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
 T5757.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)
 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 InteriorPoint Algorithm for Semidefinite Programming  7 Compositive Programming. Part II (by Jiri Matousek): 8 Lower Bounds for the Goemans–Williamson MAXCUT Algorithm  9 Coloring 3Chromatic 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/9783642220159
 Specific material designation
 remote
 System control number

 (CKB)3390000000021897
 (EBL)3070547
 (SSID)ssj0000609175
 (PQKBManifestationID)11973902
 (PQKBTitleCode)TC0000609175
 (PQKBWorkID)10609401
 (PQKB)11669835
 (DEHe213)9783642220159
 (MiAaPQ)EBC3070547
 (EXLCZ)993390000000021897
 Label
 Approximation Algorithms and Semidefinite Programming, by Bernd Gärtner, Jiri Matousek, (electronic resource)
 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 InteriorPoint Algorithm for Semidefinite Programming  7 Compositive Programming. Part II (by Jiri Matousek): 8 Lower Bounds for the Goemans–Williamson MAXCUT Algorithm  9 Coloring 3Chromatic 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/9783642220159
 Specific material designation
 remote
 System control number

 (CKB)3390000000021897
 (EBL)3070547
 (SSID)ssj0000609175
 (PQKBManifestationID)11973902
 (PQKBTitleCode)TC0000609175
 (PQKBWorkID)10609401
 (PQKB)11669835
 (DEHe213)9783642220159
 (MiAaPQ)EBC3070547
 (EXLCZ)993390000000021897
Library Locations

Architecture LibraryBorrow itGould Hall 830 Van Vleet Oval Rm. 105, Norman, OK, 73019, US35.205706 97.445050



Chinese Literature Translation ArchiveBorrow it401 W. Brooks St., RM 414, Norman, OK, 73019, US35.207487 97.447906

Engineering LibraryBorrow itFelgar Hall 865 Asp Avenue, Rm. 222, Norman, OK, 73019, US35.205706 97.445050

Fine Arts LibraryBorrow itCatlett Music Center 500 West Boyd Street, Rm. 20, Norman, OK, 73019, US35.210371 97.448244

Harry W. Bass Business History CollectionBorrow it401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US35.207487 97.447906

History of Science CollectionsBorrow it401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US35.207487 97.447906

John and Mary Nichols Rare Books and Special CollectionsBorrow it401 W. Brooks St., Rm. 509NW, Norman, OK, 73019, US35.207487 97.447906


Price College Digital LibraryBorrow itAdams Hall 102 307 West Brooks St., Norman, OK, 73019, US35.210371 97.448244

Western History CollectionsBorrow itMonnet Hall 630 Parrington Oval, Rm. 300, Norman, OK, 73019, US35.209584 97.445414
Embed (Experimental)
Settings
Select options that apply then copy and paste the RDF/HTML data fragment to include in your application
Embed this data in a secure (HTTPS) page:
Layout options:
Include data citation:
<div class="citation" vocab="http://schema.org/"><i class="fa faexternallinksquare fafw"></i> Data from <span resource="http://link.libraries.ou.edu/portal/ApproximationAlgorithmsandSemidefinite/YOeGVZBMPQ/" typeof="Book http://bibfra.me/vocab/lite/Item"><span property="name http://bibfra.me/vocab/lite/label"><a href="http://link.libraries.ou.edu/portal/ApproximationAlgorithmsandSemidefinite/YOeGVZBMPQ/">Approximation Algorithms and Semidefinite Programming, by Bernd Gärtner, Jiri Matousek, (electronic resource)</a></span>  <span property="potentialAction" typeOf="OrganizeAction"><span property="agent" typeof="LibrarySystem http://library.link/vocab/LibrarySystem" resource="http://link.libraries.ou.edu/"><span property="name http://bibfra.me/vocab/lite/label"><a property="url" href="http://link.libraries.ou.edu/">University of Oklahoma Libraries</a></span></span></span></span></div>
Note: Adjust the width and height settings defined in the RDF/HTML code fragment to best match your requirements
Preview
Cite Data  Experimental
Data Citation of the Item Approximation Algorithms and Semidefinite Programming, by Bernd Gärtner, Jiri Matousek, (electronic resource)
Copy and paste the following RDF/HTML data fragment to cite this resource
<div class="citation" vocab="http://schema.org/"><i class="fa faexternallinksquare fafw"></i> Data from <span resource="http://link.libraries.ou.edu/portal/ApproximationAlgorithmsandSemidefinite/YOeGVZBMPQ/" typeof="Book http://bibfra.me/vocab/lite/Item"><span property="name http://bibfra.me/vocab/lite/label"><a href="http://link.libraries.ou.edu/portal/ApproximationAlgorithmsandSemidefinite/YOeGVZBMPQ/">Approximation Algorithms and Semidefinite Programming, by Bernd Gärtner, Jiri Matousek, (electronic resource)</a></span>  <span property="potentialAction" typeOf="OrganizeAction"><span property="agent" typeof="LibrarySystem http://library.link/vocab/LibrarySystem" resource="http://link.libraries.ou.edu/"><span property="name http://bibfra.me/vocab/lite/label"><a property="url" href="http://link.libraries.ou.edu/">University of Oklahoma Libraries</a></span></span></span></span></div>