Presentation Project
<br>
<ul>
<li>
You can work in a group of size 2. 
<br>

<li>Each group will  make a presentation on a topic in approximation algorithm..
<br>
<li>You can choose to present i) one or two sections in the text book not covered by the lecture (e.g., any section in part II of [WS], Chap 2.6, 2.7, 4.6,...) ii) approximation algorithm papers on top conference of theoretical computer science(such as STOC/FOCS/SODA/APPROX). iii) your original research on approximation algorithms; iiii)  Other project ideas are also acceptable. Please talk to me  about any such ideas you have.
<br>
<li>All the students are expected to attend the project presentation of other groups and give feedback. 
</ul>
<br>
Below is a biased sample of interesting papers.(This list is under construction)
<ul>
<li>
 A Combinatorial, Primal-Dual approach to Semidenite Programs (<a href = "http://www.cs.princeton.edu/~arora/pubs/mmw.pdf">pdf</a>)
<br>
<li>
Approximating Graphic TSP by Matchings (<a href = "http://arxiv.org/pdf/1104.3090v1.pdf">pdf</a>)
<li>
Approximating k-Median via Pseudo-Approximation (<a href = "http://arxiv.org/pdf/1211.0243v1.pdf">pdf </a>
<br>
<li>A 1.488-approximation algorithm for the uncapacitated facility
location problem (<a href ="http://www.cs.princeton.edu/~shili/papers/fac-ICALP.pdf">pdf</a>)
<br>
<li>
Poly-logarithmic Approximation for EDP with congestion 2 (<a href ="http://arxiv.org/pdf/1208.1272v1.pdf">pdf</a>)
<li>A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization (<a href ="http://www.cs.technion.ac.il/~moranfe/Publications/FOCS2012.pdf">pdf</a>)
<br>
<li>Approximate Clustering without the Approximation (<a href = "http://www.cc.gatech.edu/~ninamf/papers/bbg-clustering-soda.pdf">pdf</a>)
<br>
<li>Optimal Algorithms and Inapproximability Results for Every CSP (<a href = "http://people.csail.mit.edu/dmoshkov/courses/projection/raghavendra.pdf">pdf</a>)
<br>
<li>Santa Claus Schedules Jobs on Unrelated Machines (<a href = "http://arxiv.org/pdf/1011.1168
v2.pdf">pdf</a>)
<br>
<li>Approximation Algorithms for Submodular Multiway Partition (<a href = "http://web.engr.illinois.edu/~ene1/papers/smp-focs.pdf">pdf</a>)
<li>Electrical Flows, Laplacian Systems, and Faster Approximation of
Maximum Flow in Undirected Graphs (<a href = "http://thl.epfl.ch/madry/docs/maxflow.pdf">pdf</a>)<br>

<li>An O(log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem (<a href = "http://thl.epfl.ch/madry/docs/atsp.pdf">pdf</a>)
<li>Algorithms and Hardness for Subspace Approximation (<a href = "http://ttic.uchicago.edu/~madhurt/Papers/subspace-full.pdf">pdf</a>)

<li> Approximating Minimum Bounded Degree Spanning Trees
to within One of Optimal (<a href = "http://research.microsoft.com/en-us/um/people/mohits/publications/mbdst.pdf">pdf</a>)
<br>
<li>Approximating CSPs with global cardinality constraints using SDP hierarchies (<a href ="http://www.cc.gatech.edu/fac/praghave/Files/maxbisectionlasserre.pdf">pdf</a>)
<br>

<li>Simple Linear Time Approximation Algorithm for Betweenness  (<a href="http://ttic.uchicago.edu/~yury/papers/betweenness.pdf">pdf</a>)
<br>
<li>Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee (<a href = "http://www.research.ibm.com/people/s/sviri/papers/bigpapfin.ps">ps</a>)
<br>
<li>Approximation Algorithms and Hardness of the k-Route Cut
Problem(<a href ="http://www.cs.cmu.edu/~yuanzhou/papers/kroute-full.pdf">pdf</a>)
<br>
<li>APPROXIMATION ALGORITHMS FOR THE 0-EXTENSION PROBLEM <a href ="http://www.cs.technion.ac.il/~rabani/Papers/CalinescuKR-SICOMP-revised.pdf">pdf</a>
<li>A geometric apporach to betweeness <a href = "http://people.csail.mit.edu/madhu/papers/1995/chor-journ.pdf">pdf</a>
<br>
<li>Polynomial Time Approximation Schemes for. Euclidean Traveling Salesman and other Geometric. Problems. <a href ="http://dl.acm.org/citation.cfm?id=290180">pdf</a>
<br>
<li>Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint (<a href ="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.2193">pdf</a>)
<br>
<li>A 7/8 Approximation Algorithm for MAX 3SAT  (<a href ="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1351">pdf</a>)
<br>
<li>Detecting High Log-Densities  an O(n1=4) Approximation for Densest k-Subgraph (<a href ="http://www.cs.princeton.edu/~bhaskara/files/dksubgraph.pdf">pdf</a>)
<br>
<li>Expander Flows, Geometric Embeddings and Graph Partitioning (<a href ="http://www.cs.princeton.edu/~arora/pubs/arvfull.pdf">pdf</a>)
<br>
<li>Max Cut and the Smallest Eigenvalue(<a href ="http://arxiv.org/pdf/0806.1978v5.pdf">pdf</a>)
<br>
<li>Maximizing the Spread of Influence through a Social
Network(<a href ="http://www-bcf.usc.edu/~dkempe/publications/spread.pdf">pdf</a>)
<br>
<li>
A new approach to the Minimum Cut Problem (<a href = "http://www.columbia.edu/~cs2035/courses/ieor6614.S09/Contraction.pdf">pdf</a>)
<br>
<li>Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas (<a href ="http://www.cs.berkeley.edu/~gvaliant/papers/corrFOCS.pdf">pdf</a>)
<br>
<li>Approximating Maximum Weight Matching in Near-linear Time (<a href = "http://web.eecs.umich.edu/~pettie/papers/ApproxMWM.pdf">pdf</a>)
Approximating Matrix p-norms (<a href = "http://arxiv.org/pdf/1001.2613v2.pdf">pdf</a>)
<br>
<li>Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering (<a href ="http://people.csail.mit.edu/dannyf/subspace.pdf">pdf</a>)
<br>
<li>
The Multiplicative Weights Update Method: a Meta Algorithm and Applications (<a href ="http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf">pdf</a>)
<br>
</ul>