General Information
| Student: | Jelena Glišić |
|---|---|
| Office: | CoRE 446 |
| School: | Faculty of Mathematics and Physics, Charles University |
| 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 Todor Antić, Ben Benčík, Adam Džavoronok, Guillermo Gamboa, Robert Jaworski, Tymur Kotkov, Sofiia Kotsiubynska, Júlia Križanová, Volodymyr Kuznietsov, Tymofii Reizin, Jakub Šošovička, Filip Úradník, 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)
-
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.
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.