COL870: Project Topics

Projects may be done in groups of at most two students. You are expected to read a few research papers (after discussing with the instructor) on a topic, write a short report, and give an hour long presentation on the topic. Here are a few suggestions for topics and the associated papers. You need not pick the topic from this list. Please feel free to pick your own topic. However, you should discuss with the instructor before deciding the topic and papers.

• Dhiraj: PDF
• Jatin: PDF
• Praneeth: PDF
• Ishaan and Surbhi: PDF
  
• Shubham: PDF
• Tushar: PDF
  
• Sachin: PDF
  
• Madhur: PDF
  
• Nipun: PDF
  
• Guntash: PDF
  
• Akanksha: PDF
  

• Smoothed analysis of the k-means (Lloyd's) Algorithm: [Dhiraj]
• Smoothed Analysis of the k-Means Method: David Arthur, Bodo Menthey, and Heiko Roglin
• Improved smoothed analysis of the k-means method: Bobo Manthey and Heiko Roglin
  
• Rate of convergence of the k-means (lloyd's) Algorithm: [Arunay]
• How fast is the k-means method? Sariel Har-Peled and Bardia Sadri
  
• How slow is the k-means method? David Arthur and Sergei Vassilvitskii
  
• NP-hardness for the k-means/median problem: [Ishaan and Surabhi]
• The hardness of k-means clustering: Sanjoy Dasgupta
• The planar k-means problem is NP-hard: Meena Mahajan, Prajakta Nimbhorkar, Kasturi Varadarajan
• The hardness of k-means clustering in the plane: Andrea Vattani
  
• Approximation algorithms for k-means/median using LP rounding: [Shubham]
• A constant factor approximation algorithm for the k-median problem: Moses Charikar, Sudipto Guha, Eva Tardos, and David B. Shmoys
• A dependent LP-rounding approach for the k-median problem: Moses Charikar and Shi Li
  
• Approximation algorithms for k-means/median using local search
• A local search approximation algorithm for k-means clustering: Tapas Kanungoa, David M. Mountb, Nathan S. Netanyahuc, Christine D. Piatkoe, Ruth Silvermand, Angela Y. Wuf
• Local search heuristics for k-median and facility location problems: Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit
  
• Coreset constructions for k-means/median: [Tushar]
• Coresets for k-means and k-median clustering and their applications: Sariel Har-Peled and Soham Mazumdar
• Smaller coresets for k-means and k-median clustering: Sariel Har-Peled and Akash Kushal
  
• On coresets for k-median and k-means clusteringin metric and Euclidean spaces and their applications: Ke Chen
  
• Streaming algorithms for k-means: [Jatin]
• Clustering data streams: Theory and Practice: Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani, and Liadan O Callaghan
  
• Better streaming algorithms for clustering problems: Moses Charikar, Liadan O Callaghan, and Rina Panigrahy
  
• Hardness of approximation for the k-means problem: [Anup]
• The hardness of approximation for Euclidean k-means: Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop
  
• Faster Algorithms for k-means: [Madhur and Nipun]
• Using the triangle inequality to accelerate k-means: Charles Elkan
  
• Making k-means even faster: Greg Hamerly
  
• The Anchors Hierarchy: Using the triangle Inequality to Survive High Dimensional Data: Andrew W. Moore
  
• An Efficient k-Means Clustering Algorithm: Analysis and Implementation: Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu
  
• Accelerating exact k-means algorithms with geometric reasoning: Dan Pelleg and Andrew Moore
  
• Hardness of the k-center problem: [Sai Praneeth and Guntash]
• Clustering to minimize the maximum intercluster distance: Teofilo F. Gonzalez
  
• Optimal algorithms for approximate clustering: Tomás Feder and Daniel Greene