June 3, 2024
Lucas Fabian Naumann Publishes at the International Conference on Machine Learning (ICML)
SECAI scholarship holder Lucas Fabian Naumann, collaborating with Fellow Bjoern Andres and his team, has answered two open questions about high-dimensional geometric objects known as lifted multicut polytopes. Connected to clustering problems in the field of machine learning, his work [1] has been accepted for publication at the International Conference on Machine Learning (ICML), a top outlet for machine learning research. The acceptance note recognizes the technical difficulty of one of Fabian's proofs and concludes that his work, while purely theoretical, may lead to improvements in algorithms.
Essentially, the publication is about analyzing the structure of feasible solutions of the lifted multicut problem, a combinatorial optimization problem whose feasible solutions relate one-to-one to the decompositions of a graph by indicating which edges to cut. This problem has a wide range of applications in computer vision, such as multiple object tracking. In particular, it is of interest to find graph-theoretic characterizations of facets, which are subsets of feasible solutions fulfilling certain properties, as these allow branch-and-cut algorithms that solve the problem exactly to be accelerated. In the past, many classes of facets have been characterized. This paper deals with two of them for which no such characterization could be found previously: the so-called lower box and cut facets.
„While finding such an efficiently decidable characterization for lower box facets was comparatively easy, the cut facets proved to be more challenging. After struggling to find such a characterization for a while and lots of frustration from my side, we realized that while we cannot give a characterization yet, our knowledge of the structure is sufficient to prove that any such characterization must be NP-hard to decide,” says Fabian. While not originally intended, this result is more impactful, as the structure responsible for the NP-hardness of characterizing cut facets exists when decomposing a graph by cutting its edges, as in the lifted multicut problem, but not when decomposing it by removing vertices. Thus, a shift of research to combinatorial optimization problems for graph decomposition based on vertex removal is expected.
Although Fabian was working on the paper before and received support from SECAI Fellow Bjoern Andres and his team, the SECAI scholarship allowed him to fully concentrate on the research. “Without it, the paper would probably not have been completed in time”, he emphasized.
