This is the home page for my summer REU project. I'm working on Hardness of Approximation for Clustering Objectives . Intuitively, imagine you have a bunch of points and some notion of distance between them. How hard is it to divide these points into groups so that points in the same group are close together?
I am mentored by Karthik C.S and Henry Fleischmann. My project partners are Kyrylo Karlov and Ashwin Padaki. The project is funded by NSF through the DIMACS program.
The first week was spent getting comfortable with the problem and the techniques used to solve the problem. I learned what kind of reductions exist and which hard problems will be useful to show our hardness results.
Random: I am still in school this week, so I've been figuring out how to do both school and research without needing to stay up too late.
We started off this week by slightly improving the hardness bound on the approximation ratio for constant k in L-p metrics for p at least 2. This was done by using a slightly different problem to reduce from. Then, Henry generalized this idea to obtain an even better bound. Though, the gap between when the problem is hard and when it is easy remains large (sqrt(5/4) vs. 2).
Random: This is my last week of school, so I am excited to have even more time next week.
My last final was Tuesday, so I'm finally done with classes. This means I can contribute much more to the project! We got to meet Karthik in person for the first time. We thought of an efficient sqrt(3) ration approximation algorithm for the euclidean metric and constant k. Later in the week, we though of a way to iterate this algorithm to turn the sqrt(3) into a sqrt(2). This is a significant improvement from the previously known 2-approximation algorithm. The gap for L1 still remains huge. Ideally, we want to show that less than 2 approximation is hard in L1 because that would simultaneously close both the L1 and L2 gap.
Random: I'm getting better at imagining 4 dimensional things, which is exciting.
This week we improved L1 hardness to 5/4 (from 1.1), and I thought of an efficient algorithm for constant k and dimension. The main thing we are working on is closing the L1 gap. I thought of a barrier result for L1 which basically shows that all of the known approaches to showing hardness for more than 7/4 here will not work. Ashwin created a linear program that generalizes my proof. We were able to turn the 7/4 into a 5/3 using that. We spent the rest of the week trying to turn this barrier into an algorithm. So far, unsuccessful.
Random: Kyrylo and I made boscht for a potluck and that was fun. I also went to NYC to dance tango, and that was also fun.
We are all stuck on either showing hardness or thinking of an algorithm. We've had 4 days of almost no tangible progress. The only results we have this week are ones that show that our current approaches will not work. On one hand, this is frustrating. On the other, this seems to be most representable of research. We'll see if we think of anything by the end of the week. We also need to start writing our paper soon, so maybe the amount of thought we put into this problem will be diluted by that.
Random: Don't have much to say here this week. I made bagels from scratch and they were tasty. That's about it.
