Abstract
In this paper, we introduce the concept of DensityBalanced Subset in a matroid, in which independent sets can be sampled so as to guarantee that (i) each element has the same probability to be sampled, and (ii) those events are negatively correlated. These DensityBalanced Subsets are subsets in the ground set of a matroid in which the traditional notion of uniform random sampling can be extended.
We then provide an application of this concept to the MatroidConstrained Maximum Coverage problem. In this problem, given a matroid ℳ = (V, ℐ) of rank k on a ground set V and a coverage function f on V, the goal is to find an independent set S ∈ ℐ maximizing f(S). This problem is an important special case of the muchstudied submodular function maximization problem subject to a matroid constraint; this is also a generalization of the maximum kcover problem in a graph. In this paper, assuming that the coverage function has a bounded frequency μ (i.e., any element of the underlying universe of the coverage function appears in at most μ sets), we design a procedure, parameterized by some integer ρ, to extract in polynomial time an approximate kernel of size ρ ⋅ k that is guaranteed to contain a 1  (μ  1)/ρ approximation of the optimal solution. This procedure can then be used to get a FixedParameter Tractable Approximation Scheme (FPTAS) providing a 1  ε approximation in time (μ/ε)^O(k) ⋅ V^O(1). This generalizes and improves the results of [Manurangsi, 2019] and [Huang and Sellier, 2022], providing the first FPTAS working on an arbitrary matroid. Moreover, as the kernel has a very simple characterization, it can be constructed in the streaming setting.
BibTeX  Entry
@InProceedings{sellier:LIPIcs.ESA.2023.94,
author = {Sellier, Fran\c{c}ois},
title = {{Parameterized MatroidConstrained Maximum Coverage}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {94:194:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772952},
ISSN = {18688969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and FarachColton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18747},
URN = {urn:nbn:de:0030drops187475},
doi = {10.4230/LIPIcs.ESA.2023.94},
annote = {Keywords: Matroids, approximate kernel, maximum coverage}
}
Keywords: 

Matroids, approximate kernel, maximum coverage 
Collection: 

31st Annual European Symposium on Algorithms (ESA 2023) 
Issue Date: 

2023 
Date of publication: 

30.08.2023 