Approximation Algorithms and Hardness of Approximation

	Credits	4
	Lecturers	Ola Svensson (course responsible) and Alantha Newman
	Schedule	Tuesdays at 16:15-18 and Fridays at 10:15-12, always in INM 203

Click here to go back to main page of course.

Project

• The goal of the project is to select a paper of your liking and summarize the main contributions and techniques/ideas in a similar fashion and length as the lecture notes of one lecture.
• Each person will make a presentation on the selected topic in approximation algorithm or hardness of approximation.
• You can choose to present i) approximation algorithm papers on top conference of theoretical computer science (such as STOC/FOCS/SODA/APPROX) ii) one or two advanced sections in one of the text books not covered by a lecture. iii) Other project ideas are also acceptable. Please talk to me about any such ideas you have.

Presentations

• Each presentation (except otherwise noted) should be for 20 minutes. This may seem short but for example FOCS/STOC have presentations of roughly this length.
• Some tips: (i) present main results, (ii) one or two key ideas, and (iii) future directions.
• All the students are expected to attend the project presentation of other students and give feedback.

Schedule of presentations

• 16-18 Tuesday 21 May in INM 203:
  
  
  • "Approximation Resistance from Pairwise Independent Subgroups" presented by Rajai Nasser
  • "Linear time 1/2 approximation for unconstrained submodular maximization" presented by Siddhartha Brahma
  • "LP-based approximation algorithms for capacitated facility location" presented by Carsten Moldenhauer
  • "Fast Approximation of Maximum Flow Via Electrical Flows " presented by Farah Charab



• 10-12 Friday 24 May in INM 203:
  
  
  • "Intrinsic robustness of the price of anarchy" presented by Akos Lukovics
  • "Approximation Algorithms for Submodular Multiway Partition" presented by Marwa El Halabi
  • "A bin packing algorithm related to discrepancy theory" presented by Christos Kalaitzis
  • "A Combinatorial, Primal-Dual approach to Semidenite Programs" presented by Alfonso Cevallos


• 16-18 Tuesday 28 May in INM 203:
  
  
  • "ATSP in log n / log log n" presented by Slobodan Mitrovic
  • "Approximating Graphic TSP by Matchings" presented by Olivier Blanvillain
  • "Meta-heuristic for Randomized Priority Search and the Set Cover Problem" presented by Bogdan Stoica
  • "Santa Claus Schedules Jobs on Unrelated Machines" presented by Chidambaram Annamalai

Biased sample of interesting papers

(This list is based on http://www.cs.purdue.edu/homes/wu510/course/590approx/project.html)

• A Combinatorial, Primal-Dual approach to Semidenite Programs (pdf)
  
• Approximating Graphic TSP by Matchings (pdf)
• Approximating k-Median via Pseudo-Approximation (pdf
  
• A 1.488-approximation algorithm for the uncapacitated facility location problem (pdf)
  
• Poly-logarithmic Approximation for EDP with congestion 2 (pdf)
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization (pdf)
  
• Approximate Clustering without the Approximation (pdf)
  
• Optimal Algorithms and Inapproximability Results for Every CSP (pdf)
  
• Santa Claus Schedules Jobs on Unrelated Machines (pdf)
  
• Approximation Algorithms for Submodular Multiway Partition (pdf)
• Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs (pdf)
  
• An O(log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem (pdf) (Taken by Slobodan)
• Algorithms and Hardness for Subspace Approximation (pdf)
  
• Approximating CSPs with global cardinality constraints using SDP hierarchies (pdf)
  
• Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee (ps)
  
• Approximation Algorithms and Hardness of the k-Route Cut Problem(pdf)
  
• APPROXIMATION ALGORITHMS FOR THE 0-EXTENSION PROBLEM pdf
• Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint (pdf)
  
• A 7/8 Approximation Algorithm for MAX 3SAT (pdf)
  
• Detecting High Log-Densities an O(n1=4) Approximation for Densest k-Subgraph (pdf)
  
• Expander Flows, Geometric Embeddings and Graph Partitioning (pdf)
  
• Max Cut and the Smallest Eigenvalue(pdf)
  
• Maximizing the Spread of Influence through a Social Network(pdf)
  
• A new approach to the Minimum Cut Problem (pdf)
  
• Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas (pdf)
  
• Approximating Maximum Weight Matching in Near-linear Time (pdf) Approximating Matrix p-norms (pdf)
  
• Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering (pdf)
  
• The Multiplicative Weights Update Method: a Meta Algorithm and Applications (pdf)
  
• Improving Christofides' algorithm for the s-t path TSP ( pdf )
• Eight-Fifth Approximation for TSP Paths (pdf)
• Approximating Bin Packing within O(log OPT * log log OPT) bins (pdf) (taken by Christos)
• Steiner Tree Approximation via Iterative Randomized Rounding. (pdf)
• Approximation Resistance from Pairwise Independent Subgroups (pdf)
• Some optimal inapproximability results (ps)
• On the Power of Unique 2-Prover 1-Round Games ( ps)
• Optimal Long Code Test with One Free Bit (pdf)
• Approximation resistant predicates from pairwise independence (pdf)

---