Back to Search
Start Over
ROBUST MATCHINGS AND MATROID INTERSECTIONS.
- Source :
-
SIAM Journal on Discrete Mathematics . 2013, Vol. 27 Issue 3, p1234-1256. 23p. - Publication Year :
- 2013
-
Abstract
- In a weighted independence system, an independent set is said to be α-robust if, for all p, the total weight of its heaviest p elements is at least α times the maximum weight of a p-independent set. Here a p-independent set is an independent set with at most p elements. The set of matchings in a weighted graph is a typical example of a weighted independence system, and Hassin and Rubinstein [SIAM J. Discrete Math., 15 (2002), pp. 530-537] showed that every graph has a 1/√2-robust matching and it can be found by a kth power algorithm in polynomial time. In this paper, we show that it can be extended to the matroid intersection problem; i.e., there always exists a 1/√2-robust matroid intersection, which is polynomially computable. We also study the time complexity of the robust matching problem. We show that a 1-robust matching can be computed in polynomial time (if one exists), and, for any fixed number α with 1/√2 < α < 1, the problem to determine whether a given weighted graph has an a-robust matching is NP-complete. These together with the positive result for α = 1/√2 in [R. Hassin and S. Rubinstein, SIAM J. Discrete Math., 15 (2002), pp. 530-537] give us a sharp border for the complexity for the robust matching problem. Moreover, we show that the problem is strongly NP-complete when a is α part of the input. Finally, we show the limitations of the kth power algorithm for robust matchings; i.e., for any ε > 0, there exists a weighted graph such that no kth power algorithm outputs a (1/√2 + ε)-approximation for computing the most robust matching. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 27
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 93430022
- Full Text :
- https://doi.org/10.1137/100808800