Thesis supervisor: András Frank
Location of studies (in Hungarian): ELTE Institute of Mathematics Abbreviation of location of studies: ELTE
Description of the research topic:
A great advantage of polyhedral methods in
combinatorial optimization is that they help solving minimum cost (or maximum weight) versions of problems where a solution is available for the cardinality case. (See, for example, the maximum cardinality versus the maximum weight matching problem). In the past two decades, however, it turned out that there are difficult graph optimization problems where the cardinality case is nicely tractable while natural weighted versions are already NP-complete, implying that polyhedral methods alone definitely cannot help. (See, for example, the min-max theorem of Watanabe and Nakamura on making a graph $k$-edge-connected by adding a minimum number of new edges).
At the beginning of the present research project, the PhD-student should provide a relatively complete overview of these type of results. The research would then focus on finding further appearences
of the phenomenon. The major goal is to develop new general tools to understand and explain the driving forces behind the concrete results.
Algorithmic aspects are also central in the investigations.
Required language skills: English Number of students who can be accepted: 1
Deadline for application: 2017-05-31
2024. IV. 17. ODT ülés Az ODT következő ülésére 2024. június 14-én, pénteken 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).
Login
