--- start-time: 2021-6-9 14:30:00 participants: ["Andrea Nardi", "Emir Demirovic"] --- # Thesis Meeting 9/6/2021 Minutes Emir asked Andrea how he ended up choosing tree decomposition Andrea gave the following motivations: * Many NP-Hard problem can be simplified by finding its tree decomposition and applying dynamic programming to them. * Many real life problems have small treewidth. * tree decomposition using separators do not only apply to treewidth decomposition but other problems (e.g. minimum fill in, tree length) * Andrea was interested in applying machine learning to combinatorial optimization problems. Andrea was wondering whether he could apply machine learning to the PACE 2016 and PACE 2017 programming competition. Emir asked Andrea whether he was confident in implementing the algorithms? Andrea answers that to implement the algorithms he would need to consult the papers and need to study smaller part of the algorithms (e.g. listing all minimal separators). Emir clarifies the question asking Andrea whether he was confident in programming. Andrea answered that he has been contributing to C++ and Rust repositories the past months. Emir states that a good way to learn and understand the algorithms is to implement them and that Andrea could implement some of the algorithms from other papers. Emir asks Andrea what are his expectation for his thesis. Andrea answers with the following expectations: * That the thesis gets finished * To learn new concepts especially in graph theory and machine learning * Have a thesis that is original. * Have a thesis that is easily accessible. Possibly have open source code or show interactively data regarding the research * Improve writing and Andrea specifies that he is not that good at writing. Emir states that the meetings will be weekly Wednesday at 2:30 of 30 minutes of duration but that the meeting duration can be extended if there is more content per meeting. Emir suggests to Andrea for the next meeting to collect papers of the algorithms of the PACE competition and log them and note some of the papers with roughly what they talk about, pros and cons. Also Emir suggests that if manage to cover of most of the literature to also mix with implementation of the algorithms. Emir suggests that before Andrea starts anything he should read papers on the subjects relevant to his thesis and build on that. Andrea and Emir discuss whether a similar approach can be applied to the PACE clustering problem. They discuss whether the problem can be solved with tree decomposition and dynamic programming or if it can be solved as a triangulation of a graph problem with objective? Emir states that the PACE instances for the clustering competitions are easy to heuristically be solved for optimality and asks whether it is possible to prove its optimality. Andrea answers that at least with tree decomposition, there is the notion of safe separators in treewidth decomposition that are guaranteed to not increase the treewidth but it is not always guaranteed to be found on a graph. Emir informs Andrea about the MMM meetings occurring every Wednesday and suggests Andrea to contact Sofie, the secretary to add me to the email list.