|
Let $M$ be a matroid on ground set $E$. A subset $l\subseteq E$
is called a \emph{line} when $r(l)\in \{1,2\}$. Given a set of lines
$L=\{l_1,\ldots, l_k\}$ in $M$, a vector $x\in \Rplus^L$ is called a
\emph{fractional matching} when $\sum_{l\in L} x_l a(F)_l\leq r(F)$ for every
flat $F$ of $M$. Here $a(F)_l$ is equal to $0$ when $l\cap F=\emptyset$,
equal to $2$ when $l\subseteq F$ and equal to $1$ otherwise. We refer to
$\sum_{l\in L}x_l$ as the \emph{size} of $x$.
It was shown by Chang et al. that a maximum size fractional matching can be found
in polynomial time. In this paper we give an efficient algorithm to find for
given weight function $w:L\to \Q$ a \emph{maximum weight} fractional matching.
Bibtex entry:
| AUTHOR | = | {Gijswijt, Dion and Pap, Gyula}, |
| TITLE | = | {An algorithm for weighted fractional matroid matching}, |
| NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2008}, |
| NUMBER | = | {TR-2008-11} |