HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Good resources for understanding semidefinite relaxation for combinatorial problems

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
understandingrelaxationsemidefinitecombinatorialforgoodresourcesproblems

Problem

I am looking for good, complete and understandable resources in the field of semidefinite programming and combinatorial optimization. Especially I have a combinatorial problem which I want to relax as SDP and want to compare the bound achieved with the LP relaxation. SO I need to know how to formulate a comb opt problem as SDP and also how to argue about the bound. Any resources would be appreciated.

Thanks.

Solution

The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys is an excellent handbook on approximation algorithms. It has an entire chapter devoted to the topic of SDPs. As of now you can download the older version directly from their website; however the printed text is pretty affordable.

Context

StackExchange Computer Science Q#59460, answer score: 3

Revisions (0)

No revisions yet.