5 papers
A Polyhedral Study of Lifted Multicuts
Bjoern Andres, Silvia Di Gregorio, Jannik Irmai +1
Fundamental to many applications in data analysis are the decompositions of a graph, i.e. partitions of the node set into component-inducing subsets. One way of encoding decomposit…
End-to-end Learning for Graph Decomposition
Jie Song, Bjoern Andres, Michael Black +2
We propose a novel end-to-end trainable framework for the graph decomposition problem. The minimum cost multicut problem is first converted to an unconstrained binary cubic formula…
Combinatorial persistency criteria for multicut and max-cut
Jan-Hendrik Lange, Bjoern Andres, Paul Swoboda
In combinatorial optimization, partial variable assignments are called persistent if they agree with some optimal solution. We propose persistency criteria for the multicut and max…
Decomposition of Trees and Paths via Correlation
Jan-Hendrik Lange, Bjoern Andres
We study the problem of decomposing (clustering) a tree with respect to costs attributed to pairs of nodes, so as to minimize the sum of costs for those pairs of nodes that are in…
Convexification of Learning from Constraints
Iaroslav Shcherbatyi, Bjoern Andres
Regularized empirical risk minimization with constrained labels (in contrast to fixed labels) is a remarkably general abstraction of learning. For common loss and regularization fu…