TR-2015-05

Algorithmic aspects of covering supermodular functions under matroid constraints

Kristóf Bérczi, Tamás Király, Yusuke Kobayashi

Published in:
SIAM Journal on Discrete Mathematics 30 (2016), 1758-1774. DOI link

A common generalization of earlier results on arborescence packing and the covering of intersecting bi-set families was presented by the authors in Bérczi et al. (2013). The present paper investigates the algorithmic aspects of that result and gives a polynomial-time algorithm for the corresponding optimization problem.

Bibtex entry:

@techreport{egres-15-05,

AUTHOR	=	{B{\'e}rczi, Krist{\'o}f and Kir{\'a}ly, Tam{\'a}s and Kobayashi, Yusuke},
TITLE	=	{Algorithmic aspects of covering supermodular functions under matroid constraints},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2015},
NUMBER	=	{TR-2015-05}

}