Combinatorial Graph Optimization: Theory, Algorithm and its Application in Pattern Analysis
Mar 14, 2014Author：
Many important problems in pattern analysis are inherently NP-hard combinatorial graph optimization problems, such as graph matching and energy minimization. The relaxation (continuous) method is currently one of the major approaches to solve such problems and has attracted much attention in recent years. By introducing both the convex and concave relaxations of the problem, recently we have summarized and proposed the convex-concave relaxation procedure (CCRP). The CCRP has been proved to be strictly equivalent to the original discrete problem; by contrast, such a merit does not hold for the conventional relaxation approaches. However, the CCRP involves explicitly both convex and concave relaxations, which are typically difficult to find and thus greatly hinder its practical applications. Consequently, we have also proposed the simplified CCRP (SCCRP), which realizes exactly a type of CCRP but its concave relaxation can be realized in an inexplicit way. In the project we are to further investigate how to construct the convex relaxation also in an inexplicit way, so that the CCRP can be realized without involving the convex or concave relaxation explicitly; this actually implies a general algorithmic framework for different combinatorial graph optimizations. The new strategy provides not only a general way to construct state-of-the-art algorithms for different combinatorial optimization problems, but also a unified viewpoint to analyze them, which traditionally seem to have little relationship between each other. Though this project will focus on two typical combinatorial graph optimization problems in pattern analysis, graph matching and energy minimization, the idea can be generalized to other combinatorial optimization problems effortlessly, such as clustering, which inherently belongs also to combinatorial optimization.