More about HKUST
Uniform Metric Labeling for Large Graphs
The Hong Kong University of Science and Technology Department of Computer Science and Engineering Final Year Thesis Oral Defense Title: "Uniform Metric Labeling for Large Graphs" by KHAN Irtaza Ahmad Abstract: Uniform metric labeling is an optimisation problem over graphs that has been applied to many real-world applications, including image segmentation and social graph partitioning. The cost minimisation function consists of two parts: the cost of assigning a vertex a label, and the cost of assigning adjacent vertexes different labels. Since uniform metric labeling is NP-hard, previous work has focused on approximation algorithms. Two prominent approaches include linear programming and the game theoretic framework. Linear programming provides quality guarantees on the solution quality, but it is very slow. On the other hand, the game theoretic approach is efficient, but has no quality guarantee. The goal of this project is to explore new methods that provide quality guarantees and, at the same time, they are efficient enough for large graphs. Date : 25 April 2018 (Wednesday) Time : 15:00 - 15:45 Venue : Room 2304 (via lifts 17/18), HKUST Advisor : Prof. PAPADIAS Dimitris 2nd Reader : Dr. YI Ke