I am considering automating testing of down-stream testing of packages that depend on other packages. There are test sets $T_1,\ ..., T_n$ which can be tested or not tested, which each have a time cost $c_1, ... , c_n$ and might invoke a certain functionality $f_1,\ ... , f_m$ which each have an weight $w$.

Let $T \in \{0,1\}^n$ be selection of tests. A set of tests either does or doesn't test a certain functionality $f_j$, testing it twice gives no benefit. I want to maximize $w^Tf$ subject to $c^T T < \text{max cost}$ . $f$ is equal to the logical OR of all $T_i$ which test $f$.

This problem is similar to knapsack but is not knapsack, because binary values mean we put multiple things in the bag together (one test set tests multiple functionalities) and adding things twice gives no benefit.

Are you you aware of a name for this problem class and whether there are alternative formulations or specialized algorithms (like there are for knapsack) for it ?

I am aware of ILP, pseudo boolean or maxsat forumlations.


1 Answer 1


This is called the budgeted maximum coverage problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.