Approximation Algorithms and Hardness of Approximation

Credits 
4 

Lecturers 
Ola Svensson (course responsible) and Alantha Newman 

Schedule 
Tuesdays at 16:1518 and Fridays at 10:1512, 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
 1618 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
 "LPbased approximation algorithms for capacitated facility location" presented by Carsten Moldenhauer
 "Fast Approximation of Maximum Flow Via Electrical Flows
" presented by Farah Charab
 1012 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, PrimalDual approach to Semidenite Programs" presented by Alfonso Cevallos
 1618 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
 "Metaheuristic 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, PrimalDual approach to Semidenite Programs (pdf)

Approximating Graphic TSP by Matchings (pdf)

Approximating kMedian via PseudoApproximation (pdf
 A 1.488approximation algorithm for the uncapacitated facility
location problem (pdf)

Polylogarithmic 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 kRoute Cut
Problem(pdf)
 APPROXIMATION ALGORITHMS FOR THE 0EXTENSION 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 LogDensities an O(n1=4) Approximation for Densest kSubgraph (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 Nearlinear Time (pdf)
Approximating Matrix pnorms (pdf)
 Turning Big data into tiny data: Constantsize coresets for kmeans, PCA and projective clustering (pdf)

The Multiplicative Weights Update Method: a Meta Algorithm and Applications (pdf)
 Improving Christofides' algorithm for the st path TSP ( pdf )
 EightFifth 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 2Prover 1Round Games ( ps)

Optimal Long Code Test with One Free Bit (pdf)
 Approximation resistant predicates from pairwise independence (pdf)