• Title of article

    A note on submodular set cover on matroids

  • Author/Authors

    Gargano، نويسنده , , Luisa and Hammar، نويسنده , , Mikael، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2009
  • Pages
    6
  • From page
    5739
  • To page
    5744
  • Abstract
    We consider a problem related to the submodular set cover on polymatroids, when the ground set is the family of independent sets of a matroid. The achievement here is getting a strongly polynomial running time with respect to the ground set of the matroid even though the family of independent sets has exponential size. We also address the optimization problem of the maximization of submodular set functions on the independent sets of a matroid.
  • Keywords
    independent sets , Set Cover , Matroid
  • Journal title
    Discrete Mathematics
  • Serial Year
    2009
  • Journal title
    Discrete Mathematics
  • Record number

    1599112