# How to select a subset from the array $A=\{\frac{S_1}{K_1},\frac{S_2}{K_2},...,\frac{S_n}{K_n}\}$ such taht the subset can meet this requirement?

Given an array $$A=\{\frac{S_1}{K_1},\frac{S_2}{K_2},...,\frac{S_n}{K_n}\}$$ whose any $$S_i$$ and $$K_i$$ are positive floating-point, and an positive floating-point $$R$$, how to select a set of element $$C=\{\frac{S_{p_1}}{K_{p_1}},\frac{S_{p_2}}{K_{p_2}},...,\frac{S_{p_m}}{K_{p_m}}\}$$ such that the absolute value of the difference between $$\frac{\sum_{i=1}^m S_{p_i}}{\sum_{i=1}^m K_{p_i}}$$ and $$R$$ (i.e. $$|\frac{\sum_{i=1}^m S_{p_i}}{\sum_{i=1}^m K_{p_i}}-R|$$)is minimal. The subset $$C$$ has at least one element.
This problem has confused me for many weeks. I can't even prove whether it is an NP or NP-hard problem. Could anyone give me some ideas on how to address it? I really appreciate any help you can provide.

• What's the context where you encountered it? Can you credit the original source?
– D.W.
Nov 15, 2022 at 7:36
• This problem is abstracted from a model we are studying. The model is actually a scheduling decision model for heterogeneous computing. We tried to tackle it for many weeks but got very little progress (probably due to our limited algorithm addressing ability). Nov 15, 2022 at 7:58

The special case where $$K_1=K_2=\cdots=K_n$$ is as hard as the subset-sum problem, which is NP-hard -- so your problem is NP-hard as well.

A plausible approach is to use integer linear programming. Let $$x_i$$ be a zero-or-one integer variable. You are looking for $$x_i$$ such that

$$-\epsilon \sum_i x_i K_i \le \sum_i x_i S_i - R \sum_i x_i K_i \le \epsilon \sum_i x_i K_i.$$

For fixed $$\epsilon$$, you can test whether there is a solution to this linear inequality using an ILP solver. Then, you can use binary search on $$\epsilon$$ to find the smallest $$\epsilon$$ for which a solution exists.