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)

We arrived to Rutgers and had our orientations and first meeting with Karthik.

Week 2 (6/3-6/7)

We had two meetings with Karthik this week. On the first, we mostly discussed what to present on the next day, when all students had to make presentations about their projects. You can see our presentation below. On the other, we discussed an exercise which we had solved. We solved in a correct but not very useful way, and we got some more thinks to think about.

Week 3 (6/10-6/14)

This week we started working on a new problem: Clustering with Outliers. The objective is the same, to minimize the max diameter, but we are allowed to throw out a fixed portion of the input points. Together with Karthik and Mursalin, we started reading up on related literature, and already got some results by following old ideas. Karthik helped us write up what we have, and next week we will focus on filling in the details and writing up the proofs.

Week 4 (6/17-6/21)

We started with working on the Overleaf. Some things ended up working out, some did not. We continue to come up with ideas with the help of Mursalin and Karthik.

Week 5 (6/24-6/28)

We continue working on different ideas. Following Karthik's advice, we decided to write a python program to find some embedding for small cycles. We are hoping to get some insight from this.

Week 6 (7/1-7/5)

This week I was away for a conference in Italy. My collegues continued programming, and made a program which can be used to check any embedding for any graph (given that it is small enough) and sees what the ratio is. We plan to use it to test a lot of our ideas.

Week 7 (7/8-7/12)

We kept using the code to check many ideas. We figured out that there is a connection between embeddings and positive semi-definite matrices. So we incorporated this into the code as well and continued testing ideas. No results so far though.

Week 8 (7/15-7/19)

We worked on our final presentation and had our last few meetings with Karthik. When compiled, we realized that we had a decent amount of small results. We presented them to our fellow REU participants. We were happy with how the presentation went and glad to share the results. This is our last week in the US.

Week 9 (7/22-7/26)

We attended four interesting lectures and tutorials in Prague. We had a student workshop on Thursday. We worked on our final reports.

Acknowledgements

This work was carried out while the author Todor Antic 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.