0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What's the context where you encountered it? Can you credit the original source? $\endgroup$
    – D.W.
    Nov 15, 2022 at 7:36
  • $\begingroup$ 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). $\endgroup$
    – Virux
    Nov 15, 2022 at 7:58

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

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.