TR-2015-05

Algorithmic aspects of covering supermodular functions under matroid constraints

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



Abstract

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 www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2015},
NUMBER = {TR-2015-05}
}


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