| Creator |
|
|
|
|
|
| Language |
|
| Publisher |
|
|
|
| Date |
|
| Source Title |
|
| Vol |
|
| Publication Type |
|
| Access Rights |
|
| Related DOI |
|
| Related URI |
|
| Relation |
|
| 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.show more
|
Export Mendeley
MI2014-12