3
$\begingroup$

Suppose we have multiple intervals $R_1,R_2,...,R_i$ of non-negative integers. These intervals may overlap and we use $R_h(\mathrm{median})$ to denote the median integer in the $h$-th interval $R_h$, and $x_R$ to denote the interval that the integer $x$ comes from. It is possible that two integers $x$ and $y$ are equal but they come from different intervals (i.e., $x=y$ but $x_R\neq y_R$).

Suppose we have a threshold $T$, a positive integer $N$, and a function $f(x)$ whose input is an integer $x$ and it is defined as: $f(x)=x$, if $x \leq N$. $f(x)=max(0,2N-x)$, if $x>N$.

I want to choose integers from intervals $R_1,R_2,...,R_i$ to maximise the cumulative scores $f()$ without exceeding the threshold $T$.

There are two constraints

  1. Chosen integers must come from different intervals

  2. Given two chosen integers $x$ and $y$, if $x_R(\mathrm{median}) \leq y_R(\mathrm{median})$, then $$ \frac{x_R(\mathrm{median})}{x} \leq \frac{y_R(\mathrm{median})}{y}. $$

The objective is maximising the following: $$ \sum_{x \in R_1,R_2,...,R_i} p_x f(x) $$ subject to:

  1. $p_x=\{0,1\}$,
  2. $\sum_{x \in R_1,R_2,...,R_i} xp_x \leq T$,
  3. $\forall (x, y)$, if $p_x=p_y=1$, then $x_R \neq y_R$,
  4. $\forall (x, y)$, if $p_x=p_y=1$ and $x_R(\mathrm{median}) \leq y_R(\mathrm{median})$, then $$ \frac{x_R(\mathrm{median})}{x} \leq \frac{y_R(\mathrm{median})}{y}. $$

I have proved that this problem is weakly NP-hard by reduction from knapsack problem when each range contains exactly one integer. But I think the my problem should not be just weakly NP-hard. I know this problem can be reduced to the Knapsack Problem with conflict graphs, but not vice versa. Is it possible to perform reduction from existing strongly NP-hard problems to the one described above?

$\endgroup$
9
  • 1
    $\begingroup$ You may want to think about the case where every range contains a single number. $\endgroup$
    – Gamow
    May 16 at 13:46
  • $\begingroup$ So the function $f$ is of the form $f(x) = \max(0, \min(x, N-x))$ for some fixed $N$? Do you allow the case where $N$ is much larger than all intervals, and all intervals are non-negative, so $f(x) = x$? $\endgroup$
    – Neal Young
    May 16 at 20:02
  • $\begingroup$ @Gamow, thanks for your reply. I have updated my questions based on your comments. The case you mentioned only shows the weakly NP-hardness of my problem but I want to see whether my problem is strongly NP-hard. $\endgroup$ May 17 at 5:52
  • $\begingroup$ @NealYoung The function $f(x)=x$ when $x < N$ and $f(x)=max(0,2N-x)$ when $x \geq N$. Actually each range/interval $R_j$ $(1 \leq j \leq i)$ corresponds to a fixed $N_j$. But here, I assume that all intervals correspond to the same fixed $N$, which probably makes it easier to analyse the hardness. The value of $N$ is arbitrary. I want to show this problem to be strongly-NP hard. $\endgroup$ May 17 at 6:15
  • 1
    $\begingroup$ What does range mean here? $\endgroup$ May 17 at 7:34
3
+100
$\begingroup$

This problem can be solved with dynamic programming in pseudo-polynomial time (proof below). Therefore, it is not possible to show that this problem is strongly NP-hard (unless P=NP).


First, let's restate the problem:

Given: values $N$ and $T$ and positive integer intervals $R_1$, $R_2$, $\ldots$, and $R_n$

Output: the largest possible value of $\sum_{i=1}^nf(x_i)$ (where $f$ is defined in terms of $N$ as described above) such that the variables $x_1, x_2, \ldots, x_n$ satisfy all of the following:

  • $x_i \in R_i$ for $i = 1,2,\ldots,n$
  • $\sum_{i=1}^nx_i \le T$
  • for all pairs $i,j$, if $\text{median}(R_i) \le \text{median}(R_j)$ then $\frac{\text{median}(R_i)}{x_i} \le \frac{\text{median}(R_j)}{x_j}$

We can assume without loss of generality that the $R_i$s are sorted by median. That is, assume that $\text{median}(R_1) \le \text{median}(R_2) \le \ldots \le \text{median}(R_n)$. If we do, the final condition can be simplified. It is both necessary and sufficient that $\frac{\text{median}(R_1)}{x_1} \le \frac{\text{median}(R_2)}{x_2} \le \ldots \le \frac{\text{median}(R_n)}{x_n}$.

(Note: this is not precisely correct. Assuming no intervals have the same median, this is correct, but if multiple intervals have the same median it is actually also necessary that the $x_i$ values chosen for those intervals have to all be the same. This makes things more complicated without really making the problem any harder, so I'm going to ignore this possibility for the rest of this answer.)


With that done, we can define the subproblems that we will use for our dynamic programming solution.

Given: all the inputs for the problem as well as (1) an index $k$ with $1 \le k \le n$, (2) a threshold $t$ with $0 \le t \le T$, and (3) a value $X \in R_k$

Output: the largest possible value of $\sum_{i=1}^kf(x_i)$ such that the variables $x_1, x_2, \ldots, x_k$ satisfy all of the following:

  • $x_i \in R_i$ for $i = 1,2, \ldots, k$
  • $x_k = X$
  • $\sum_{i = 1}^kx_i \le t$
  • for $i = 1,2, \ldots, k-1$, it is the case that $\frac{\text{median}(R_i)}{x_i} \le \frac{\text{median}(R_{i+1})}{x_{i+1}}$

Let $S[k][t][X]$ denote the output of this subproblem.


Note that the overall problem's answer can be expressed in terms of several subproblems: the overall answer is $\max_{X \in R_n}S[n][T][X]$.

Note also that the number of subproblems is small (polynomial in the size of the numbers in the input of the problem). In particular, $k$ takes on $n$ possible values, $t$ takes on $T+1$ possible values, and $X$ takes on $\sum_{i=1}^n|R_i|$ possible values. Each of these is polynomial in the numbers used as inputs to the problem. Therefore, the overall number of subproblems is also polynomial in the numeric value of the input. Thus, provided we can show that each subproblem can be solved in pseudo-polynomial time, it will also be the case that all the subproblems together can be solved in pseudo-polynomial time, and therefore that the overall problem can be solved in pseudo-polynomial time.


In order to actually solve the subproblems, we will use dynamic programming. In other words, we will build up a table of values for $S[k][t][X]$. We can compute these subproblems in order primarily by $k$. In other words, we can assume that by the time we are computing $S[k][t][X]$, the value of $S[k'][t'][X']$ has already been computed provided $k' < k$.

So how do we actually compute these values?

The base case, where $k=1$, is easy. $S[1][t][X]$ is defined as the largest possible value of $\sum_{i=1}^kf(x_i) = f(x_1)$ where $x_1 = X \le t$. Therefore, provided $X \le t$, we have that $S[1][t][X] = f(X)$. Otherwise, no such value is possible and so we can set $S[1][t][X]$ to $-\infty$ to indicate that no real value is achievable.

Otherwise, let's say we're trying to compute $S[k][t][X]$ for some $k > 1$. This value is defined as the largest possible value of $\sum_{i=1}^kf(x_i)$ subject to the following constraints:

  • $x_i \in R_i$ for $i = 1,2, \ldots, k$
  • $x_k = X$
  • $\sum_{i = 1}^kx_i \le t$
  • for $i = 1,2, \ldots, k-1$, it is the case that $\frac{\text{median}(R_i)}{x_i} \le \frac{\text{median}(R_{i+1})}{x_{i+1}}$

Since we know $x_k = X$, the value we are maximizing is $\sum_{i=1}^kf(x_i) = f(x_k) + \sum_{i=1}^{k-1}f(x_i) = f(X) + \sum_{i=1}^{k-1}f(x_i)$. This is the same as just maximizing $\sum_{i=1}^{k-1}f(x_i)$. What conditions do the variables $x_1, \ldots, x_{k-1}$ have to satisfy? We can reframe the above conditions as follows:

  • $x_i \in R_i$ for $i = 1,2, \ldots, k-1$
  • $\sum_{i = 1}^{k-1}x_i \le t - X$
  • for $i = 1,2, \ldots, k-2$, it is the case that $\frac{\text{median}(R_i)}{x_i} \le \frac{\text{median}(R_{i+1})}{x_{i+1}}$
  • it is the case that $\frac{\text{median}(R_{k-1})}{x_{k-1}} \le \frac{\text{median}(R_{k})}{X}$

By the final condition, only some of the possible values of $x_{k-1}$ are actually permissible values. In particular, we have the condition that $\frac{\text{median}(R_{k-1})}{x_{k-1}} \le \frac{\text{median}(R_{k})}{X}$, which can be rearranged to be $x_{k-1} \ge X \times \frac{\text{median}(R_{k-1})}{\text{median}(R_{k})}$. Thus, $x_{k-1}$ must be some value from $R_{k-1} \cap [X \times \frac{\text{median}(R_{k-1})}{\text{median}(R_{k})}, \infty)$. Call this other interval $R_{k-1}'(X)$

Suppose we fix some value $Y \in R_{k-1}'(X)$ and add the constraint that $x_{k-1} = Y$. At that point, we're trying to maximize $\sum_{i=1}^{k-1}f(x_i)$ subject to the following:

  • $x_i \in R_i$ for $i = 1,2, \ldots, k-1$
  • $x_{k-1} = Y$
  • $\sum_{i = 1}^{k-1}x_i \le t - X$
  • for $i = 1,2, \ldots, k-2$, it is the case that $\frac{\text{median}(R_i)}{x_i} \le \frac{\text{median}(R_{i+1})}{x_{i+1}}$

But this is just the definition of $S[k-1][t-X][Y]$.

It should be pretty clear at this point that $S[k][t][X]$ is just the maximum over $Y \in R_{k-1}'(X)$ of $f(X) + S[k-1][t-X][Y]$. Note: if $R_{k-1}'(X)$ is empty then no choice of values is possible and so we again set $S[k][t][X]$ to $-\infty$. Similarly, we can assume that if $t-X < 0$ then the value $S[k-1][t-X][Y]$ is just defined to be $-\infty$ by default. (Note that this formula appropriate handles the case where some of the $S[k-1][t-X][Y]$ values are $-\infty$).

Anyway, assuming you deal with all the edge cases, this shows that you can compute $S[k][t][X]$ in terms of the previous values $S[k'][t'][X']$ with $k' < k$. The runtime of this computation is linear in the size of $R_{k-1}'(X)$, which is at most $|R_{k-1}|$. Therefore, the computation of each $S[k][t][X]$ is pseudo-polynomial in the input, implying (as previously argued) that the computation of all the subproblems together also runs in pseudo-polynomial time.


EDIT: I was asked to address two specific issues in the comments. First of all, what happens if the function $f$ can depend on which interval $R_i$ it is taken from. And second, what happens if not every interval has to contribute a value (i.e. if you are allowed to skip an $x_i$). I believe the problem is still solvable with the same pseudo-polynomial time dynamic programming approach. I also mentioned earlier that the solution above ignores the possibility that multiple ranges share the same medians. I have not edited the solution above, but to address these concerns, I'm adding a coded up version of my algorithm (using python), fixed to address all these issues.

I assume that the input consists of a value T (representing $T$) and a list Rs, whose elements represent the ranges $R_i$ and which can be looped over. I assume that the elements of Rs are in sorted order by median and that there exists a function median that can identify the median of any such range. I also assume that there exists a function f which takes as input two values: an index i and a value x. f(i, x) is used to represent $f_i(x)$.

def solve(T, Rs):
  if len(Rs) == 0:
    return 0

  # S is going to be the subproblem lookup table. S[k][t][X] will denote
  # the largest possible output value using xs only from ranges Rs[0]
  # through Rs[k] (with each range contributing at most one x), such that
  # the sum of the xs is at most t, and such that range Rs[k] does contribute
  # a value, and the value it contributes is X.
  S = []

  # base case
  layer = [{X: float(-inf) for X in Rs[0]} for t in range(T+1)] # default to -inf
  S.append(layer)
  for t in range(T+1):
    for X in Rs[0]:
      if X <= t:
        S[0][t][X] = f(0, X)

  # inductive case
  for k in range(1, len(Rs)):
    layer = [{X: float(-inf) for X in Rs[0]} for t in range(T+1)] # default to -inf
    S.append(layer)
    for t in range(T+1):
      for X in Rs[k]:
        # the minimum necessary condition is that X <= t
        if X <= t:
          # if no other range contributes an x, then the smallest possible
          # value is f(k, X)
          layer[t][X] = f(k, X)
          # if some other range does contribute an x, then there is a largest
          # index range which does so; the index of that range is some i < k
          # and we can loop over the possibilities
          for i in range(k):
            # we can also loop over the possible values of what x that range
            # contributed
            for Y in Rs[i]:
              # in order for this to be valid, the following must hold:
              if median(Rs[i]) / Y <= median(Rs[k]) / X:
                # also, if the medians are the same, we also have the
                # constraint that X=Y; therefore, this case is only valid
                # if the following holds
                if median(Rs[i]) != median(Rs[k]) or X == Y:
                  # the best possible value in this case is the following
                  value = f(k, X) + S[i][t-X][Y]
                  # if this is better than anything so far, use this value
                  S[k][t][X] = max(S[k][t][X], value)

  # Now lets actually get the overall answer. One possibility is to use no xs
  # from any range:
  best = 0

  # otherwise, there will be some largest index range which contributes an x
  # and it will contribute some specific X
  for k in range(len(Rs)):
    for X in Rs[k]:
      # the largest possible value in that case subject to all the constraints:
      value = S[k][T][X]
      # we can use that value instead of the best one saved if it's better
      best = max(best, value)

  return best
$\endgroup$
9
  • $\begingroup$ Thanks for the reply. I have two questions. It seems that there is some discrepancy between your problem formulation and mine. Based on yours, the first constraint specifies that each interval must `contribute' an integer. On the other hands, in my problem, for a specific interval, we can either choose one integer from it or just ignore it. So is your solution still able to solve my case? $\endgroup$ May 19 at 14:02
  • $\begingroup$ The second question. Actually, above is the simplified version of my problem. The general one is that the value N varies from interval to interval, which means that each interval $R_i$ corresponds to a value $N_i$ in the function $f()$. So it is possible that $N_i \neq N_j$ if $i \neq j$. Based on my understanding, your solution is still feasible to this general case. Am I right? $\endgroup$ May 19 at 14:07
  • $\begingroup$ The second question is based on the assumption that the answer to the my first question is yes. $\endgroup$ May 19 at 14:15
  • $\begingroup$ Yes, I believe that the same dynamic programming approach solves both of the issues you are referring to. To make it so that you can "skip" an interval, it's enough to just look back over the entire table of past subproblems instead of just looking back over the previous value of $k$. This makes the final answer a bit different (the max over $S[\cdot][T][\cdot]$ instead of $S[n][T][\cdot]$), but the idea is the same. Similarly, replacing $f$ with $f_i$ is also doable, just replace $f(X)$ with $f_i(X)$ in the recursion step. $\endgroup$ May 20 at 5:43
  • $\begingroup$ I agree that the same approach can solve the second issue. But it is still a little bit unclear on the first one. To 'skip' intervals, I think that we cannot just set S[k][t][x] as $- \infty$ when $x>t$. Instead of looking back over the entire table of past subproblems, we should just check the row of $k'$ which is the largest one when $R'_{k'}$ is not empty. Does it make sense? $\endgroup$ May 20 at 7:28

Your Answer

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

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