neural information processing systems · 2018 · 29 citations · 28 references
Natural SciencesComputer ScienceMathematicsAlgorithmsDiscrete MathematicsOptimizationApproximation AlgorithmsAssignment ProblemsCombinatorial OptimizationGraph AlgorithmsMatching TheoryQuadratic ProgrammingGraph MatchingMatching AlgorithmsMatching ProblemsOptimality ConditionsOptimality Criteria
Graph matching has received persistent attention over decades, which can be formulated as a quadratic assignment problem (QAP). We show that a large family of functions, which we define as Separable Functions, can approximate discrete graph matching in the continuous domain asymptotically by varying the approximation controlling parameters. We also study the properties of global optimality and devise convex/concave-preserving extensions to the widely used Lawler's QAP form. Our theoretical findings show the potential for deriving new algorithms and techniques for graph matching. We deliver solvers based on two specific instances of Separable Functions, and the state-of-the-art performance of our method is verified on popular benchmarks.
28
Object recognition from local scale-invariant features
David Lowe · 1999 · 16.2K citations
The Hungarian method for the assignment problem
Harold W. Kuhn · Naval Research Logistics Quarterly · 1955 · 12.6K citations
Robust wide-baseline stereo from maximally stable extremal regions
Jiřı́ Matas, Ondřej Chum, M. Urban et al. · Image and Vision Computing · 2004 · 3.7K citations