Timezone: »

Weighted Theta Functions and Embeddings with Applications to Max-Cut, Clustering and Summarization
Fredrik D Johansson · Ankani Chattoraj · Chiranjib Bhattacharyya · Devdatt Dubhashi

Wed Dec 09 04:00 PM -- 08:59 PM (PST) @ 210 C #59 #None

We introduce a unifying generalization of the Lovász theta function, and the associated geometric embedding, for graphs with weights on both nodes and edges. We show how it can be computed exactly by semidefinite programming, and how to approximate it using SVM computations. We show how the theta function can be interpreted as a measure of diversity in graphs and use this idea, and the graph embedding in algorithms for Max-Cut, correlation clustering and document summarization, all of which are well represented as problems on weighted graphs.

Author Information

Fredrik D Johansson (Chalmers University, Sweden)
Ankani Chattoraj (Chalmers University)
Chiranjib Bhattacharyya (Indian Institute of Science)
Devdatt Dubhashi (Chalmers University, Sweden)

More from the Same Authors