A Greedy Approximation for Minimum Cardinality Multiple Quasi-submodular Cover with Applications

Abstract

Quasi-submodularity is a unified measurement to characterize submodularity or approximate submodularity of a set function. In this paper, we consider a variant of Minimum Cardinality Cover named Minimum Cardinality Multiple Quasi-submodular Cover, which requires to find the smallest subset of given ground set such that multiple quasi-submodular functions reach a maximum. We design and analyze a greedy approximation algorithm for Minimum Cardinality Multiple Quasi-submodular Cover. As some applications of our results, we achieve a O(ln n)-approximation algorithm for Minimum Resolving Restrained Dominating Set, and a O(ln delta)-approximation algorithm for Minimum Dominating Set in multiplex networks, where $n$ is the node number and delta is the maximum node degree of the input graph.