General Information
| Student: | Todor Antic |
|---|---|
| Office: | CoRE 446 |
| School: | Faculty of Mathematics and Physics, Charles University |
| Non-REU website: | Personal website |
| Contact: |
|
| Project: | Approximability of Euclidean k-center and k-diameter |
| Mentor: | Karthik C.S. | Project colleagues: |
I am part of a group of students from Charles University which includes Ben Bencik, Adam Dzavoronok, Guillermo Gamboa, Jelena Glisic, Robert Jaworski, Tymur Kotkov, Sofiia Kotsiubynska, Julia Krizanova, Volodymyr Kuznietsov, Tymofii Reizin, Jakub Sosovicka, Filip Uradnik, and Patrik Zavoral.
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.
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.