1
$\begingroup$

Suppose a sequence of sets $S_1,S_2,...,S_i$ where each set contains sets of elements. That is, each set $S$ contains many sets $a_1,a_2,...,a_{|S|}$. We are given an integer $k$ and we assume that $\forall 1 \leq j \leq i, |S_j|>k$. The goal is to choose at most $k$ sets from each $S$ such that the number of elements covered by the chosen sets is maximized. Formally, the goal can be defined as:

$$argmax_{b_1 \subseteq S_1, |b_1|\leq k,...,b_i \subseteq S_i, |b_i| \leq k} \: |\cup_{a \in X} a|, where \;X= \cup_{j=1}^i b_j$$

One straightfoward approach is to adjust the standard greedy algorithm where we iteratively choose a set $a$ with the maximum marginal gain without breaking the choice constraint (i.e., k). However, I think that this strategy may not produce approximate solution.

Another potential solution to this problem I know is to adopt the continuous greedy method [1]. However, the computational cost is expensive.

Is there any efficient approximate algorithm for this problem with theoretical guarantees? The algorithm I am looking for does not need to have tight bounds but is expected to perform well in practice.

  1. Vondrák, Jan. "Optimal approximation for the submodular welfare problem in the value oracle model." Proceedings of the fortieth annual ACM symposium on Theory of computing. 2008.
Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ This is a special case of submodular function maximization subject to a partition matroid constraint. Greedy (even local greedy) gives a $1/2$-approximation and this is well known. One can get a $(1-1/e)$-approximation but that is computationally more expensive. You can look at the following article by Goundal and Schulz or other papers for details on greedy analysis etc. optimization-online.org/DB_FILE/2007/08/1740.pdf $\endgroup$
    – Chandra Chekuri
    Nov 2 '21 at 4:29
  • $\begingroup$ @ChandraChekuri Thanks for your reply! I have read the paper you suggested. It is very helpful. I still have a question. Now I understand how the local greedy works and the proof. However, I did not find (global) greedy solution with the partition matroid constraint. Could you please point out where the global greedy is applied to solve this problem? I am very curious about the mechanism and proof. $\endgroup$
    – Rise of Kingdom
    Nov 2 '21 at 9:06
  • $\begingroup$ @ChandraChekuri I have made several passes on the proof of local greedy. I think that the proof can be directly applied to the global greedy. Specifically, as for my problem, the global greedy, in each iteration, consider all qualified sets S where we have not pick out $k$ elements and select one element $a$ from those qualified sets with the maximum marginal gain. Please correct me if I am wrong. $\endgroup$
    – Rise of Kingdom
    Nov 2 '21 at 9:36
  • $\begingroup$ Global greedy gives 1/2 for any matroid, not just partition matroid. The fact that local greedy gives 1/2 also for partition matroid is less obvious. $\endgroup$
    – Chandra Chekuri
    Nov 2 '21 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.