Logo image
Back
On the applications of metric trees and metric labeling to hard combinatorial optimization problems
Dissertation   Open access

On the applications of metric trees and metric labeling to hard combinatorial optimization problems

Yusuf Osmanlioglu
Doctor of Philosophy (Ph.D.), Drexel University
May 2016
DOI:
https://doi.org/10.17918/etd-6789
pdf
Osmanlioglu_Yusuf_20165.83 MBDownloadView
PDF Open Access Open Access (License Unspecified)

Abstract

Approximation theory--Data processing Combinatorial optimization Computer Science
Matching of metric distributions is a fundamental problem in computer science having numerous real life applications including computer vision, pattern recognition, and natural language processing. The problem can be reduced to graph matching since arbitrary metrics can be represented using graphs. Exact graph matching is known to be computationally intractable which motivates inexact matching approaches. Although graphs structurally represent metric data without losing information, processing data over graphs is prone to entail performance problems. Specifically, running time of many graph algorithms depend on the number of edges and vertices of the input graph which increases quadratically by the number of nodes on the extreme case of complete graphs. Thus, it is desirable to obtain a sparse representation of the data while preserving the quality of information. A common technique to achieve this is through representing graphs by metric trees which recently became defacto metric structures for embedding problems. In this dissertation, we focus on problems involving data that can be represented by graphs. As a general theme, we concentrate on approximation of graphs by trees for improving the performance of certain algorithms using topological structure of trees. We also focus on the fundamental problem of inexact graph matching, efficient approximation algorithms for the problem and its applications. Specifically, we present an inexact graph matching problem referred to as multilayer matching, which utilizes the structure of hierarchical metric trees. We represent graphs as trees and achieve matching over the trees to improve the performance and accuracy of inexact matching. We also establish a relationship between the well known metric labeling problem and inexact graph matching. We propose efficient approximation algorithms for both multilayer matching and metric labeling using the primal-dual approximation scheme. We provide application of the proposed methods to image matching, pattern recognition, and question answering problems. Finally, we present a novel motion segmentation method utilizing metric trees which provides tracking of objects in a video sequence without a priori knowledge of number of objects in the scene.

Metrics

59 File views/ downloads
33 Record Views

Details

Logo image