Solving Partial Assignment Problems using Random Clique Complexes
We present an alternate formulation of the partial assignment problem as matching random clique complexes, that are higher-order analogues of random graphs, designed to provide a set of invariants that better detect higher-order structure. The proposed method creates random clique adjacency matrices for each k-skeleton of the random clique complexes and matches them, taking into account each point as the affine combination of its geometric neighbourhood. We justify our solution theoretically, by analyzing the runtime and storage complexity of our algorithm along with the asymptotic behaviour of the quadratic assignment problem (QAP) that is associated with the underlying random clique adjacency matrices. Experiments on both synthetic and real-world datasets, containing severe occlusions and distortions, provide insight into the accuracy, efficiency, and robustness of our approach. We outperform diverse matching algorithms by a significant margin.
Code (1)
Similar Papers 제목 키워드 기반
Logspace Reducibility From Secret Leakage Planted Clique
The planted clique problem is well-studied in the context of observing, explaining, and predicting interesting computational phenomena associated with statistical problems. When equating computational efficiency with the…
Computational EfficiencyTowards combinatorial clustering: preliminary research survey
The paper describes clustering problems from the combinatorial viewpoint. A brief systemic survey is presented including the following: (i) basic clustering problems (e.g., classification, clustering, sorting, clustering…
ClusteringCombinatorial OptimizationMultiple-choiceSurveyTowards Integrated Glance To Restructuring in Combinatorial Optimization
The paper focuses on a new class of combinatorial problems which consists in restructuring of solutions (as sets/structures) in combinatorial optimization. Two main features of the restructuring process are examined: (i)…
ClusteringCombinatorial OptimizationMultiple-choiceLanding Probabilities of Random Walks for Seed-Set Expansion in Hypergraphs
We describe the first known mean-field study of landing probabilities for random walks on hypergraphs. In particular, we examine clique-expansion and tensor methods and evaluate their mean-field characteristics over a cl…
A Fast Maximum Clique Algorithm Based on Network Decomposition for Large Sparse Networks
Finding maximum cliques in large networks is a challenging combinatorial problem with many real-world applications. We present a fast algorithm to achieve the exact solution for the maximum clique problem in large sparse…