2 edited tags
| link
    Tweeted twitter.com/#!/StackCompSci/status/352879850190684160
1
source | link

Subset optimization problem

Consider we have a finite set $S$ with $n$ distinct elements. We want to find a subset $\{a_1, a_2, \dotsc, a_k\}\subseteq S$ ($k\ll n$) such that a function $f(a_1,a_2,\dotsc,a_k)$ is maximized. Consider $f$ to be a symmetric function that takes $k$ arguments.


More specifically, we are given $n = 120$ items, each item being associated with three positive numbers $(A_i, B_i,C_i)$, and we want to choose $k=12$ items within this set such that

$$ \frac{\sum_{k=1}^{12} A_{i_k} \times \left\lceil\frac{\sum_{k=1}^{12} B_{i_k}}{10000}\right\rceil}{\sum_{k=1}^{12} C_{i_k}} $$

is maximal.


If we solve it by exhaustive search it requires $\binom{120}{12} \approx 10^{16}$ operations. Is there faster method to this problem? Approximate solution is also fine.