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