2012/07/22 by Venkatesan T. Chakaravarthy, Natwar Modani, Chakaravarthy, Venkatesan T. +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #Limits and Structures in Graph Theory #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1207.5215
openalex publication_date 2012/07/22 · arxiv created 2012/07/30 · arxiv updated 2012/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we consider the problem of finding the \em densest subset subject to \em co-matroid constraints. We are given a \em monotone supermodular set function f defined over a universe U, and the density of a subset S is defined to be f(S)/\crdS. This generalizes the concept of graph density. Co-matroid constraints are the following: given matroid \calM a set S is feasible, iff the complement of S is \em independent in the matroid. Under such constraints, the problem becomes \np-hard. The specific case of graph density has been considered in literature under specific co-matroid constraints, for example, the cardinality matroid and the partition matroid. We show a 2-approximation for finding the densest subset subject to co-matroid constraints. Thus, for instance, we improve the approximation guarantees for the result for partition matroids in the literature.