General Information
| Student: | Guillermo Gamboa Quintero |
|---|---|
| Office: | CoRE 417 |
| School: | Faculty of Mathematics and Physics, Charles University |
| Contact: | guillermo.gamboa@rutgers.edu |
| 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 that includes Todor Antic, Ben Bencik, Adam Dzavoronok, Jelena Glisic, Robert Jaworski, Tymur Kotkov, Sofiia Kotsiubynska, Julia Krizanova, Volodymyr Kuznietsov, Tymofii Reizin, Jakub Sosovicka, Filip Uradnik and Patrik Zavoral.
Project Description
Research Log
Week 1 (5/28-5/31)
-
We arrived to Rutgers after a long trip from Prague. I started my work by getting familiar with the notions, terminology and main results involving our topic of research, as well as preparing a presentation introducing the project to the whole REU2024 group. I also met with my supervisor as well as the other member of my research group to establish a work plan and determine which notions from the literature are the most important ones for us to focus on and understand.
Week 2 (6/3-6/7)
-
We spent the first hald of the week solving an exercise that our mentor assigned us in order to better understand clustering problems. At the moment of presenting our solution to our mentor, we found out that we ended up solving the exercise in a wrong way. We spent the second half of the week correcting the exercise.
Week 3 (6/10-6/14)
-
Our mentor introduced us to a new problem, which is the we will be working on until the end of the program. The problem is the following: given a finite metric space (X,d) and a>0, what is the optimal diameter of a 1-cluster of X with a|X| outliers. We have some basic results that our mentor is helping us to write down and put together.
Week 4 (6/17 - 6/21)
-
During this week, we worked on the 1-clustering with outliers problem, introduced to us in the previous week. We established a 4/3 inapproximability for the Manhattan metric, which translates to (4/3)^0.5 inapproximability in the Euclidean metric. The main goal now is to get the inapproximability constant as close to 2 as possible, since this would reduce (and possibly close) the gap.
Week 5 (6/24 - 6/28)
-
For this week, our mentor suggested we write a computer program to find a suitable embedding of a graph that gives allows us to prove a 2-inapproximability for 1-clustering with outliers. However, it seems like our embedding only works well for paths of length 3 and 4.
Week 6 (7/1 - 7/5)
-
In this week, we implemented some program to find some embedding for cycles, given a specific criteria that the embeddings should satisfy. For the Manhattan and Euclidean metrics, we found some embeddings for cycles on 4 and 5 vertices. We are now trying to see if these embeddings generalize.
Week 7 (7/8 - 7/12)
-
We continued adjusting the code to our needs for the embedding and found out that the existence of the embeddings corresponding to the existence of certain positive semi-definite matrices, which means that we are now tryng to find the embedding by checking if some matrices are semi-positive deifnite. However, we have not been very successful at this.
Project Summary
References
-
- [1] Henry Fleischmann, Kyrylo Karlov, Karthik C. S., Ashwin Padaki, and Stepan Zharkov. Inapproximability of Maximum Diameter Clustering for Few Clusters. arXiv:2312.02097. 2024.
Acknowledgements
-
This work was carried out while the author G.A. Gamboa Quintero was a participant in the 2024 DIMACS REU program, supported by CoSP, a project funded by European Union Horizon 2020 research and innovation programme, grant agreement No. 823748.