CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Weighted theta functions and embeddings with applications to Max-Cut, clustering and summarization

Fredrik Johansson (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)) ; A. Chattoraj ; C. Bhattacharyya ; Devdatt Dubhashi (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers))
29th Annual Conference on Neural Information Processing Systems, NIPS 2015, Montreal, Canada, 7-12 December (1049-5258). Vol. 2015-January (2015), p. 1018-1026.
[Konferensbidrag, övrigt]

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.

Nyckelord: Correlation clustering, Document summarization, Embeddings, Geometric embedding, Graph embeddings, Semi-definite programming, Theta-function, Weighted graph, Information science



Denna post skapades 2016-06-13. Senast ändrad 2016-06-13.
CPL Pubid: 237641

 

Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)

Ämnesområden

Diskret matematik

Chalmers infrastruktur