<p><em>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...</em></p>

<p><strong>Observation.</strong> <em>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$.</em></p>

<p><em>Proof sketch.</em>
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$.</p>

<p>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)$.</p>

<p>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.</p>

<p>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$</p>

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

<p><em>Remark.</em> 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.</p>

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

CC BY-SA 4.0
2018-08-01T19:21:22.640Z
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?
Wei Zhan
CC BY-SA 4.0
2018-08-01T20:10:38.227Z
@WillardZhan, yes, that seems right.
Neal Young
CC BY-SA 4.0
2018-07-31T02:39:42.743Z
2018-08-01T20:12:35.010Z
2018-08-01T20:12:35.010Z
Neal Young
<p>Your are asking about the maximization of a function with no restrictions?</p>

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

<p>This problem seems similar to the knapsack problem, which is NP by the way.</p>

CC BY-SA 3.0
2012-01-18T15:58:11.837Z
The question says, “the subset M of size k.”
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-18T15:33:04.507Z
2012-01-18T15:33:04.507Z
Guillermo.
<p>Set $S=\{e_1,\cdots,e_n\}$ is given. For each element $e_i$, we have weight $w_i&gt;0$ and cost $c_i&gt;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}$$.</p>

<p>Is the problem NP-hard?</p>

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

<p>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>

<p>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.[<strong>I was wrong about this! It is in P by this assumption</strong>]</p>

CC BY-SA 3.0
2012-01-12T21:16:52.257Z
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?
zotachidil
CC BY-SA 3.0
2012-01-12T21:28:25.280Z
It is not correct, because costs are important as well. Consider following example:
Nasooh
CC BY-SA 3.0
2012-01-12T21:37:14.470Z
w1=50, c1=80 - w2=40, c2= 15 - w3=10, c3=5. For k equal to 1 choosing e2 is more beneficial than e1.
Nasooh
CC BY-SA 3.0
2012-01-12T23:14:21.783Z
You're right. Hmm...
zotachidil
CC BY-SA 3.0
2012-01-13T23:30:57.507Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-17T17:21:29.953Z
Unless I misunderstand, for the case where $w_i c_i = p$ couldn't you just add the $k$ elements where $w_i - p/w_i$ is largest?
mhum
CC BY-SA 3.0
2012-01-17T19:59:41.420Z
@mhum: nice idea! I checked it. In this case, $w_i c_i = p$, sorting with respect to $w_i$ works. We will get the optimum solution by choosing $k$ element with with the largest $w_i$ value. In general maybe something like $w_i + f(c_i,w_i)$ helps.
Nasooh
<np-hardness><optimization>
Set optimization problem - is it np-complete?
Nasooh
# Set optimization problem - is it np-complete?

(Asked by: username_0 on 2012-01-12)

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**]

**Tags:** np-hardness, optimization

> **Comments:**
> **username_1**: 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?  
> **username_0**: It is not correct, because costs are important as well. Consider following example:  
> **username_0**: w1=50, c1=80 - w2=40, c2= 15 - w3=10, c3=5. For k equal to 1 choosing e2 is more beneficial than e1.  
> **username_1**: You're right. Hmm...  
> **username_2**: 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.  
> **username_3**: Unless I misunderstand, for the case where $w_i c_i = p$ couldn't you just add the $k$ elements where $w_i - p/w_i$ is largest?  
> **username_0**: @username_3: nice idea! I checked it. In this case, $w_i c_i = p$, sorting with respect to $w_i$ works. We will get the optimum solution by choosing $k$ element with with the largest $w_i$ value. In general maybe something like $w_i + f(c_i,w_i)$ helps.  

---

## 2 answers

### Answer by username_4 on 2018-07-31. Score: 2

*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.)*

> **Comments:**
> **username_5**: 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?  
> **username_4**: @WillardZhan, yes, that seems right.  

---

### Answer by username_6 on 2012-01-18. Score: -6

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.

> **Comments:**
> **username_2**: The question says, “the subset M of size k.”  

---

