Presentation Project
-
You can work in a group of size 2.
- Each group will make a presentation on a topic in approximation algorithm..
- 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.
- All the students are expected to attend the project presentation of other groups and give feedback.
Below is a biased sample of interesting papers.(This list is under construction)
-
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)
- Algorithms and Hardness for Subspace Approximation (pdf)
- Approximating Minimum Bounded Degree Spanning Trees
to within One of Optimal (pdf)
- Approximating CSPs with global cardinality constraints using SDP hierarchies (pdf)
- Simple Linear Time Approximation Algorithm for Betweenness (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
- A geometric apporach to betweeness pdf
- Polynomial Time Approximation Schemes for. Euclidean Traveling Salesman and other Geometric. Problems. 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)