(MAX-2-SAT Algorithm)
Solve the vector program. Let be an optimal solution.
Pick r to be a uniformly distributed vector on the unit sphere .
Let be the “true” variables. Algorithm
Analysis Term-by-term analysis. Contribution to semidefinite program: Contribution to the solution: Approximation Ratio: First consider the second term.
Analysis Term-by-term analysis. Contribution to semidefinite program: Contribution to the solution: Approximation Ratio: Consider the first term.
(MAX-2-SAT Algorithm)
Solve the vector program. Let be an optimal solution.
Pick r to be a uniformly distributed vector on the unit sphere .
Let be the “true” variables. Algorithm This is a 0.87856-approximation algorithm for MAX-2-SAT. Can be improved to 0.931!
More SDP in approximation algorithms Sparsest cut: O(√log n)
Constraint satisfaction problems
Correlation clustering
Graph colouring A very powerful tool in the design of approximation algorithms. Useful to know geometry and algebra. Next two lectures: SDP and perfect graphs.
Summary: Topics Classical problem: TSP, Steiner trees
Covering problem: vertex cover, set cover
Packing problem: knapsack, bin packing
Graph partitioning problem: multiway cut, multi-cut
Job scheduling: makespan, general assignment
Network design: Steiner network, degree constrained spanning trees
Constraint satisfaction: maximum cut, max 2-SAT
Summary: Techniques Combinatorial arguments: TSP, Steiner trees, multiway cut
Greedy algorithm and Randomized rounding: set cover
Dynamic programming: knapsack, bin packing
Region Growing: multi-cut
Iterative relaxation: scheduling, network design problems
Primal-dual method: vertex cover, multi-cut in tree
Semidefinite programming: maximum cut, constraint satisfaction
Concluding Remarks Learn to design better heuristics.
e.g. iterative rounding, SDP performs extremely well in practice. Use LP or SDP as a good way to estimate the optimal value.
e.g. help to test the performance of a heuristic. Relax the search space to a convex set.
Remaining Schedule Apr 10-11: NO CLASSES
Apr 17-18: Last week of lecture (perfect graphs, SDP)
Apr 23-24: Project presentation (15 minutes)
May 1: Project report deadline
May 8: Homework 3 deadline
Comments