I encountered the following optimization problem. Let $ S = \lbrace 1, 2, \ldots, n \rbrace $ be a set of items. Each item $ i \in S $ has a non-negative benefit $ b_i \in \mathbb R^+ $, non-negative weight $ w_i \in \mathbb R^+ $ and a non-negative cost $ c_i \in R^+ $. The objective is to select $ A \subseteq S $ that maximizes the function $ \frac{\sum_{i \in A} b_i w_i}{\sum_{i \in A} w_i} - \frac{\sum_{i \in A} c_i \sqrt{w_i} }{\sqrt{\sum_{i \in A} w_i}} $. In addition, there is an optional cardinality contraint $ |A| \leq K $ for a given $ K \in \mathbb Z^+ $.

The problem can be viewed as a fractional combinatorial optimization problem. However the difficulty stems from the second term where the denominator is not linear.

  1. If the second term is omitted, the problem becomes solvable in polynomial time (Hansen et al., 1991).
  2. If the second term had instead a linear denominator which is different from the denominator of the first term, the problem becomes NP-hard (Prokopyev et al., 2004)

The problem can also be viewed as a set function optimization problem. When the set function $F$ is submodular (i.e. $ F(A) + F(B) >= F(A \cup B) + F(A \cap B), \forall A, B \subseteq S $), maximization is NP-hard.

The objective function exhibits submodularity for some values of $b_i$, $w_i$, $c_i$ but not for all cases.

Are there problems with similar objective functions? Is the problem solvable in polynomial time or NP-hard?

The decision version of the problem can be stated as: is there $ A \subseteq S $ such that $ \frac{\sum_{i \in A} b_i w_i}{\sum_{i \in A} w_i} - \frac{\sum_{i \in A} c_i \sqrt{w_i} }{\sqrt{\sum_{i \in A} w_i}} \geq M $ for some $ M $?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.