Partial Optimality in Cubic Correlation Clustering
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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Partial Optimality in Cubic Correlation Clustering for General Graphs
The higher-order correlation clustering problem for a graph $G$ and costs associated with cliques of $G$ consists in finding a clustering of $G$ so as to minimize the sum of the costs of those cliques whose nodes all bel…
Partial Optimality and Fast Lower Bounds for Weighted Correlation Clustering
Weighted correlation clustering is hard to solve and hard to approximate for general graphs. Its applications in network analysis and computer vision call for efficient algorithms. To this end, we make three contrib…
ClusteringInverse Optimal Cardano-Lyapunov Feedback for PDEs with Convection
We consider the problem of inverse optimal control design for systems that are not affine in the control. In particular, we consider some classes of partial differential equations (PDEs) with quadratic convection and cou…
Partial Optimality in the Preordering Problem
Preordering is a generalization of clustering and partial ordering with applications in bioinformatics and social network analysis. Given a finite set $V$ and a value $c_{ab} \in \mathbb{R}$ for every ordered pair $ab$ o…
Spotting micro-movements in image sequence by introducing intelligent cubic-LBP
Invisible to naked human eyes, micro-movements are barely noticeable. There are wide ranges of micro-movement applications from spotting subtle changes in a volcano, vascular pulse, and blood vessel to micro-expression d…