72. Problems on Group-labeled Matroid Bases
Invited abstract in session WF-2: Combinatorial Optimization II, stream Discrete Optimization.
Wednesday, 16:45 - 18:15Room: C 103
Authors (first author is the speaker)
| 1. | Tamás Schwarcz
|
| Department of Operations Research, Eötvös Loránd University | |
| 2. | Florian Hörsch
|
| CISPA | |
| 3. | András Imolay
|
| Eötvös Loránd University | |
| 4. | Ryuhei Mizutani
|
| The University of Tokyo | |
| 5. | Taihei Oki
|
| The University of Tokyo |
Abstract
Several combinatorial optimization problems involve additional constraints, such as parity, congruency, and exact-weight constraints. These constraints are subsumed by group-label constraints defined as follows: given a labeling of a ground set to an abelian group and a prescribed set F of forbidden labels, we define a subset of the ground set F-avoiding if the sum of the labels of its elements is not in F. Non-zero and zero problems are particularly important special cases, where F consists of the zero and non-zero labels, respectively.
We study the problems of finding F-avoiding bases and common bases of two matroids. For the single matroid case, finding an F-avoiding basis is hard if F is part of the input, while for a fixed |F|, we show the polynomial solvability of the problem in several cases, including matroids representable over fixed, finite fields. Finding a zero common basis of two matroids is hard for any nontrivial group, while we show that the solvability of finding a non-zero basis depends on the group. Furthermore, if the group is finite, we give a randomized algebraic algorithm for finding an F-avoiding common basis of two matroids represented over the same field, with running time polynomial in |F| and the group size.
Keywords
- Complexity and efficiency of optimization algorithms
Status: accepted
Back to the list of papers