Learn to optimize from structured samples for minimum partial set cover
Weizhi Hong, Yingli Ran, Zhao Zhang · Discrete Mathematics Algorithms and Applications · 2025
This paper presents a learning algorithm to solve the Minimum Partial Set cover (MinPSC) problem from structured samples. Given a ground set [Formula: see text] with [Formula: see text] elements, a collection [Formula: see text] of subsets of [Formula: see text] and an integer [Formula: see text], the goal of MinPSC is to find a sub-collection of [Formula: see text] with the minimum size that covers at least [Formula: see text] elements of [Formula: see text]. Without knowing [Formula: see text], one has to find out a solution based on some sampled subcollections of [Formula: see text]. We present a bicriteria algorithm with approximation ratio at most [Formula: see text], whose output covers at least [Formula: see text] elements with probability at least [Formula: see text], and the sample complexity is [Formula: see text], where [Formula: see text] is a constant related to the size of the samples, [Formula: see text] is the approximation ratio for the classic MinPSC problem, [Formula: see text] and [Formula: see text] are constants and [Formula: see text], [Formula: see text] is the size of an optimal solution and [Formula: see text] is a constant. Furthermore, when the subcollections are sampled from a uniform distribution, we design an algorithm whose output covers at least [Formula: see text] elements with probability at least [Formula: see text], where [Formula: see text] is a constant, the approximation ratio is at most [Formula: see text] and the sample complexity is [Formula: see text].