In this paper we introduce the selective maximum coverage and the selective maximum set packing problem and variants of them. Both problems are strongly related to well studied problems such as maximum coverage, set packing, and (bipartite) hypergraph matching. The two problems are given by a collection of subsets of a ground set and index subsets of the indices of these subsets. Additionally, there are weights either for each element of the ground set or each subset for each index subset. The goal is to find at most one index per index subset such that the total weight of covered elements or of disjoint subsets is maximum. Applications arise in transportation, e.g., dispatching for ride-sharing services. We prove strong intractability results for the problems and provide almost best possible approximation guarantees.
Citation
@techreport{repORt:2020-62, author = {F.J.L. Willamowski and Bj\"{o}rn Tauer}, title = {Selective Maximum Coverage and Set Packing}, institution = {Lehrstuhl f\"{u}r Operations Research, RWTH Aachen University}, year = {2020}, type = {repORt}, number = {2020--62}, month = {June}}