Using 3SAT to prove Knapsack, Clique's hardness

http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fivese4.html#Q1-60004-22

Semidefinite Programming

This semester, I have a chance to study carefully SDP. Here are some useful materials from Ngo and Rudra seminar I am taking. If you want to discuss any of these, let me know.

• Laci Lovasz, Semidefinite optimization, 1995-2001. [ ps ]
• L. Vandenberghe and S. Boyd, Semidefinite Programming, SIAM Review, 38(1): 49-95, March 1996. [ pdf ]
• Zwick, Semidefinite Programming Based Approximation Algorithms. [ ppt ]
• Feige, The Use of Semidefinite Programming in Approximation Algorithms. [ ppt ]
• Arora, Semidefinite Programming and Approximation Algorithms for NP-hard Problems: A Survey. ( Slides in pdf )

Optimization books

Here is the good reference for optimization books.

I should read the following books now:
1. Convex Optimization
Stephen Boyd and Lieven Vandenberghe
Lecture slides and videos for this book can be found here.
2. Nonlinear programming
by Dimitri P. Bertsekas

Sublinear Time Algorithms

I am reading "Approximating the minimum spanning tree weight in sublinear time" by Chazelle, Robinfeld, and Trevisan. So far, we try to approximate problems NP. In this paper, I come to know it's very interesting to approximate polynomial time algorithms as data sets are really BIG nowadays. This raises a lot of open problems. Here is a useful page of Ronitt Rubinfeld for a starting point in this area.

Approximation Algorithms

1. Lecture notes on Approximation Algorithms by Chandra Chekuri
http://www.cs.uiuc.edu/homes/chekuri/teaching/fall2006/approx.htm
2. Using primal dual method for Approximation Algorithms, a good survey by David P. Williamson
The primal-dual method for approximation algorithms and its application to network design problems
3. Using Local Ratio method for Approximation Algorithms, a survey by Reuven Bar-Yehuda, Keren Bendel, Ari Freund, and Dror Rawitz
Local ratio: A unified framework for approximation algorithms
4. Some time it seems that whatever way we try, we just can find a approximation. Well, maybe computing good approximation for that problem is also NP-hard. To prove the hardness of approximation, following documents are good starting point:
A survey by Sanjeev Arora, and Carsten Lund
Hardness of approximations
Another one by Luca Trevisan
Inapproximability of Combinatorial Optimization Problems
For approximating minimization problems
On the hardness of approximating minimization problems