3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.