TR-2008-11

An algorithm for weighted fractional matroid matching

Dion Gijswijt, Gyula Pap



Abstract

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:

@techreport{egres-08-11,
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}
}


Last modification: 15.9.2018. Please email your comments to Tamás Király!