General Information

---

Project Description

• In the Euclidean k-center problem we are given a set of points in the Euclidean plane and the goal is to partition them into k parts (called clusters) so as to minimize the maximum over all clusters, the radius of the minimum enclosing circle for the clusters. In the Euclidean k-diameter we are given the same input and would like to minimize the maximum diameter over all the clusters. In this project, we try to bridge the gap for both these problems between their polynomial time approximation factor and their NP-hardness inapproximability factor.

Research Log

Week 1 (5/28-5/31)

The program has just begun. We met with Karthik and his PhD student Mursalin for the first time. We discussed some known results and agreed on what to read and (try to) understand until the next meeting.

Week 2 (6/3-6/7)

On Monday we had a meeting with Karthik where he gave us some advice on what to include in the presentation which we had the next day. We solved last week's exercise in a way which did not help us understand the problem better. So we continued working on it from another perspective, and noticed some mistakes in the original proof. On the next meeting with Karthik, we got some more things to think about.
Here is our presentation:

Week 3 (6/10-6/14)

We finished the part of getting familiar with the clustering problem. Karthik introduced us to a new problem, which is the one he actually wants us to work on from now on. This is Clustering with Outliers, where we are given the choice to throw out a fixed portion of the input points. We met with him three times this week, and once with Mursalin. We already got some results, which Karthik helped us outline and it remains to fill in the gaps.

Week 4 (6/17-6/21)

We tried to fill in the gaps in the proofs of the partial results from last week's meeting with Karthik. We got stuck, and some of the ideas stopped making sense. So we tried coming up with some more, and have some simpler but weaker results.

Week 5 (6/24-6/28)

We continued working on fixing the proofs. We took a step back. After a meeting with Karthik, we decided to make a computer program to find an edge embedding for small cycles, which might give some insight on how to proceed, as well as what works and what does not.

Week 6 (7/1-7/5)

Programming, coding, developing. That is the name of the game this week. We found some embeddings for cycles on 4 and 5 vertices in both l_1 and l_2. So now we are trying to generalize them. We have many ideas, and an easily modifiable program.

Week 7 (7/8-7/12)

We continue expoloring different ideas through the code. We figured out that embeddings correspond to positive semi-definite matrices, so we are trying to work backwards: i.e. find the embedding by checking many different matrices. This idea seemed helpful in the beginning, but we have failed to get better results.

Week 8 (7/15-7/19)

This is our last week in the US. We had our final presentation of the program where we got to present our results. On Thrusday we left for Prague.

Week 9 (7/22-7/26)

This week the Prague students together with six of our American colleagues got to attend a series of interesting lectures at Charles University. We are also writing our final report.

Acknowledgements

This work was carried out while the author Jelena Glišić was a participant in the 2024 DIMACS REU program, supported by CoSP, a project funded by European Union’s Horizon 2020 research and innovation programme, grant agreement No. 823748.