The matroid intersection cover problem
| Autor: | Kirk Pruhs, Sungjin Im, Benjamin Moseley |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Computer Science::Computer Science and Game Theory
0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research 01 natural sciences Matroid Industrial and Manufacturing Engineering Combinatorics 010104 statistics & probability Computer Science::Discrete Mathematics Partition (number theory) 0101 mathematics Special case Computer Science::Data Structures and Algorithms Mathematics Mathematics::Combinatorics 021103 operations research Matroid intersection Applied Mathematics Combinatorial optimization problem TheoryofComputation_GENERAL Approximation algorithm Set cover problem Standard type Software MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Operations Research Letters. 49:17-22 |
| ISSN: | 0167-6377 |
| Popis: | We consider the matroid intersection cover problem. This is a special case of set cover where the sets are derived from the intersection of matroids. We introduce a technique for computing matroid intersection covers. We give polynomial-time algorithms to compute partition decompositions for matroids that commonly arise in combinatorial optimization problems. We then give a polynomial-time algorithm for computing matroid intersection covers given the partition decompositions of the matroids. Combining these algorithms, we obtain an O ( 1 ) -approximation algorithm when each of the O ( 1 ) matroids is of a standard type. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect