2026-07-25T21:15:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3862 2024-03-06T10:34:32Z ddc:004 open_access

Density Functions subject to a Co-Matroid Constraint Chakaravarthy, Venkatesan T. Modani, Natwar Natarajan, Sivaramakrishnan R. Roy, Sambuddha Sabharwal, Yogish Approximation Algorithms Submodular Functions Graph Density In this paper we consider the problem of finding the densest subset subject to co-matroid constraints. We are given a monotone supermodular set function f defined over a universe U, and the density of a subset S is defined to be f(S)/|S|. This generalizes the concept of graph density. Co-matroid constraints are the following: given matroid M a set S is feasible, iff the complement of S is 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. Thereby we improve the approximation guarantees for the result for partition matroids in the literature. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Venkatesan T. Chakaravarthy and Natwar Modani and Sivaramakrishnan R. Natarajan and Sambuddha Roy and Yogish Sabharwal 2012 Is Part Of LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2012.236 urn:nbn:de:0030-drops-38627 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.236 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode