Integer knapsack problems with profit functions of the same value range

Abstract

Integer knapsack problems with profit functions of the same value range are studied. Linear time algorithms are presented for the case of convex non-decreasing profit functions, and an NP-hardness proof and a fully polynomial-time approximation scheme are provided for the case of arbitrary non-negative non-decreasing profit functions. Fast solution procedures are also devised for the bottleneck counterparts of these problems. Computational complexity of the case with concave profit functions remains open.

1 Introduction

Knapsack problems appear in diverse applications as sub-tasks of more complex problems. Their solution techniques are employed as subroutines in column generation schemes and lower bound constructions for many NP-hard combinatorial optimization problems. Numerous results exist for knapsack problems, see monographs of Martello and Toth (1990) and Kellerer et al. (2004).

Denote an interval of integer numbers $\{a,a+1,\ldots ,b\}$ as [a, b] for $a<b$, and denote a variable vector $(x_1,\ldots ,x_n)$ as x. Let integer numbers B, $d_j$, real number C, and functions $f_j(x_j)$, $j\in [1,n]$, be given such that $d_j>0$, $0<B<\sum _{j\in [1,n]}d_j$, $0<C\le n$, $f_j(x_j)$ is non-decreasing for $x_j\in [0,d_j]$, $f_j(0)=0$, $f_j(d_j)=1$, and $f_j(x_j)=-\infty$ for $x_j\not \in [0,d_j]$, $j\in [1,n]$. We study the following two knapsack problems, which we denote as K1 and K2.

The problems K1 and K2 admit several equivalent formulations, in which feasible domains of the variables are extended from $[0,d_j]$ to $[a_j,b_j]$, $j\in [1,n]$, the common objective function value range is extended from the interval [0, 1] of real numbers to an arbitrary common interval of real numbers, and the direction of optimization in K1 and the inequality sign in K2 are reversed. Let numbers $B^+$, $C^+$, $L^+$, $U^+$, $B^-$, $C^-$, $L^-$, $U^-$, $a_j$, $b_j$, and functions $f^+_j(x_j)$ and $f^-_j(x_j)$ be given such that $a_j<b_j$ and

• $f^+_j(a_j)=L^+$, $f^+_j(b_j)=U^+$, $L^+<U^+$, $f^+_j(x_j)$ is non-decreasing for $x_j\in [a_j,b_j]$, $f^+_j(x_j)=-\infty$ for $x_j\not \in [a_j,b_j]$, $j\in [1,n]$,

• $f^-_j(a_j)=U^-$, $f^-_j(b_j)=L^-$, $L^-<U^-$, $f^-_j(x)$ is non-increasing for $x_j\in [a_j,b_j]$, and $f^-_j(x_j)=+\infty$ for $x_j\not \in [a_j,b_j]$, $j\in [1,n]$.

The following knapsack problems are equivalent to K1.

The following problems are equivalent to K2.

It is easy to see that for any instance of the problem K1$^+$ (resp., K2 $^+$), the following instance of K1 (resp., K2) is equivalent: $d_j=b_j-a_j$, $f_j(x_j)=\frac{f^+_j(x_j+a_j)-L^+}{U^+-L^+ }$, $j\in [1,n]$, $B=B^+-\sum _{j\in [1,n]}a_j$ (resp., $C=\frac{C^+-nL^+}{U^+-L^+}$). Similarly, for any instance of the problem K1 $^-$ (resp., K2 $^-$), the following instance of K1 $^+$ (resp., K2 $^+$) is equivalent: $f^+_j(x_j)=-f^-_j(x_j)$, $j\in [1,n]$, $B^+=B^-$ (resp., $C^+=-C^-$), $L^+=-U^-$, $U^+=-L^-$. Furthermore, if the profit functions are convex non-decreasing in the original instance of the problem K1 (resp., K2), then they are concave non-increasing in the corresponding instance of the problem K1 $^-$ (resp., K2 $^-$).

To facilitate the presentation, it is convenient to assume that all the functions considered in this paper are computable in a constant time. In this case, any instance of any of the problems K1 $^+$ and K1 $^-$ (resp., K2 $^+$ and K2 $^-$) can be transformed into an equivalent instance of K1 (resp., K2) in O(n) time.

Motivation for the problem K1 $^+$ (resp., K1 $^-$) comes from the maximization of the total success (resp., minimization of the total risk) of the projects by allocating limited resources to them. In this situation, there are n projects, $f^+_j(x_j)$, $0\le f^+_j(x_j)\le 1$, is a convex non-decreasing success function (resp., $f^-_j(x_j)$, $0\le f^-_j(x_j)\le 1$, is a concave non-increasing risk function) for project j, which depends of the amount $x_j$ of a discrete resource allocated to this project, $x_j\in [a_j,b_j]$. Equality $f^+_j(a_j)=L^+=0$ (resp., $f^-_j(a_j)=U^-=1$) implies that if the resource is allocated at its lower bound, then there is no success (resp., there is a full risk) and equality $f^+_j(b_j)=U^+=1$ (resp., $f^-_j(b_j)=L^-=0$) implies that if the resource is allocated at its upper bound, then there is a full success (resp., there is no risk).

Problems K1 and K2 belong to the class of non-linear knapsack problems, which consist in the optimization of a non-linear function, subject to a single non-linear constraint. A review of these problems and their solution methods is given by Bretthauer and Shetty (2002). More recent results can be found in D’Ambrosio and Martello (2011), Zhang and Chen (2012) and D’Ambrosio et al. (2018). In these studies, portfolio selection, stratified sampling, production and inventory planning, and resource distribution are noted as applications of the non-linear knapsack problems.

Given a function f(x) of a discrete argument $x\in [a,b]$ and a number A, we call function $\min \{x\in [a,b]\mid f(x)\ge A\}$ a minimum pseudo-inverse of f(x). In Sect. 2, the case of convex profit functions is studied. We present O(n) time algorithms for the problems K1 and K2 under the assumptions that the function $f_j(x_j)$ for any $x_j$ in the problem K1 and its minimum pseudo-inverse $\min \{x_j\in [0,d_j]\mid f_j(x_j)\ge A\}$ for any A in the problem K2 are computable in a constant time for any $j\in [1,n]$. These algorithms are adaptations of the algorithms for the problems K1 $^-$ and K2 $^-$ with concave non-increasing functions $f^-_j(x_j)$, $j\in [1,n]$, given by Gurevsky et al. (2022) as an illustration of their generic solution approach for a class of min-sum controllable risk problems. The algorithms employ the median finding technique of Blum et al. (1973), which was used for the fractional knapsack problem by Balas and Zemel (1980).

The case of arbitrary non-negative non-decreasing profit functions is considered in Sect. 3. Let a number $\varepsilon >0$ be given. An algorithm for an optimization problem is called an $\varepsilon$-approximation algorithm, if for any instance I of this problem it finds a feasible solution with value $F^0(I)$ such that $|F^0(I)-F^*(I)|\le \varepsilon |F^*(I)|$, where $F^*(I)$ is the optimum value for the instance I. A Fully Polynomial-Time Approximation Scheme (FPTAS) for an optimization problem is a family of $\varepsilon$-approximation algorithms $\{A_\varepsilon \}$ each of which runs in time bounded by a polynomial of $1/\varepsilon$ and of the problem input length in binary encoding. FPTASes are popular solution techniques for knapsack type problems. Recently, Halman et al. (2018) presented an FPTAS for a knapsack problem with parametric weights and Malaguti et al. (2019) and Kovalev (2021) provided FPTASes for a fractional knapsack problem. In Sect. 3, we prove that the problems K1 and K2 with non-negative non-decreasing profit functions are ordinary NP-hard, and present FPTASes with the running times $O(n^3\log _2 n+\frac{n^3}{\varepsilon ^2})$ and $O(n^3\log _2(n d_{\max })+\frac{n^3}{\varepsilon ^2})$, respectively, where $d_{\max }=\max _{j\in [1,n]}d_j$. Our FPTASes are applications of the trimming-of-the-state-space and rounding techniques, originally described by Ibarra and Kim (1975) and Sahni (1977) for the classical knapsack and subset sum problems. We did not manage to prove NP-hardness or develop a polynomial-time algorithm for the case of concave profit functions. Bottleneck counterparts of the problems K1 and K2 are formulated in Sect. 3.3. Simple solution procedures are presented for them. The paper concludes with a short summary of the results and suggestions for future research.

2 Convex profit functions

In this section, it is assumed that the profit functions $f_j(x_j)$, $j\in [1,n]$, are convex non-decreasing. In this case, O(n) time algorithms are developed for the problems K1 and K2.

2.1 Problem K1

Algorithm for the problem K1 is based on the following theorems.

Theorem 1

There exists an optimal solution x of the problem K1, in which there is at most one index $j^*\in [1,n]$ such that all variables but variable $x_{j^*}$ are equal to their lower or upper bounds: $x_j\in \{0,d_j\}$, $j\in [1,n]\backslash \{j^*\}$, and $x_{j^*}=\min \Big \{d_{j^*},B-\sum _{j\in [1,n]\backslash \{j^*\}} x_j\Big \}$.

Proof

Follows from the convexity of the functions $f_j(x_j)$, $j\in [1,n]$. $\square$

Denote $N_j=\{i\mid d_i\le d_j, i\in [1,n]\}$, $j\in [1,n]$.

Theorem 2

There exists an optimal solution x of the problem K1 and indices $j^0$ and $j^*$, $j^0\in [1,n]$, $j^*\in [1,n]$, such that $x_j=d_j$ for $j\in N_{j^0}\backslash \{j^*\}$, $x_j=0$ for $j\not \in N_{j^0}\cup \{j^*\}$ and $x_{j^*}=\min \Big \{d_{j^*},B-\sum _{j\in N_{j^0}\backslash \{j^*\}}d_j\Big \}$.

Proof

Let index $j^*$, mentioned in Theorem 1, be fixed. Since $f_j(d_j)=1\ge f_i(x_i)$ for $j\in [1,n]$, $i\in [1,n]$, the problem K1 reduces to selecting the maximum number of $d_j$, $j\ne j^*$, whose sum does not exceed B. Obviously, these numbers form the set $N_{j^0}\backslash \{j^*\}$ for some $j^0\in [1,n]$. $\square$

Denote $D_j=\sum _{i\in N_j}d_i$, $j\in [1,n]$.

Theorem 3

If the function $f_j(x_j)$ is computable in a constant time for any $x_j$ and $j\in [1,n]$, then the problem K1 can be solved in O(n) time.

Proof

Assume for a while that the elements of the set [1, n] are re-numbered such that $d_1\le \cdots \le d_n$. Define a unique index $j^{(B)}$ such that $D_{j^{(B)}}\le B<D_{j^{(B)}+1}$, $j^{(B)}\in [0,n-1]$, where $D_0:=0$. Denote by $F^*$ the optimal solution value of the problem K1 and denote by F(v, u) the value of a solution x of this problem such that $x_j=d_j$ for $j\in N_v\backslash \{u\}$, $x_j=0$ for $j\not \in (N_{v}\cup \{u\})$ and $x_u=\min \Big \{d_{u},B-\sum _{j\in N_{v}\backslash \{u\}}d_j\Big \}$, that is,

$$\begin{aligned} F(v,u)=\sum _{j\in N_v\backslash \{u\}}f_j(d_j)+f_u(x_u)=|N_v\backslash \{u\}|+f_u\left( \min \left\{ d_{u},B-\sum _{j\in N_{v}\backslash \{u\}}d_j\right\} \right) . \end{aligned}$$

Note that, by the definition of the function $f_j(x_j)$, $F(v,u)=-\infty$ if $x_u<0$. It follows from Theorem 2 that $F^*=\max \{F(v,u)\mid v\in [1,n],u\in [1,n]\}$.

Consider three cases for the index u: 1) $u\le j^{(B)}$, 2) $u=j^{(B)}+1$ and 3) $u\ge j^{(B)}+2$. In the case 1), there are three sub-cases: 1.1) $v\le j^{(B)}$, 1.2) $v=j^{(B)}+1$, and 1.3) $v\ge j^{(B)}+2$. In the sub-case 1.1), $F(v,u)=v\le j^{(B)}$. In the sub-case 1.2), there are two more sub-cases: 1.2.1) $\sum _{j\in N_{j^{(B)}+1}\backslash \{u\}}d_j\le B$ and 1.2.2) $\sum _{j\in N_{j^{(B)}+1}\backslash \{u\}}d_j>B$. In the sub-case 1.2.1), $F(v,u)=F(j^{(B)}+1,u)=j^{(B)}+ f_u(B-D_{j^{(B)}+1}+d_u)$, and in the sub-case 1.2.2), $F(v,u)=F(j^{(B)}+1,u)=-\infty$. In the case 2), there are three sub-cases again: 2.1) $v\le j^{(B)}$, 2.2) $v=j^{(B)}+1$, and 2.3) $v\ge j^{(B)}+2$. In the sub-case 2.1), $F(v,u)=F(v,j^{(B)}+1)= v+f_{j^{(B)}+1}({\min \{d_{j^{(B)}+1},B-D_v\}})\le j^{(B)}$ if $v\le j^{(B)}-1$, and $F(v,u)=F(j^{(B)},j^{(B)}+1)= j^{(B)}+f_{j^{(B)}+1}(B-D_{j^{(B)}})$ if $v=j^{(B)}$. In the sub-case 2.2), $F(v,u)=F(j^{(B)}+1,j^{(B)}+1)=j^{(B)}+f_{j^{(B)}+1}(B-D_{j^{(B)}})$, and in the sub-case 2.3), $F(v,u)=-\infty$. In the case 3), there are two sub-cases: 3.1) $v\le j^{(B)}$, and 3.2) $v\ge j^{(B)}+1$. In the sub-case 3.1), $F(v,u)=v+f_u({ \min \{d_u,B-D_v\}})\le j^{(B)}$ if $v\le j^{(B)}-1$, and $F(v,u)=F(j^{(B)},u)= j^{(B)}+f_u(B-D_{j^{(B)}})$ if $v=j^{(B)}$. In the sub-case 3.2), $F(v,u)=-\infty$. We deduce that

$$\begin{aligned} F^*= & {} j^{(B)}+\max \left\{ \max \{f_{u}(B-D_{j^{(B)}+1}+d_u)\mid u\in N_{j^{(B)}}\},\right. \\&\left. \max \{f_{u}(B-D_{j^{(B)}})\mid u\in [1,n]\backslash N_{j^{(B)}}\} \right\} . \end{aligned}$$

If index of the $j^{(B)}$-th smallest value $d_j$ is given, then the sets $N_{j^{(B)}}$, $N_{j^{(B)}+1}$ and $[1,n]\backslash N_{j^{(B)}}$, and the values $D_{j^{(B)}}$ and $D_{j^{(B)}+1}$ can be calculated in O(n) time. Hence, the optimal value $F^*$ and the corresponding optimal vector $x^*$ can be found in O(n) time as well. The index $j^{(B)}$ is an analogue of the split item in the continuous knapsack problem, which can be found in O(n) time by the algorithm Split described in (Kellerer et al. 2004, p. 44). $\square$

Observe that the algorithm in the proof of Theorem 3 is an adaptation of the greedy algorithm of Dantzig (1957) for the continuous knapsack problem in a combination with the median finding technique. However, we do not see a way to justify this observation other than to repeat our arguments in Theorems 1,  2 and 3.

2.2 Problem K2

Similar to K1, an O(n) time algorithm for the problem K2 is justified by the following theorems.

Theorem 4

There exists an optimal solution x of the problem K2, in which there is at most one index $j^*\in [1,n]$ such that all variables but variable $x_{j^*}$ are equal to their lower or upper bounds: $x_j\in \{0,d_j\}$, $j\in [1,n]\backslash \{j^*\}$, and $x_{j^*}=\min \Big \{x\mid x\in [0,d_{j^*}],\ f_{j^*}(x)\ge C-\sum _{j\in [1,n]\backslash \{j^*\}} f_j(x_j)\Big \}$.

Proof

Follows from the convexity of the functions $f_j(x_j)$, $j\in [1,n]$. $\square$

Recall that $N_j=\{i\mid d_i\le d_j, i\in [1,n]\}$ and $D_j=\sum _{i\in N_j}d_i$, $j\in [1,n]$.

Theorem 5

There exists an optimal solution x of the problem K2 and indices $j^0$ and $j^*$, $j^0\in [1,n]$, $j^*\in [1,n]$, such that $x_j=d_j$ for $j\in N_{j^0}\backslash \{j^*\}$, $x_j=0$ for $j\not \in (N_{j^0}\cup \{j^*\})$ and $x_{j^*}=\min \Big \{x\mid x\in [0,d_{j^*}],\ f_{j^*}(x)\ge C-|N_{j^0}\backslash \{j^*\}|\Big \}$.

Proof

Let the index $j^*$ mentioned in Theorem 4 be fixed. Since $f_j(d_j)=1\ge f_i(x_i)$ for $j\in [1,n]$, $i\in [1,n]$, the problem K2 reduces to selecting the minimum number, denoted as k, of smallest $d_j$, $j\ne j^*$, such that $k\ge C-1$. Obviously, these numbers form the set $N_{j^0}\backslash \{j^*\}$ for some $j^0\in [1,n]$. $\square$

Theorem 6

If the minimum pseudo-inverse $\min \{x_j\in [0,d_j]\mid f_j(x_j)\ge A\}$ of the function $f_j(x_j)$ is computable in a constant time for any A and $j\in [1,n]$, then the problem K2 can be solved in O(n) time.

Proof

Assume for a while that $d_1\le \cdots \le d_n$. Denote by $G^*$ the optimal solution value of the problem K2 and denote by G(v, u) the value of a solution x of this problem such that $x_j=d_j$ for $j\in N_{v}\backslash \{u\}$, $x_j=0$ for $j\not \in (N_{v}\cup \{u\})$ and $x_u=\min \Big \{x\mid x\in [0,d_u],\ f_{u}(x)\ge C-|N_{v}\backslash \{u\}|\Big \}$, that is,

$$\begin{aligned} G(v,u)=\sum _{j\in N_{v}\backslash \{u\}}d_j+x_u= & {} \sum _{j\in N_{v}\backslash \{u\}}d_j+\min \left\{ x\mid x\in [0,d_u],\ f_{u}(x)\right. \\&\left. \ge C-|N_{v}\backslash \{u\}|\right\} . \end{aligned}$$

If the system of two relations $x\in [0,d_u]$ and $f_{u}(x)\ge C-|N_{v}\backslash \{u\}|$ has a solution (that is, if $C-|N_{v}\backslash \{u\}|\le 1$), then G(v, u) is well defined. If it does not have a solution (that is, if $C-|N_{v}\backslash \{u\}|>1$), then define $G(v,u)=+\infty$. It follows from Theorem 5, that $G^*=\min \{G(v,u)\mid v\in [1,n],u\in [1,n],v\ge \lceil C\rceil -1\}$.

Consider $v\ge \lceil C\rceil -1$ and two cases for the index u: 1) $1\le u\le v$ and 2) $u\ge v+1$. In the case 1), $|N_{v}\backslash \{u\}|=v-1$ and there are three sub-cases: 1.1) $v=\lceil C\rceil -1$, 1.2) $v=\lceil C\rceil$, and 1.3) $v\ge \lceil C\rceil +1$. In the sub-case 1.1), $|N_{v}\backslash \{u\}|=\lceil C\rceil -2$, $C-|N_{v}\backslash \{u\}|=C-\lceil C\rceil +2>1$, and hence, $G(v,u)=+\infty$. In the sub-case 1.2), $C-|N_{v}\backslash \{u\}|=C-v+1=C-\lceil C\rceil +1\le 1$, and hence, for $u\le v=\lceil C\rceil$,

$$\begin{aligned} G(v,u)=G(\lceil C\rceil ,u)=D_{\lceil C\rceil }-d_u +\min \{x\mid x\in [0,d_u],\ f_{u}(x)\ge C-\lceil C\rceil +1\}. \end{aligned}$$

In the sub-case 1.3), $C-|N_{v}\backslash \{u\}|=C-v+1\le C-\lceil C\rceil \le 0$, and hence,

$$\begin{aligned} G(v,u)= & {} D_v-d_u +\min \{x\mid x\in [0,d_u],\ f_{u}(x)\ge C-v+1\}\\= & {} D_v-d_u\ge { D_v-d_v=D_{v-1}\ge }D_{\lceil C\rceil }. \end{aligned}$$

In the case 2), $|N_{v}\backslash \{u\}|=v$ and there are two sub-cases: 2.1) $v=\lceil C\rceil -1$ and 2.2): $v\ge \lceil C\rceil$. In the sub-case 2.1), $|N_{v}\backslash \{u\}|=v=\lceil C\rceil -1$, $C-|N_{v}\backslash \{u\}|=C-\lceil C\rceil +1\le 1$, and hence, for $u\ge v+1=\lceil C\rceil$,

$$\begin{aligned} G(v,u)=G(\lceil C\rceil -1,u)= D_{\lceil C\rceil -1}+\min \{x\mid x\in [0,d_u],\ f_{u}(x)\ge C-\lceil C\rceil +1\}. \end{aligned}$$

In the sub-case 2.2), $C-|N_{v}\backslash \{u\}|=C-v\le C-\lceil C\rceil \le 0$, and hence,

$$\begin{aligned} G(v,u)=D_v+\min \{x\mid x\in [0,d_u],\ f_{u}(x)\ge C-v\}=D_v\ge D_{\lceil C\rceil }. \end{aligned}$$

We deduce that

$$\begin{aligned} G^*= & {} \min \left\{ D_{\lceil C\rceil }- \max _{1\le u\le \lceil C\rceil }\{d_u -\min \{x\mid x\in [0,d_u],\ f_{u}(x)\ge C-\lceil C\rceil +1\}\}\right. , \\&\left. D_{\lceil C\rceil -1}+\min _{\lceil C\rceil \le u\le n}{ \min }\{x\mid x\in [0,d_u],\ f_{u}(x)\ge C-\lceil C\rceil +1\} \right\} . \end{aligned}$$

Similar to the index $j^{(B)}$ in the Proof of Theorem 3, index of the $\lceil C\rceil$-th smallest value $d_j$, and hence, the optimal value $G^*$ and the corresponding optimal solution of the problem K2 can be found in O(n) time by an adaptation of the algorithm Split in (Kellerer et al. 2004, p. 44). $\square$

Note that the minimum pseudo-inverse is computable in a constant time for many functions. For example, for the function $f(x)=x^2$, we have $\min \{x\in [0,d]\mid f(x)\ge A\}=\lceil \sqrt{A}\rceil$, if $\sqrt{A}\le d$ and the above minimum does not exist if $\sqrt{A}>d$. For an arbitrary non-decreasing function f(x) which is computable in a constant time, and $x\in [0,d]$, the minimum pseudo-inverse can be calculated in $O(\log _2 d)$ time by a bisection search.

3 Arbitrary non-negative non-decreasing profit functions

In this section, we assume that the profit functions $f_j(x_j)$, $j\in [1,n]$, are arbitrary non-negative non-decreasing and their minimum pseudo-inverse $\min \{x_j\in [0,d_j]\mid f_j(x_j)\ge A\}$ is computable in a constant time for any A and $j\in [1,n]$. We prove that any of the problems K1 and K2 is NP-hard in this case and present FPTASes for K1 and K2. We failed to prove NP-hardness or develop a polynomial-time algorithm for the problem K1 or K2 with concave profit functions. Note that analogues of Theorems 1 and 4 do not hold in this case.

3.1 NP-hardness proof

Let us consider the following decision version of any of the problems K1 and K2, which we denote as KD.

Problem

KD: Given positive integer numbers A, B, $d_j$ and arbitrary non-negative non-decreasing functions $f_j(\cdot )$, $j\in [1,n]$, does there exist a vector $x=(x_1,\ldots ,x_n)$ such that $\sum _{j\in [1,n]} f_j(x_j)\ge A$, $\sum _{j\in [1,n]} x_j\le B$ and $x_j\in [0,d_j]$, $j\in [1,n]$?

We prove that KD is NP-complete if profit functions $f_j(\cdot )$ are arbitrary non-negative non-decreasing and computable in polynomial time of $~\log _2 d_j$, $j\in [1,n]$. This implies that both K1 and K2 are NP-hard.

Theorem 7

Problem KD is NP-complete if profit functions $f_j(\cdot )$ are arbitrary non-negative non-decreasing and computable in polynomial time of $~\log _2 d_j$, $j\in [1,n]$.

Proof

We use a transformation from the NP-complete problem Partition (Garey and Johnson 1979): Given positive integer numbers $h_j$, $j\in [1,k]$, and H such that $\sum _{j\in [1,k]}h_j=2H$, is there a set $I\subset [1,k]$ such that $\sum _{j\in I} h_j=H$? Assume without loss of generality that $h_j\ge 2$, $j\in [1,k]$.

For any instance of Partition, we construct the following instance of KD. Set $n=k$, $A=2$, $B=H$, $d_j=H-1$, $f_j(x_j)=0$ for $x_j\in [0,h_j-1]$, $f_j(x_j)=2h_j/H$ for $x_j\in [h_j,d_j-1]$ and $f_j(d_j)=1$, $j\in [1,n]$. We show that the instance of Partition has a solution if and only if the respective instance of KD has a solution.

Assume that set I is a solution of the instance of Partition. Define $x_j=h_j$ if $j\in I$ and $x_j=0$ if $j\not \in I$, $j\in [1,n]$. Then, we have $\sum _{j\in [1,n]} f_j(x_j)=2\sum _{j\in I} h_j/H=2$ and $\sum _{j\in I} x_j=\sum _{j\in I} h_j=H$. Hence, vector x is a solution of the instance of KD.

Now, assume that the instance of KD has a solution, which we denote as vector x. If there is $j\in [1,n]$ such that $x_j=d_j=H-1$, then $f_j(x_j)=1$, $\sum _{i\in [1,j-1]\cup [j+1,n]}x_i\le 1$, $x_i\le 1$, $i\in [1,j-1]\cup [j+1,n]$, and, as a consequence, $\sum _{j\in [1,n]}f_j(x_j)=1$, which is a contradiction. Therefore, $x_j\le d_j-1$, $j\in [1,n]$. Define set I such that $j\in I$ if $d_j-1\ge x_j\ge h_j$ and $j\not \in I$ if $x_j<h_j$, $j\in [1,n]$. Then, we have $f_j(x_j)=0$ for $j\not \in I$ and $f_j(x_j)=f_j(h_j)=2h_j/H$ for $j\in I$. Taking into account the definition of the problem KD, we must have $\sum _{j\in I}h_j\le \sum _{j\in I}x_j\le \sum _{j\in [1,n]}x_j\le H$ and $\sum _{j\in I}2h_j/H=\sum _{j\in I}f_j(h_j)=\sum _{j\in I}f_j(x_j)+\sum _{j\not \in I}f_j(x_j)=\sum _{j\in [1,n]}f_j(x_j)\ge 2$. The latter chain of relations implies $\sum _{j\in I}h_j\ge H$, which together with $\sum _{j\in I}h_j\le H$ further indicates that I is a solution of the instance of Partition. $\square$

3.2 Generic FPTASes

The main components of our FPTAS for the problems K1 are:

• formulation of a generic problem, denoted as KG1,

• formulation of a scaled and rounded problem, denoted as KG-R1,

• proof that an optimal solution of KG-R1 is an $\varepsilon$-approximation solution of KG-R1,

• dynamic programming algorithm for KG-R1, denoted as DP-R1, which constitutes an FPTAS for KG1, and

• a procedure to improve lower and upper bounds for the optimal profit $F^*$, which finds a value L such that $L\le F^*\le 4L$ and makes the FPTAS more efficient.

Assume that, besides $f_j(x_j)$, non-negative non-decreasing functions $g_j(x_j)$ are given, $j\in [1,n]$.

Generic problem KG1:

$$\begin{aligned} \max _{x} \sum _{j\in [1,n]} f_j(x_j), \text{ subject } \text{ to } \sum _{j\in [1,n]} g_j(x_j)\le B,\ x_j\in [0,d_j],\ j\in [1,n]. \end{aligned}$$

Let $x^*$ and $F^*$ denote an optimal solution and its optimal objective value of KG1, respectively. Assume that numbers V and U are known such that $0<V\le F^*\le U$. Define $\delta =\varepsilon V/n$.

Scaled and rounded problem KG-R1:

$$\begin{aligned} \max _{x} \sum _{j\in [1,n]} \Big \lceil \frac{f_j(x_j)}{\delta }\Big \rceil , \text{ subject } \text{ to } \sum _{j\in [1,n]} g_j(x_j)\le B,\ x_j\in R_j,\ j\in [1,n], \end{aligned}$$

where

$$\begin{aligned} R_j= & {} \Big \{r_j(0),r_j(1),\ldots ,r_j\Big (\Big \lfloor \frac{U}{\delta }\Big \rfloor \Big )\Big \}, \\ r_j(s)= & {} \min \Big \{ x\mid x\in [0,d_j],\ \Big \lfloor \frac{f_j(x)}{\delta }\Big \rfloor =s\Big \}\\= & {} \min \{ x\mid x\in [0,d_j],\ f_j(x)\ge s\delta \},\ j\in [1,n]. \end{aligned}$$

Let $x^{(0)}$, $Q^{(0)}$ and $F^{(0)}$ denote an optimal solution, its objective function value with respect to the problem KG-R1 and its objective function value with respect to the original generic problem KG1, respectively. Note that $x^{(0)}$ is feasible for KG1, and $x^*$ is feasible for KG-R1. Let us evaluate the quality of $x^{(0)}$ with respect to KG1.

$$\begin{aligned} F^{(0)}= & {} \sum _{j\in [1,n]} f_j(x^{(0)}_j)=\delta \sum _{j\in [1,n]} \frac{f_j(x^{(0)}_j)}{\delta }>\delta \sum _{j\in [1,n]} \Big (\Big \lceil \frac{f_j(x^{(0)}_j)}{\delta }\Big \rceil -1\Big )\\\ge & {} [\, x^{(0)} \text{ is } \text{ optimal } \text{ for } \text{ KG-R1 } ] \\\ge & {} \delta \sum _{j\in [1,n]} \Big (\Big \lceil \frac{f_j(x^*_j)}{\delta }\Big \rceil -1\Big )\ge \sum _{j\in [1,n]} f_j(x^*_j)-n\delta =F^*-n\delta =F^*-\varepsilon V. \end{aligned}$$

We obtain $F^*-F^{(0)}<\varepsilon F^*$. Let us evaluate $Q^{(0)}$ from above.

$$\begin{aligned} Q^{(0)}= & {} \sum _{j\in [1,n]} \Big \lceil \frac{f_j(x^{(0})}{\delta }\Big \rceil < \sum _{j\in [1,n]} \Big (\frac{f_j(x^{(0)})}{\delta }+1\Big )\\\le & {} \sum _{j\in [1,n]} \frac{f_j(x^*)}{\delta }+n=\frac{F^*}{\delta }+n\le \frac{U}{\delta }+n\\= & {} \frac{nU}{\varepsilon V}+n. \end{aligned}$$

We deduce that $Q^{(0)}\le \Big \lfloor \frac{nU}{\varepsilon V}\Big \rfloor +n:=U^{(0)}$.

In the algorithm DP-R1 for the problem KG-R1, partial solutions $x=(x_1,\ldots ,x_j)$ are constructed for $j\in [1,n]$. With each partial solution x, state (j, Q) is associated, where $Q=\sum _{h\in [1,j]} \Big \lceil \frac{f_h(x_h)}{\delta }\Big \rceil$ is the current value of the scaled and rounded profit. Constraint function G(j, Q) is recursively calculated for each state (j, Q), which is the minimum value of $\sum _{h\in [1,j]}g_h(x_h)$ over partial solutions x in the same state (j, Q). A partial solution with value G(j, Q) dominates all other partial solutions in the state (j, Q) in the sense that if there is a partial solution in this state that can be extended to an optimal solution of KG-R1, then the dominant solution can also be extended to an optimal solution of KG-R1. Therefore, only the dominant solution can be left for each state, and non-dominant solutions can be eliminated.

Algorithm DP-R1. The initialization is $G(0,0)=0$, and $G(0,Q)=B+1$ for $(j,Q)\ne (0,0)$, $j\in [1,n]$, $Q=0,1,\ldots ,U^{(0)}$. The recursion for $j\in [1,n]$, $Q=0,1,\ldots ,U^{(0)}$, is

$$\begin{aligned} G(j,Q)=\min _{x_j\in R_j}\Big \{G\Big (j-1,{ Q}- \Big \lceil \frac{f_j(x_j)}{\delta }\Big \rceil \Big )+g_j(x_j)\Big \}. \end{aligned}$$

The optimal objective function value of the problem KG-R1 is equal to

$$\begin{aligned} Q^{(0)}=\max \{Q\mid G(n,Q)\le B, Q=0,1,\ldots ,U^{(0)}\}, \end{aligned}$$

and the corresponding optimal solution can be found by tracing back optimal solutions of the recursive equation. The recursive equation can be solved in $O(|R_j|)=O\Big (\frac{nU}{\varepsilon V}\Big )$ time for each state (j, Q). Therefore, the running time of the algorithm DP-R1 is $O\Big (\frac{n^3U^2}{\varepsilon ^2 V^2}\Big )$.

Kovalev (2021) describes a procedure to improve lower and upper bounds for a minimization problem if an approximation algorithm satisfying certain properties is available. It is given in the Appendix for completeness. The bound improvement procedure with algorithm DP-R1 incorporated in it runs in $O(n^3\log _2\frac{U}{V})$ time and delivers number L such that $L\le F^*\le 4L$ for the problem KG1. With lower and upper bounds $V:=L$ and $U:=4L$, algorithm DP-R1 runs in $O\left( \frac{n^3}{\varepsilon ^2}\right)$ time. Therefore, the overall running time of the FPTAS for KG1 is $O \left( n^3\log _2 \frac{U}{V}+\frac{n^3}{\varepsilon ^2}\right)$. For KG1, the lower bound can be calculated as $V=\max _{j\in [1,n]}\{f_j(x^0_j)\}$, where $x^0_j=\min \{d_j,\max \{x_j\mid g_j(x_j)\le B\}\}$, $j\in [1,n]$. In this case, the corresponding upper bound is $U=nV$, and the running time of the FPTAS for KG1, and hence, for K1, is $O(n^3\log _2 n+\frac{n^3}{\varepsilon ^2})$.

Similar ideas – a generic problem KG2, a scaled and rounded problem KG-R2, a dynamic programming algorithm for KG-R2, which constitutes an FPTAS for KG2, and a bound improvement procedure – are used to develop an FPTAS for the minimization problem K2.

Generic problem KG2:

$$\begin{aligned} \min _{x} \sum _{j\in [1,n]} g_j(x_j), \text{ subject } \text{ to } \sum _{j\in [1,n]} f_j(x_j)\ge C,\ x_j\in [0,d_j],\ j\in [1,n]. \end{aligned}$$

Let $x^*$ now denote an optimal solution of the problem KG2, and let $G^*$ denote its optimal objective function value. Assume that numbers S and T are known such that $0<S\le G^*\le T$. Define $\delta =\varepsilon S/n$.

Scaled and rounded problem KG-R2:

$$\begin{aligned} \min _{x} \sum _{j\in [1,n]} \Big \lfloor \frac{g_j(x_j)}{\delta }\Big \rfloor , \text{ subject } \text{ to } \sum _{j\in [1,n]} f_j(x_j)\ge C,\ x_j\in H_j,\ j\in [1,n], \end{aligned}$$

where

$$\begin{aligned} H_j= & {} \Big \{h_j(0),h_j(1),\ldots ,h_j\Big (\Big \lfloor \frac{T}{\delta }\Big \rfloor \Big )\Big \}, \\ h_j(s)= & {} \max \Big \{ x\mid x\in [0,d_j],\ \Big \lfloor \frac{g_j(x)}{\delta }\Big \rfloor =s\Big \}\\= & {} \max \{ x\mid x\in [0,d_j],\ g_j(x)<(s+1)\delta \},\ j\in [1,n]. \end{aligned}$$

Assume that $h_j(s)$ is calculated in a constant time for any s. In the problem K2, $g_j(x)=x$ and $h_j(s)=\min \{d_j,\lceil (s+1)\delta \rceil -1\}$. Let $x^{(0)}$, $P^{(0)}$ and $G^{(0)}$ denote an optimal solution, its objective function value with respect to the problem KG-R2 and its objective function value with respect to the problem KG2, respectively. We have

$$\begin{aligned} G^{(0)}= & {} \sum _{j\in [1,n]} g_j(x^{(0)}_j)=\delta \sum _{j\in [1,n]} \frac{g_j(x^{(0)}_j)}{\delta }< \delta \sum _{j\in [1,n]} \Big (\Big \lfloor \frac{g_j(x^{(0)}_j)}{\delta }\Big \rfloor +1\Big )\\\le & {} [ x^{(0)} \text{ is } \text{ optimal } \text{ for } {KG}\text {-}{R2} ] \\\le & {} \delta \sum _{j\in [1,n]} \Big (\Big \lfloor \frac{g_j(x^*_j)}{\delta }\Big \rfloor +1\Big )\le \sum _{j\in [1,n]} g_j(x^*_j)+n\delta =G^*+n\delta =G^*+\varepsilon S. \end{aligned}$$

Thus, $G^{(0)}-G^*<\varepsilon G^*$. Let us evaluate $P^{(0)}$ from above.

$$\begin{aligned} P^{(0)}=\sum _{j\in [1,n]} \Big \lfloor \frac{g_j(x^{(0)})}{\delta }\Big \rfloor \le \sum _{j\in [1,n]} \Big \lfloor \frac{g_j(x^*)}{\delta }\Big \rfloor \le \sum _{j\in [1,n]} \frac{g_j(x^*)}{\delta }=\frac{G^*}{\delta }\le \frac{T}{\delta }=\frac{nT}{\varepsilon S}. \end{aligned}$$

We deduce that $P^{(0)}\le \Big \lfloor \frac{nT}{\varepsilon S}\Big \rfloor :=T^{(0)}$.

In the algorithm DP-R2 for the problem KG-R2, partial solutions $x=(x_1,\ldots ,x_j)$ are constructed for $j\in [1,n]$. With each partial solution x, a state (j, P) is associated, where $P=\sum _{h\in [1,j]} \Big \lfloor \frac{g_h(x_h)}{\delta }\Big \rfloor$ is the current value of the scaled and rounded cost. Dominance function F(j, P) is recursively calculated for each state (j, P), which is the maximum value of $\sum _{h\in [1,j]}f_h(x_h)$ over partial solutions x in the same state (j, P).

Algorithm DP-R2. The initialization is $F(0,0)=0$, and $F(0,P)=-\sum _{j\in [1,n]}$ $\Big \lfloor \frac{g_j(d_j)}{\delta }\Big \rfloor$ for $(j,P)\ne (0,0)$, $j\in [1,n]$, $P=0,1,\ldots ,T^{(0)}$. The recursion for $j\in [1,n]$, $P=0,1,\ldots ,T^{(0)}$, is

$$\begin{aligned} F(j,P)=\max _{x_j\in H_j}\Big \{F\Big (j-1,P- \Big \lfloor \frac{g_j(x_j)}{\delta }\Big \rfloor \Big )+f_j(x_j)\Big \}. \end{aligned}$$

The optimal objective function value of the problem KG-R2 is equal to

$$\begin{aligned} P^{(0)}=\min \{P\mid F(n,P)\ge C, P=0,1,\ldots ,T^{(0)}\}, \end{aligned}$$

and the corresponding optimal solution can be found by tracing back optimal solutions of the recursive equation. The running time of the algorithm DP-R2 is $O\Big (\frac{n^3T^2}{\varepsilon ^2 S^2}\Big )$.

Kovalyov (1995) describes a procedure to improve lower and upper bounds for a minimization problem if an approximation algorithm satisfying certain properties is available. The bound improvement procedure with algorithm DP-R2 incorporated in it runs in $O(n^3\log _2\frac{T}{S})$ time and delivers number L such that $L\le F^*\le 3L$ for the problem KG2. With lower and upper bounds $S:=L$ and $T:=3L$, algorithm DP-R2 runs in $O(\frac{n^3}{\varepsilon ^2})$ time. Therefore, the overall running time of the $\varepsilon$-approximation algorithm for KG2 is $O(n^3\log _2\frac{T}{S}+\frac{n^3}{\varepsilon ^2})$.

For KG2, the lower and upper bounds can be calculated as $S=g_{\min }$ and $T=ng_{\max }$, where $g_{\min }=\min _{j\in [1,n]}\{g_j(1)\}$ and $g_{\max }=\max _{j\in [1,n]}\{g_j(d_j)\}$. In this case, the running time of the $\varepsilon$-approximation algorithm for KG2 is $O\left( n^3\log _2 \frac{ng_{\max }}{g_{\min }}+\frac{n^3}{\varepsilon ^2}\right)$. For K2, it becomes $O(n^3\log _2(n d_{\max })+\frac{n^3}{\varepsilon ^2})$, which means that this algorithm constitutes an FPTAS for K2.

Remark 1

The problem K1 can be solved in $O(nB^2)$ time by a dynamic programming algorithm similar to DP-R1, in which the roles of the dominance function and the state variable are switched. Namely, value $b:=\sum _{h\in [1,j]} x_h\in [0,B]$ is the state variable and $F(j,b):=\sum _{h\in [1,j]} f_h(x_h)$ is the dominance function to be maximized. The problem K2 can be solved in $O((\sum _{j\in [1,n]}d_j)^2)$ time by the algorithm DP-R2, in which $g_j(x_j)=x_j$, $j\in [1,n]$, and $\delta =1$. Thus, both problems K1 and K2 are pseudo-polynomially solvable.

3.3 Bottleneck problems

The following bottleneck counterparts of the problems K1 and K2 can be of interest. Let E be a given number, $0\le E\le 1$.

Consider the problem K2B and define $f^{(-1)}_j(E)=\min \{x_j\mid f_j(x_j)\ge E, x_j\in [0,d_j]\},\ j\in [1,n]$. It is obvious that the vector $x^*$ in which $x^*_j=f^{(-1)}_j(E)$, $j\in [1,n]$, is optimal for K2B. Therefore, this problem can be solved in O(n) time, provided that the value $f^{(-1)}_j(E)$ is computable in a constant time for any $j\in [1,n]$.

Consider the problem K1B. Assume that the difference between any two distinct values $f_j(x_j)$, $j=1,\ldots ,n$, is at least $\frac{1}{\delta }$ for a positive integer $\delta$, and that the value $f^{(-1)}_j(A)$ is computable in a constant time for any $j\in [1,n]$ and A. In this case, the problem K1B can be solved in $O(n\log _2 \delta )$ time by a bisection search in the interval [0, 1] of the optimal objective function value $F^*$ of this problem. In each iteration of this search, the relation $\sum _{j\in [1,n]}f^{(-1)}_j(A)\le B$ is verified for a trial value A, $LB\le A\le UB$, starting with lower bound $LB=0$ and upper bound $UB=1$. If the mentioned relation is satisfied, then $F^*\ge A$, else $F^*<A$. The lower and upper bounds LB and UB are re-set accordingly. The procedure stops when $UB-LB<\frac{1}{\delta }$, in which case the vector $x^*$ with $x^*_j=f^{(-1)}_j(LB)$, $j\in [1,n]$, is optimal for K1B.

4 Conclusions and suggestions for future research

The following results are obtained:

• an O(n) time algorithm for the problem K1, provided that the profit function $f_j(x_j)$ is convex non-decreasing and computable in a constant time for any $x_j\in [0,d_j]$ and $j\in [1,n]$,

• an O(n) time algorithm for the problem K2, provided that the profit function $f_j(x_j)$ is convex non-decreasing and the minimum pseudo-inverse $f^{(-1)}_j(A)$ is computable in a constant time for any A and $j\in [1,n]$,

• an $O(n\log _2 \delta )$ time algorithm for the problem K1B, provided that the profit function $f_j(x_j)$ is non-negative non-decreasing and the difference between any two distinct values $f_j(x_j)$, $j\in [1,n]$, is at least $\frac{1}{\delta }$ for a positive integer $\delta$, and that the value $f^{(-1)}_j(A)$ is computable in a constant time for any A and $j\in [1,n]$,

• an O(n) time algorithm for the problem K2B, provided that the profit function $f_j(x_j)$ is non-negative non-decreasing and the value $f^{(-1)}_j(E)$ is computable in a constant time for any $j\in [1,n]$,

• proof of NP-hardness of the problems K1 and K2 with arbitrary non-negative non-decreasing profit functions, and

• FPTASes with running times $O(n^3\log _2 n+\frac{n^3}{\varepsilon ^2})$ and $O(n^3\log _2(n d_{\max })+\frac{n^3}{\varepsilon ^2})$ for the problems K1 and K2, respectively, provided that the profit function $f_j(x_j)$ is arbitrary non-negative non-decreasing and the value $f^{(-1)}_j(A)$ is computable in a constant time for any A and $j\in [1,n]$.

For future research, it is worth to establish computational complexity of the problems K1 and K2 with concave non-decreasing profit functions and to study theoretically and practically interesting modifications of K1 and K2.

Appendix. Bound improvement procedure

The procedure calculates numbers B and C such that $B\le F^*\le C$ and $C\le 4B$. For a maximization problem with optimum value $F^*$, let lower and upper bounds $V'$ and $U'$ be given such that $0<V'\le F^*\le U'$. Compute integer number k satisfying $2^{k-1}V'<U'\le 2^kV'$. We have $V'\le F^*\le 2^kV'$ and $k=O\left( \log _2\frac{U'}{V'}\right)$. For $q=k,k-1,\ldots ,1$, apply an approximation algorithm for the maximization problem which finds a feasible solution with value $F^{(q)}\ge F^*-2^{q-2}V'$ if $F^*\le 2^qV'$. If $F^*>2^qV'$, then the algorithm can still find a feasible solution with value $F^{(q)}\ge F^*-2^{q-2}V'$, but it is not guaranteed. For the problem KG1, algorithm DP-R1 with $\varepsilon =1/2$, $U=2^qV'$ and $V=2^{q-1}V'$ is such an algorithm because it finds a solution with value $F^0\ge F^*-\varepsilon V=F^*-\frac{1}{2}V=F^*-2^{q-2}V'$ if $F^*\le U=2^qV'$. For the problem KG1, it runs in $O(n^3)$ time. Since $F^*\le 2^kV'$, a feasible solution with value $F^{(k)}\ge F^*-2^{k-2}V'$ will be found. If $F^{(k)}\ge 2^{k-2}V'$, then $2^{k-2}V'\le F^{(k)}\le F^*\le 2^kV'$. Hence, $B=F^{(k)}$, $C=2^kV'$, and the procedure stops. If $F^{(k)}<2^{k-2}V'$, then $F^*\le F^{(k)}+2^{k-2}V'<2^{k-1}V'$, and we can re-set $k:=k-1$. Therefore, $B=F^{(t)}$ and $C=2^tV'$, where t is the largest index such that $k\ge t\ge 1$ and $F^{(t)}\ge 2^{t-2}V'$. Such an index t exists. Assume that it does not exist for all iterations up to the iteration in which k is re-set to 1. Since this iteration is reached, relations $F^{(2)}<2^0V'$ and $F^*\le F^{(2)}+2^0V'<2L'$ are satisfied. Furthermore, $V'\le F^*$ by the definition of $V'$. Hence, $V'\le F^*\le 2V'$, and for $t=1$ we have $F^{(1)}\ge F^*-2^{-1}V'\ge 2^{-1}L'$, as it is required by the definition of t. Note that if $t=1$, then $C/B=2$. For the problem KG1, since $0<V\le F^*\le nV$, the number of iterations of the bound improvement procedure is at most $O(\log _2 n)$ and its overall running time is $O(n^3\log _2 n)$.