Abstract:

The higher-order correlation clustering problem is an expressive model, and recently, local search heuristics have been proposed for several applications. Certifying optimality, however, is NP-hard and practically hampered already by the complexity of the problem statement. Here, we focus on establishing partial optimality conditions for the special case of complete graphs and cubic objective functions. In addition, we define and implement algorithms for testing these conditions and examine their effect numerically, on two datasets.

Bio:

Silvia Di Gregorio’s academic background is originally in mathematics: she obtained her B.S. from the University of Parma in 2014 and her M.S. from the University of Padova in 2016. Later in 2020, she received her Ph.D. from the Department of Industrial & Systems Engineering of the University of Wisconsin-Madison, under the supervision of Alberto Del Pia. After that, she moved to TU Dresden, where she works as a postdoctoral researcher with Bjoern Andres at the Chair of Machine Learning for Computer Vision in the Faculty of Computer Science.