Tata Institute of Fundamental Research
Exact and Approximation Algorithms for Weighted Matroid Intersection
STCS Seminar
Speaker:
Chien-Chung Huang (Chalmers University of Technology
Department of Computer Science and Engineering
SE-412 96 Gothenburg
Sweden)
Organiser:
Umang Bhaskar
Date:
Tuesday, 15 Mar 2016, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: We propose new exact and approximation algorithms for the weighted matroid intersection problem. Our exact algorithm is faster than previous algorithms when the largest weight is relatively small. Our approximation algorithm delivers a $(1-\epsilon)$-approximate solution with a running time significantly faster than most known exact algorithms.
The core of our algorithms is a decomposition technique: we decompose an instance of the weighted matroid intersection problem into a set of instances of the unweighted matroid intersection problem. The computational advantage of this approach is that we can make use of fast unweighted matroid intersection algorithms as a black box for designing algorithms. Precisely speaking, we prove that we can solve the weighted matroid intersection problem via solving $W$ instances of the unweighted matroid intersection problem, where $W$ is the largest given weight. Furthermore, we can find a $(1-\epsilon)$-approximate solution via solving $O(\epsilon^{-1} \log r)$ instances of the unweighted matroid intersection problem, where $r$ is the smallest rank of the given two matroids.
Bio: Chien-Chung Huang is currently an assistant professor at Chalmers University of Technology in Sweden. He obtained his Ph.D. at Dartmouth College in 2008, under the supervision of Peter Winkler. He works in the area of algorithm design nd analysis. The major topics that he has worked on include stable matching, machine scheduling, and selfish routing games.
| Speaker: | Chien-Chung Huang (Chalmers University of Technology Department of Computer Science and Engineering SE-412 96 Gothenburg Sweden) |
| Organiser: | Umang Bhaskar |
| Date: | Tuesday, 15 Mar 2016, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: We propose new exact and approximation algorithms for the weighted matroid intersection problem. Our exact algorithm is faster than previous algorithms when the largest weight is relatively small. Our approximation algorithm delivers a $(1-\epsilon)$-approximate solution with a running time significantly faster than most known exact algorithms.
The core of our algorithms is a decomposition technique: we decompose an instance of the weighted matroid intersection problem into a set of instances of the unweighted matroid intersection problem. The computational advantage of this approach is that we can make use of fast unweighted matroid intersection algorithms as a black box for designing algorithms. Precisely speaking, we prove that we can solve the weighted matroid intersection problem via solving $W$ instances of the unweighted matroid intersection problem, where $W$ is the largest given weight. Furthermore, we can find a $(1-\epsilon)$-approximate solution via solving $O(\epsilon^{-1} \log r)$ instances of the unweighted matroid intersection problem, where $r$ is the smallest rank of the given two matroids.
Bio: Chien-Chung Huang is currently an assistant professor at Chalmers University of Technology in Sweden. He obtained his Ph.D. at Dartmouth College in 2008, under the supervision of Peter Winkler. He works in the area of algorithm design nd analysis. The major topics that he has worked on include stable matching, machine scheduling, and selfish routing games.
The core of our algorithms is a decomposition technique: we decompose an instance of the weighted matroid intersection problem into a set of instances of the unweighted matroid intersection problem. The computational advantage of this approach is that we can make use of fast unweighted matroid intersection algorithms as a black box for designing algorithms. Precisely speaking, we prove that we can solve the weighted matroid intersection problem via solving $W$ instances of the unweighted matroid intersection problem, where $W$ is the largest given weight. Furthermore, we can find a $(1-\epsilon)$-approximate solution via solving $O(\epsilon^{-1} \log r)$ instances of the unweighted matroid intersection problem, where $r$ is the smallest rank of the given two matroids.
Bio: Chien-Chung Huang is currently an assistant professor at Chalmers University of Technology in Sweden. He obtained his Ph.D. at Dartmouth College in 2008, under the supervision of Peter Winkler. He works in the area of algorithm design nd analysis. The major topics that he has worked on include stable matching, machine scheduling, and selfish routing games.