Here is a list of papers that you may choose from to present as part of the course project. You may also choose to present something outside of this list, but in that case you need to write to me. Again, you may work alone or in groups of size at most 2. You need to write a report summarising the main results, ideas in the paper in your own words and give a presentation of 15-20 mins on that paper. Most likely we will have the presentations in the last week of the course. I will ask you about your choice and I will prepare a schedule.
Guidelines: It is perfectly fine to present a simpler or special case of the main result that you can explain easily to others. You don't need present all the ideas in the paper, present the main results and focus on one or two main ideas. For presentation, you need to prepare slides.
Grading of presentations: All of you are expected to be present during these sessions. You may ask questions, preferably at the end of the each presentation. I will share a google form using which each of you will evaluate the presentations of others. I will use my own judgement and your inputs to prepare the final marks for the presentation.
*Once you decide on a paper, let me know, I will mark it taken.
For some of the references, I have also mentioned the relevant sections in the book.
List of papers:
Aggregating inconsistent information: Ranking and clustering by Nir Ailon, Moses Charikar, Alantha Newman (JACM 2008) (ref: http://dimacs.rutgers.edu/~alantha/papers2/aggregating_journal.pdf)
Approximating k-Median via Pseudo-Approximation by Shi Li and Ola Svensson (ref: https://arxiv.org/pdf/1211.0243v1.pdf) (Taken by Diprupa Saha and E.A.Sreeram) [Report]
Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields by J. Kleinberg and E. Tardos (JACM 2002) (ref: https://dl.acm.org/doi/pdf/10.1145/585265.585268) (Taken by Deepak Kumar and Nalin Kumar) [Report]
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular approximation: SICOMP 2015 (https://www.openu.ac.il/personal_sites/moran-feldman/publications/SICOMP2015.pdf)
An Improved Approximation Algorithm for Multiway Cut (JCSS 2000) (Ref: Section 8.2 of WS, https://www.cs.huji.ac.il/~yrabani/Papers/CalinescuKR-JCSS-revised.pdf) (Taken by Saswat Kumar Pati and Shashank Saumya) [Report]
The multiplicative weights update method by Sanjeev Arora, Elad Hazan and Satyen Kale (Ref: https://theoryofcomputing.org/articles/v008a006/v008a006.pdf)
Solving LPs/SDPs using Multiplicative Weights (Refs: http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture17.pdf) (Taken by Aditya Petety and Akshat Agrawal) [Report]
Probabilistic approximation of metric spaces and its algorithmic applications by Yair Bartal (Ref: Sections 8.5 in WS, Paper: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.8507&rep=rep1&type=pdf)
Minimum-cost bounded degree spanning trees (Ref: Section 11.2 of WS, Paper: https://dl.acm.org/doi/pdf/10.1145/2629366) (Taken by Tanmay Panigrahi and Ajay Saipriya Sahoo) [Report]
Euclidean TSP by Sanjeev Arora (Section 10.1 in WS, Paper: https://dl.acm.org/doi/pdf/10.1145/290179.290180) (Taken by Shashank Shekhar and M Raj Abhishek) [Report]
Approximate Graph Coloring by Semidefinite Programming (Refs: WS: Section 6.5, Paper: https://arxiv.org/abs/cs/9812008)
Ellipsoid method for solving linear programs (Refs: http://math.mit.edu/~goemans/18433S15/ellipsoid-notes.pdf) (Taken by Konthalapalli Hradini and Karan) [Report]
Interior Point Methods for solving LP (Ref: http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture21.pdf) (Taken by Dinesh Beniwal and Gautameshwar S) [Report]
PTAS for geometric hitting set problems via local search by Mustafa and Ray (Taken by K Prahlad Narasimhan) [Report]
Linear Programming and Convex Hulls Made Easy by Raimund Seidel (Taken by Aman Upadhyay and Adittya Pal) [Report]
Best response dynamics and Nash Equilibria by Patil Prathmesh Vinod [Report]
Genetic algorithm for Multiple sequence alignment by Vaishali Agarwal [Report]