3
$\begingroup$

I have an optimization problem of the form:

\begin{align} &\text{maximize}\quad f(\mathbf{x}) = \dfrac{\sum\limits_{n=1}^{N}x_na_n}{1+\sum\limits_{n=1}^{N}x_nb_n}\\ & \text{subject to}\quad \sum\limits_{n=1}^{N}x_n\leqslant M,\\ & \quad\quad\quad\quad\quad\;\mathbf{x}=\left[x_1,\ldots,x_N\right]^\top\in\{0,1\}^N. \end{align} where $a_n,b_n$, for all $n$, $M$ and $N$ are the inputs of the problem.

It is a $0-1$ integer programming problem. Can we say that it is NP-hard? Or can you see a straightforward solution for it?

EDIT:

To me, the following algorithm looks like a good one but I cannot prove that it gives the optimal solution.

Algorithm:

Step 1: Sort the list $(a_1/b_1,a_2/b_2,\ldots,a_N/b_N)$ and get the index of the sorted list, i.e., a permutation $\sigma$ of $(1,2,\ldots,N)$, $\sigma(1,2,\ldots,N)$.

Step 2: Set $x_n=0$ for all $n$.

Step 3: Repeat until $\sum_{n=1}^Nx_n=M$

Step 3.1: For $n$ in $\sigma(1,2,\ldots,N)$

Step 3.2: Set $x_n=1$

$\endgroup$
3
  • 2
    $\begingroup$ Do you want NP or NP hard? For NP, you need an algorithm that verifies in polynomial time that some educated guess is the correct answer. For NP hard, you have to give an algorithm that reduces any NP problem whatsoever to this one in polynomial time. $\endgroup$ Dec 15, 2015 at 22:11
  • 1
    $\begingroup$ Your problem is a fractional linear program en.wikipedia.org/wiki/Linear-fractional_programming --- try converting it and seeing if the integer constraints make things hard. Perhaps this problem ends up having a reasonable solution via this route. $\endgroup$
    – Suvrit
    Dec 16, 2015 at 0:24
  • $\begingroup$ Do you know anything about the $a_n$ and $b_n$? Are they nonnegative? Integers? $\endgroup$
    – Noah Stein
    Dec 16, 2015 at 4:05

1 Answer 1

4
$\begingroup$

Short answer: with negative $b_i$'s, it's NP-hard, but otherwise it's polynomial time.

If you allow negative $b_i$ then it is hard (set all the $a_i=1$, so the goal is to get the chosen subset of $b_i$'s to sum to a number close to but greater than $-1$ in order to make the denominator as small as possible — this is a subset sum problem.

If the $a_i$'s and $b_i$'s are all positive, you have a bicriterion matroid optimization problem (the condition that $\sum x_i\le M$ is matroidal, and by bicriterion I mean taking a nonlinear combination of two linear functions). It is known that (under mild conditions on the nonlinear combination that hold for positive $b_i$ but not negative ones) such problems can be solved in polynomial time by parametric techniques (replace the objective function $\sum a_i/(1+\sum b_i)$ by the parametric function $\sum a_i+\lambda(1+\sum b_i)$, then vary $\lambda$ from $-\infty$ to $+\infty$ and keep track of the sequence of maximum weight bases you get — one of them will be the optimal value for the original objective function).

For more on parametric matroid optimization see my paper

Geometric lower bounds for parametric matroid optimization. D. Eppstein. Tech. Rep. 95-11, ICS, UCI, 1995. 27th ACM Symp. Theory of Computing, Las Vegas, 1995, pp. 662–671. Disc. Comp. Geom. 20: 463–476, 1998. http://www.ics.uci.edu/~eppstein/pubs/Epp-DCG-98.pdf

For more on the relation between parametric and bicriterion optimization (mostly not about matroids but with the same general principle) you can see another of my papers, more recent (although this connection is far from original to me):

The parametric closure problem. D. Eppstein. 14th Algorithms and Data Structures Symp. (WADS 2015), Victoria, BC. Springer, Lecture Notes in Comp. Sci. 9214 (2015), pp. 327–338. http://arxiv.org/abs/1504.04073

The particular matroid involved in your question (a uniform matroid), when turned into a parametric optimization problem, has $O(n^{4/3})$ different changes of basis and they can be found in time proportional to that bound — see https://en.wikipedia.org/wiki/K-set_(geometry) for an equivalent problem in computational geometry.

$\endgroup$

Your Answer

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

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