Description
EGERVÁRY SZEMINÁRIUM
Absztrakt:
Group-labeled combinatorial optimization problems have been
considered several times before. We focus on the group-labeled
variants for matroidal problems.
Let $\Gamma$ be an abelian group. A group-labeled matroid is a matroid
$M$ whose ground set $E$ is endowed with a group labeling $\psi: E \to
\Gamma$.
The label of a set $X \subseteq E$ is defined as the sum of labels of
the elements in $X$, i.e., $\psi(X) = \sum_{e \in X} \psi(e)$.
Zero and non-zero bases of $M$ are bases whose labels are the zero
element of $\Gamma$ and a non-zero element, respectively.
The most basic problems on group-labeled matroids are the following:
- Zero Base Problem: given a group-labeled matroid, find a zero base
(if it exists).
- Non-Zero Base Problem: given a group-labeled matroid, find a
non-zero base (if it exists).
We also considered several generalizations of these including weighted
cases and common base cases. We are mainly interested in whether the
proposed problems are solvable in polynomial time or not.
This is a joint research project with several co-authors that started
at Emléktábla this year.