Publications in top-tier conferences

We are happy to report that our group has seen recent success through papers accepted at two top-tier conferences.

Chien-Chung Huang, Naonori Kakimura and Naoyuki Kamiyama will have their paper Exact and Approximation Algorithms for Weighted Matroid Intersection published in the very competitive SODA 2016.

A few weeks earlier, Fredrik Johansson, Ankani Chattoraj, Devdatt Dubhashi and Chiranjib Bhattacharyya had their paper Weighted Theta Functions and Embeddings with Applications to Max-Cut, Clustering and Summarization accepted for publication at NIPS 2015.

 

Exact and Approximation Algorithms for Weighted Matroid Intersection
Chien-Chung Huang, Naonori Kakimura and Naoyuki Kamiyama

Abstract
We present exact and approximation algorithms for the weighted matroid intersection problems. Our exact algorithms are faster than previous algorithms when the largest weight is relatively small. Our approximation algorithms deliver a (1-∈)-approximate solution with running times significantly faster than known exact algorithms. The core of our algorithms is a decomposition technique: we decompose the weighted version of the problem into a set of unweighted matroid intersection problems. The computational advantage of this approach is that we can then make use of fast unweighted matroid intersection algorithms as a black box for designing algorithms. To be precise, we show that we can find an exact solution via solving W unweighted matroid intersections problems, where W is the largest given weight. Furthermore, we can find a (1-∈)-approximate solution via solving O(∈^{-1} log r) unweighted matroid intersection problems, where r is the smallest rank of the given two matroids.

 

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

Abstract
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.