Solving Partial Assignment Problems using Random Clique Complexes

Sharma, Charu and Nathani, Deepak and Kaul, Manohar (2019) Solving Partial Assignment Problems using Random Clique Complexes.

Full text not available from this repository. (Request a copy)


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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Article
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 19 Dec 2019 08:10
Last Modified: 19 Dec 2019 08:10
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 7193 Statistics for this ePrint Item