10
$\begingroup$

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]

Improve this question
$\endgroup$
7
  • $\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, 2012 at 21:16
  • $\begingroup$ It is not correct, because costs are important as well. Consider following example: $\endgroup$
    – Nasooh
    Jan 12, 2012 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, 2012 at 21:37
  • $\begingroup$ You're right. Hmm... $\endgroup$
    – zotachidil
    Jan 12, 2012 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, 2012 at 23:30

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 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$
    – Wei Zhan
    Aug 1, 2018 at 19:21
  • $\begingroup$ @WillardZhan, yes, that seems right. $\endgroup$
    – Neal Young
    Aug 1, 2018 at 20:10
-6
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.