patternMinor
Good resources for understanding semidefinite relaxation for combinatorial problems
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.
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.