Set $S=\{e_1,\cdots,e_n\}$ is given. For each element $e_i$, we have weight $w_i>0$ and cost $c_i>0$. The goal is findIng the subset $M$ of size $k$ that maximize the following objective function: $$\sum_{e_i\in M} w_i + \frac{\sum_{e_i\notin M} w_i c_i}{\sum_{e_i\notin M} c_i}$$.

Is the problem NP-hard?

Since the objective function seems weird, it is helpful to explain an application of the objective function.

Suppose we have n items $e_1$ to $e_n$ and there are $c_i$ copies of each object $e_i$ in our inventory. We have some customers and they are interested in these objects in proportion with their weight $w_i$, which means the object with greater $w_i$ is more popular. We have an online sale system and we need to answer our customer's requests correctly. We cannot recognize objects by their shapes (They all look the same!). But we have some classifier to find them. Each classifier can be used for detecting copies of an object. We aim to run k classifier in order to maximize our customer's satisfaction.

P.S: It may be useful to think about the case that $w_i c_i=p$ for all $i\leq n$; however, I'm not sure.[I was wrong about this! It is in P by this assumption]

  • $\begingroup$ The right term is less than or equal to the largest weight of an element not in M. So if you have an element with a large weight it's better to put it in M, rather than letting it go to waste. So M should consist of the elements with the k largest weights. Right? $\endgroup$ – zotachidil Jan 12 '12 at 21:16
  • $\begingroup$ It is not correct, because costs are important as well. Consider following example: $\endgroup$ – Nasooh Jan 12 '12 at 21:28
  • $\begingroup$ w1=50, c1=80 - w2=40, c2= 15 - w3=10, c3=5. For k equal to 1 choosing e2 is more beneficial than e1. $\endgroup$ – Nasooh Jan 12 '12 at 21:37
  • $\begingroup$ You're right. Hmm... $\endgroup$ – zotachidil Jan 12 '12 at 23:14
  • 2
    $\begingroup$ Thank you for trying to explaining the motivation. Unfortunately, the connection between your explanation and the objective function in the question is still totally unclear to me, but I guess I have to be satisfied with the current explanation to keep the question within a reasonable length. $\endgroup$ – Tsuyoshi Ito Jan 13 '12 at 23:30

The answer below observes that a special case of the problem is solvable in polynomial time. This does not fully answer the question in the post, but may give some insight on what might be needed for an NP-hardness proof, and may provoke additional interest in the post...

Observation. The problem in the post has an algorithm that, given any instance where each $c_i$ is an integer, runs in time polynomial in $n$ and $D = \sum_i c_i$.

Proof sketch. Fix any input $(S, w, c, K)$ where $w,c\in\mathbb{R}_+^n$ and (WLOG) $S=\{1,2,\ldots,n\}$. Rephrasing the problem slightly, the goal is to find $M\subseteq S$ of size $K$ maximizing $\frac{\sum_{i\in M} w_i c_i}{\sum_{i\in M} c_i} - \sum_{i\in M} w_i$.

Consider the following dynamic program. For any integers $(d_1, d_2, k, m)$ with $0\le d_1 \le d_2 \le D$, $0\le k \le K$, and $k\le m\le n$, define $$\textstyle\phi(d_1, d_2, k, m) = \max \Big\{ \sum_{i\in M} w_i (c_i / d_1 - 1) ~:~ M \subseteq [m],\, |M| = k, \, \sum_{i\in M} c_i = d_2\Big\}.$$ The desired solution is $\max_d \phi(d, d, K, n)$.

Partitioning the possible solutions for $\phi(d_1, d_2, k, m)$ into those that contain $m$ and those that don't, we get the recurrence $$\textstyle\phi(d_1, d_2, k, m) = \max\begin{cases} \phi(d_1, d_2 - c_m, k-1,m-1) + w_m(c_m/d_1-1) \\ \phi(d_1, d_2, k, m-1). \end{cases}$$ We leave the boundary cases as an exercise.

The number of subproblems is $O(n^2 D^2)$, and for each the right-hand side of the recurrence can be evaluated in constant time, so the algorithm runs in time polynomial in $n$ and $D$. $~~\Box$

Corollary. Unless P=NP, any reduction showing NP-hardness will reduce to instances where $D$ is not polynomial in $n$.

Remark. Unless I am mistaken, there is also a PTAS for the problem in the post, based on rounding the $w_i$'s then using dynamic programming. However, the existence of a PTAS has no direct bearing on whether the problem is NP-hard, as asked in the post.

I am also curious --- does anyone know whether the special case when $w_i=c_i$ (for each $i$) has a poly-time algorithm? (EDIT: it does, per Willard Zhan's comment this seems to be optimized by taking $M$ to contain the $k$ largest elements.)

  • 1
    $\begingroup$ Isn't the case of $w_i=c_i$ the same as minimizing $(\sum_{i\neq j\notin M}w_iw_j)/(\sum_{i\notin M} w_i)$, which is optimized when $M$ consists of the largest $w_i$'s? $\endgroup$ – Willard Zhan Aug 1 '18 at 19:21
  • $\begingroup$ @WillardZhan, yes, that seems right. $\endgroup$ – Neal Young Aug 1 '18 at 20:10

Your are asking about the maximization of a function with no restrictions?

It is really simple. If M is the biggest set, then it is the best solution. No need to calculate anything.

This problem seems similar to the knapsack problem, which is NP by the way.

  • 3
    $\begingroup$ The question says, “the subset M of size k.” $\endgroup$ – Tsuyoshi Ito Jan 18 '12 at 15:58

Your Answer

