An FPTAS for the parametric knapsack problem
Michael Holzhauser Sven O. Krumke






TUKL]Michael Holzhausercor1
holzhauser@mathematik.uni-kl.de

TUKL]Sven O. Krumke
krumke@mathematik.uni-kl.de

[cor1]Corresponding author. Fax: +49 (631) 205-4737. Phone: +49 (631) 205-2511

[TUKL]University of Kaiserslautern, Department of Mathematics

  Paul-Ehrlich-Str. 14, D-67663 Kaiserslautern, Germany



	
	In this paper, we investigate the parametric knapsack problem, in which the item profits are affine functions depending on a real-valued parameter. The aim is to provide a solution for all values of the parameter. It is well-known that any exact algorithm for the problem may need to output an exponential number of knapsack solutions.

	We present a fully polynomial-time approximation scheme (FPTAS) for the problem that, for any desired precision ε∈ (0,1), computes (1-ε)-approximate solutions for all values of the parameter. This is the first FPTAS for the parametric knapsack problem that does not require the slopes and intercepts of the affine functions to be non-negative but works for arbitrary integral values. Our FPTAS outputs (n^2/ε) knapsack solutions and runs in strongly polynomial-time (n^4/ε^2). Even for the special case of positive input data, this is the first FPTAS with a strongly polynomial running time. We also show that this time bound can be further improved to (n^2/ε· A(n,ε)), where A(n,ε) denotes the running time of any FPTAS for the traditional (non-parametric) knapsack problem.



	knapsack problems parametric optimization approximation algorithms









§ INTRODUCTION



The knapsack problem is one of the most fundamental combinatorial optimization problems: Given a set of n items with weights and profits and a knapsack capacity, the task is to choose a subset of the items with a maximum profit such that the weight of these items does not exceed the knapsack capacity. The problem is known to be weakly -hard and solvable in pseudo-polynomial time. Moreover, several constant factor approximation algorithms and approximation schemes have been developed for the problem <cit.> (cf. <cit.> for an overview).

In this paper, we investigate a generalization of the problem in which the profits are no longer constant but affine functions depending on a parameter λ∈ℝ. More precisely, for a knapsack with capacity W and for each item i in the item set {1,…,n} with weight w_i ∈ℕ_> 0, the profit p_i is now of the form p_i(λ)  a_i + λ· b_i with a_i,b_i ∈ℤ. The resulting optimization problem can be stated as follows:

    p^*(λ) = max    ∑_i=1^n (a_i + λ· b_i) · x_i 
       ∑_i=1^n w_i · x_i ≤ W 
        x_i ∈{0,1}  ∀ i ∈{1,…,n}

The aim of this parametric knapsack problem is to return a partition of the real line into intervals (-∞,λ_1], [λ_1,λ_2], …, [λ_k-1,λ_k], [λ_k,+∞) together with a solution x^* for each interval such that this solution is optimal for all values of λ in the interval. The function mapping each λ∈ℝ to the profit of the corresponding optimal solution is called the optimal profit function and will be denoted by p^*(λ) in the following. It is easy to see that p^* is continuous, convex, and piecewise linear with breakpoints λ_1,…,λ_k <cit.>.

Clearly, since the parametric knapsack problem is a generalization of the traditional (non-parametric) knapsack problem, it is at least as hard to solve as the knapsack problem. In fact, it was shown that, even in the case of integral input data, the minimum number of breakpoints of the optimal profit function can be exponentially large, so any exact algorithm may need to return an exponential number of knapsack solutions <cit.>. In this paper, we are interested in a fully polynomial time approximation scheme for the parametric knapsack problem. We will show that, for any desired precision ε∈ (0,1), a polynomial number of intervals suffices in order to be able to provide a (1-ε)-approximate solution for each λ∈ℝ.

Without loss of generality, we may assume that w_i ≤ W for each i ∈{1,…,n} since otherwise we are not able to chose item i at all. However, note that we do not set any further restrictions on the profits, i.e., the parameters a_i and b_i. In particular, each profit may become negative for some specific value of λ. It is even possible that there a no profitable items at all for some values of λ.



 §.§ Previous work


A large number of publications investigated parametric versions of well-known problems. This includes the parametric shortest path problem <cit.>, the parametric minimum spanning tree problem <cit.>, the parametric maximum flow problem <cit.>, and the parametric minimum cost flow problem <cit.> (cf. <cit.> for an overview). The parametric knapsack problem considered here was first investigated by <cit.>. She showed that the number of breakpoints of the optimal profit function can become exponentially large in general. If the parameters are integral, the number of breakpoints can still attain a pseudo-polynomial size. The first specialized exact algorithm for the problem was presented by <cit.>, who showed that the problem can be solved in (knW) time, where k denotes the number of breakpoints of the optimal profit function p^*.

The first approximation scheme for the problem was recently published by <cit.>. The authors presented a generalization of the standard polynomial-time approximation scheme for the knapsack problem, resulting in a PTAS for the problem with a running time in (1/ε^2· n^1/ε+2). In the special case of positive values of λ as well as non-negative values of a_i and b_i for each i ∈{1,…,n}, the authors show that an algorithm of <cit.> for the bicriteria knapsack problem can be used to obtain an FPTAS for the parametric knapsack problem running in (n^3/ε^2·log^2 UB_max) time, where UB_max denotes an upper bound on the maximum possible profit with respect to both of the profit functions ∑_i=1^n a_i · x_i and ∑_i=1^n b_i · x_i.



 §.§ Our contribution


We present the first FPTAS for the parametric knapsack problem without the restriction to non-negative input data. In particular, we show that we only need a total number of (n^2/ε) intervals to approximate the problem (which, itself, may need an exponential number of intervals as described above) and that we can compute an approximate solution for each interval in (n^2/ε) time, yielding an FPTAS with a strongly polynomial running time of (n^4/ε^2). Our algorithm is the first FPTAS for the problem with a strongly polynomial running time, being superior to the PTAS of <cit.> for ε≤ 0.5 and, in the special case of positive input data, superior to their FPTAS for large input values. In a second step, we improve this result to a running time of (n^2/ε· A(n,ε)), where A(n,ε) denotes the running time of any FPTAS for the traditional knapsack problem. Using the FPTAS of <cit.>, this yields a time bound of ( n^3/εlog1/ε + n^2/ε^4log^2 1/ε) for the parametric knapsack problem.



 §.§ Organization


The results of this paper are divided into three main parts. In Section <ref>, we show how we can generalize the well-known greedy-like 1/2-approximation algorithm for the traditional knapsack problem to the parametric setting and how the resulting profit function can be “smoothened” such that it becomes convex and continuous without losing the approximation guarantee. This will be the key ingredient for the parametric FPTAS, which will be presented in Section <ref>. We will first recapitulate a basic FPTAS for the traditional knapsack problem in Section <ref> and then extend it to the parametric case in Section <ref>, presenting a first time bound for the resulting FPTAS. In Section <ref>, as a main result of the paper, we present an improved analysis yielding the claimed running time of the FPTAS. Finally, in Section <ref>, we show that is suffices to solve the corresponding subproblems only approximately so that we can incorporate traditional FPTASs, which improves the running time of our algorithm to the claimed one.






§ OBTAINING A PARAMETRIC 1/2-APPROX­IMATION



The parametric FPTAS will rely on a convex and continuous 1/2-approximation of the optimal profit function p^*(λ), i.e., a parametric 1/2-approximation algorithm for the parametric knapsack problem. We will therefore present such an algorithm in this section and describe how we can guarantee these properties of the function.



 §.§ Traditional 1/2-approximation algorithm



The basic (non-parametric) 1/2-approximation algorithm proceeds as follows: In a first step, the algorithm sorts the items in decreasing order of their ratios p_i/w_i, which can be done in (n log n) time. It then packs the items in this ordering until the next item k with k ≥ 2 would violate the knapsack capacity (or until there are no items left), yielding a feasible solution x'. The algorithm either returns x' or, if better, the solution containing only an item with the largest profit p^(max). If x^* denotes an optimal solution to the given knapsack instance, x^A the solution returned by the above algorithm, and x^LP a solution to the LP-relaxation of the problem, we get that

    p^A  p(x^A)    ∑_i=1^n p_i · x^A_i = max{ p^(max), ∑_i=1^k-1 p_i }
       ≥1/2·∑_i=1^k p_i ≥1/2· p(x^LP) ≥1/2· p(x^*),

so x^A is a 1/2-approximation. We refer to <cit.> for further details on this standard algorithm.



 §.§ Parametric 1/2-approximation algorithm



In the parametric knapsack problem, the profits are affine functions of the form p_i(λ) = a_i + λ· b_i such that the optimal profit p^* changes with λ. However, note that the solution x' of the traditional 1/2-approximation algorithm only depends on the ordering of the items and, thus, remains constant as long as this ordering does not change. Moreover, two items can only change their relative ordering if their profit functions intersect, yielding (n^2) intervals I'_j, within which the ordering of the items remains unchanged. For all values of λ in such an interval I'_j, the algorithm computes the same solution x', which has a profit of the form p^(j)(λ) α^(j) + λ·β^(j). For each λ∈ I'_j, the 1/2-approximation algorithm either returns x' with profit p^(j)(λ) or the most valuable item only. One possibility to obtain a parametric 1/2-approximation algorithm would be to consider each interval I'_j separately and to divide it into subintervals, depending on whether p^(j)(λ) or p^(max)(λ) is larger, where p^(max) denotes the profit of the most valuable item (which, again, now depends on λ). However, the resulting piecewise linear function p^A(λ) is not necessarily continuous or convex, which will be required later, though (see Figure <ref>).

Instead, we ignore the intervals I'_j and only consider the above affine functions p^(j)(λ) = α^(j) + λ·β^(j). Let S denote the set of all such functions together with the function p^(0)(λ)  0 and each profit function p_i(λ). By computing the upper envelope of the (n^2) functions in S, we obtain a function φ, which is based on feasible solutions whose profit is not smaller than p^A(λ) at each λ∈ℝ (see the dotted curve in Figure <ref>). By standard arguments, it follows that φ is convex, piecewise linear, and continuous as it is the pointwise maximum of affine functions. For m functions, the upper envelope can be computed in (m log m) time as shownby <cit.>. Within the same time bound, we can sort the resulting intervals by increasing values of their left boundary. Hence, we obtain a piecewise linear, continuous, and convex 1/2-approximation φ with (n^2) breakpoints in (n^2 log n) time. In the following, we will refer to the intervals between the breakpoints of φ as I_1,…,I_q.
Strictly speaking, the author proves the result for finite line segments and not for straight lines. However, it is easy to compute upper and lower bounds for the smallest and largest possible intersection point of two of the involved functions, respectively, and to reduce the problem to the resulting interval.








§ OBTAINING A PARAMETRIC FPTAS



Before we explain the parametric FPTAS in detail, we first recapitulate the basic FPTAS for the traditional (non-parametric) knapsack problem as introduced by <cit.> since its way of proceeding is crucial for the understanding of the parametric version.



 §.§ Traditional FPTAS



Consider the case of some fixed value for λ, such that the profits have a constant, but possibly negative value p_i. The basic FPTAS for the traditional knapsack problem is based on a well-known dynamic programming scheme, which was originally designed to solve the problem exactly in pseudo-polynomial time: Let P denote an upper bound on the maximum profit of a solution to the given instance. For k ∈{0,…,n} and p ∈{0,…,P}, let w(k,p) denote the minimum weight that is necessary in order to obtain a profit of exactly p with those items in the item set {1,…,k} that have a non-negative[Note that items with a negative profit will not be present in an optimal solution.] profit. For k=0, we set w(0,p) = 0 for p=0 and w(0,p) = W+1 for p > 0. For k ∈{1,…,n} and for the case that p_k ∈{0,…,p}, we compute the values w(k,p) recursively by w(k,p) = min{w(k-1,p), w(k-1,p-p_k) + w_k}, representing the choice to either not pack the item or to pack it, respectively. Else, if p_k ∉{0,…,p}, we set w(k,p) = w(k-1,p) since we can omit negative item- and knapsack-profits. The largest value of p such that w(n,p) ≤ W then yields the optimal solution to the problem. The procedure runs in pseudo-polynomial time 𝒪(nP).

The idea of the basic FPTAS is to scale down the item profits p_i to new values _i p_i/M, where M ε·øp/n for some value øp fulfilling 1/2· p^* ≤øp≤ p^*. Instead of setting øp p^A as it is done in the traditional FPTAS, we can alternatively use our improved 2-approximate solution φ. Since the maximum possible profit P is then given by

    P≤∑_i=1^n _i ≤∑_i=1^n n · p_i/ε·φ≤n/ε·p^*/φ≤2n/ε,

the procedure runs in polynomial time (n^2/ε). The crucial observation is that we only lose a factor of (1-ε) by scaling down the profits, so the solution obtained by the above dynamic programming scheme applied to the scaled profits yields a (1-ε)-approximate solution for the problem (see <cit.> for further details on the algorithm).




 §.§ Parametric scaling



Although the parametric FPTAS is based on the basic FPTAS, the instance parameters now depend on λ and, thus, change while λ increases. In particular, both the item profits and φ now depend on λ, so the scaled profits _i(λ) n · p_i(λ)/ε·φ(λ) have a highly non-linear behavior. Nevertheless, similar to the parametric 1/2-approximation considered in Section <ref>, the solution returned by the FPTAS does not change as long as the profit _i(λ) of each item remains constant. Hence, if I'_j denotes an interval such that the scaled profits _i remain constant for each λ∈ I'_j, we can evaluate the dynamic programming scheme with the profits _i to obtain a (1-ε)-approximate solution for the interval I'_j. The proof of the polynomial running time and the approximation guarantee remain unchanged.

It remains to show how we can divide the real line into a polynomial number of intervals such that the profits remain constant in each interval. The basic FPTAS will then be evaluated for each such interval subsequently (using the corresponding constant scaled profits) in order to obtain (1-ε)-approximate solutions for the whole real line.

One natural idea would be to build on those intervals described in Section <ref> for which φ(λ) behaves like an affine function: Let I_1,…,I_q with q ∈𝒪(n^2) denote the affine segments of φ such that, for each j ∈{1,…,q}, the function φ takes on some affine form φ(λ) = α^(j) + λ·β^(j) for λ∈ I_j.

Now consider one such interval I_j. If φ(λ) = 0 for λ∈ I_j, it also holds that p^*(λ) = 0 since φ(λ) ≥1/2· p^*(λ) for λ∈ℝ, so the all-zero solution is optimal. Otherwise, for the non-rounded scaled profit of each item i, it holds that

    n · p_i(λ)/ε·φ(λ) = n · (a_i + λ· b_i)/ε· (α^(j) + λ·β^(j))n/ε· f_i(λ).

These functions f_i are monotonous, since the first derivative fulfills

    df_i/dλ (λ)    = b_i · (α^(j) + λ·β^(j)) - (a_i + λ· b_i) ·β^(j)/(α^(j) + λ·β^(j))^2
       = b_i ·α^(j) - a_i ·β^(j)/(α^(j) + λ·β^(j))^2

and, thus, does not change its sign within I_j. Hence, within the interval I_j, each scaled profit _i has a monotone behavior. Moreover, it holds that 0 ≤ f_i(λ) ≤ 2 for all λ∈ I_j since each item either has a non-negative profit within the whole interval or it will be ignored and since p_i(λ) ≤ p^*(λ) ≤ 2 ·φ(λ). These observations yield that each scaled profit _i changes its (integral) value at most (n/ε) times within I_j since we only need to consider values for _i between 0 and 2n/ε. Hence, the above recursive formulae only change (n^2/ε) times within each I_j, in which case we have to repeat the computation of the values w(i,p). This yields a total computational overhead of (n^4/ε^2) per interval and, since there are at most 𝒪(n^2) intervals, a total running time of (n^6/ε^2) for the parametric FPTAS. This running time will be significantly improved in the next subsection.

It should be noted that we need to take care of a proper definition of the returned intervals: For example, consider two scaled profits of the forms _i = 1 + λ and _j = 1 - λ. For the critical value λ_1 = 1, both profits evaluate to 1. However, for λ_1' λ_1 + δ and λ_1”λ_1 - δ for a small value of δ, one of the profits already changes its integral value and the dynamic programming scheme may behave differently. One simple solution is to assess that we add a single-point interval [λ_1,λ_1] for each critical value as well as two open intervals of the forms (λ_0,λ_1) and (λ_1,λ_2), where λ_0 and λ_2 are adjacent critical values. The returned (ordered) sequence of intervals then alternates between single-point intervals and open intervals. For an open interval, we can obtain an approximate solution by setting λ to the middle point of the interval and performing the dynamic program for the corresponding constant scaled profits.










 §.§ Improved Analysis



The major drawback of the above algorithm is that we basically need to reset the whole procedure whenever the function φ changes its behavior. With this approach, we were able guarantee that each scaled profit has a monotone behavior such that each possible integral value is only attained at most once per interval. As it will be shown in this Section, we are somewhat allowed to “ignore” these changes without losing the guarantee that each possible value of the scaled profits will only be attained a constant number of times.


	For each item i ∈{1,…,n}, the scaled profits _i(λ) attain each value in { 0, …, 2n/ε} at most three times as λ increases from -∞ to +∞.



	In order to prove the claim, it suffices to show that the sign of the first derivative of each function f_i changes at most twice while λ increases. As above, let I_1,…,I_q denote the intervals for which φ takes on some affine form φ(λ) = α^(j) + λ·β^(j) such that
	
    f_i(λ) = a_i + λ· b_i/α^(j) + λ·β^(j)

	for λ∈ I_j. Since φ is convex and continuous, it holds that β^(j)≤β^(j+1) for j ∈{1,…,q-1} and that there is some index h such that α^(j)≤α^(j+1) for j ∈{1,…,h} and α^(j)≥α^(j+1) for j ∈{h+1,…,q-1}. In fact, due to the construction of the intervals, these inequalities hold in the strict sense since β^(j) = β^(j+1) would also imply that α^(j) = α^(j+1) by continuity of φ, so both segments would belong to the same interval. Hence, if we plot the points (β^(j),α^(j))^T into a b-a-space, we get a picture as shown in Figure <ref>. Moreover, for each j ∈{1,…,q-1}, there is some λ_j ∈ℝ with
	
    α^(j) + λ_j ·β^(j) = α^(j+1) + λ_j ·β^(j+1)

	due to the continuity and construction of φ. Hence, since β^(j+1) = β^(j) + δ_j for some value δ_j > 0, we get that
	
    α^(j+1)   = α^(j) + λ_j ·β^(j) - λ_j ·β^(j+1)
       = α^(j) - λ_j ·δ_j,

	so the slope of the line that connects the points (β^(j),α^(j))^T and (β^(j+1),α^(j+1))^T evaluates to
	
    α^(j+1) - α^(j)/β^(j+1) - β^(j) = -λ_j ·δ_j/δ_j = -λ_j

	and, thus, decreases while j increases. This yields that the piecewise linear function g connecting each of the points (β^(j),α^(j))^T in the order j=1,…,q is concave(as illustrated by the highlighted area in Figure <ref>).

	This can also be seen by arguments used in the field of computational geometry: It is known that the upper envelope of a set of affine functions of the form c ·λ - d corresponds to the lower surface of a convex hull in the dual space, which is clearly convex. Such a dual space contains a point (c,d)^T for each affine function of the above form in the primal space and, conversely, an affine function λ· c - μ for each point (λ,μ)^T in the primal space. Hence, each line segment (breakpoint) of our upper envelope corresponds to a corner point (line segment) of the lower surface of a convex hull in the dual space (cf. <cit.>). In fact, Figure <ref> shows the dual space mirrored at the b-axis.

	Now, for some specific item i ∈{1,…,n}, consider the first derivate of f_i, which as we have seen evaluates to
	
    df_i/dλ(λ) = b_i ·α^(j) - a_i ·β^(j)/(α^(j) + λ·β^(j))^2

	as shown above. Since the denominator is always positive, we need to bound the number of times the sign of the numerator changes. The value b_i ·α^(j) - a_i ·β^(j) can be interpreted as the inner product of the vectors (-a_i,b_i) and (β^(j),α^(j))^T. Hence, since (-a_i,b_i) · (b_i,a_i)^T = 0, the sign of the derivate changes whenever the function g crosses the line going through the origin and the point (b_i,a_i)^T (see the dotted line in Figure <ref>). Since g is concave as shown above, this can happen at most two times while λ increases, which yields the claim.




Theorem <ref> shows that each possible profit is only attained a constant number of times per item although the involved functions f_i are rational functions whose denominator changes for increasing λ. Hence, each item only creates (n/ε) subintervals as opposed to the (n^2 ·n/ε) subintervals proven in Section <ref>. It remains to show that we can determine these subintervals efficiently.

As shown in the proof of Theorem <ref>, the slope of each function f_i changes at most twice, yielding for each item up to three partitions of the set of intervals I_1,…,I_q such that f_i is monotonous within each partition. By scanning through the sequence of intervals of φ, we can determine these three partitions for all items in total time (n · n^2) = (n^3). For each item, each partition, and each possible scaled profit in {0,…,2n/ε} (which can be attained only once in the partition), we perform a binary search on the intervals in the partition in order to find a value for λ at which the corresponding profit is attained, if such a λ exists. This can be done in (n · 3 ·n/ε·log n^2) = (n^2/ε·log n) time in total. Finally, we need to sort this list of critical values of λ in order to determine the subintervals of the FPTAS, which can be done in (n ·n/ε·log (n ·n/ε)) = (n^2/ε·logn/ε) time.

In summary, we need (n^3 + n^2/ε·logn/ε) time to determine the (n^2/ε) subintervals of the FPTAS. For each of these subintervals, we need to perform the traditional FPTAS with the corresponding (constant) scaled profits, which can be done in (n^2/ε) time each. Hence, we obtain an FPTAS for the parametric knapsack problem running in (n^4/ε^2) time in total. This yields the main result of this paper:


	There is an FPTAS for the parametric knapsack problem running in strongly polynomial time (n^4/ε^2). 







§ COMBINING FPTASS



In the previous section, we have seen that the parametric knapsack problem can be divided into (n^2/ε) subproblems, for which we need to provide (1 - ε)-approximate solutions. These subproblems were created in a way such that the scaled profits are constant for each subproblem. Each of them can be seen as a new, independent, and non-parametric knapsack instance (albeit a special one, since the profits are now of polynomial size). In Section <ref>, we simply solved each of the resulting knapsack instances exactly in 𝒪(n^2/ε) time. The main observation of this section is that we actually do not necessarily need to solve the subproblems exactly – it suffices to solve them up to a factor of (1 - ε) using any FPTAS for the traditional knapsack problem.

Consider one fixed interval I' of the (n^2/ε) subintervals of the problem. For each λ∈ I', the scaled profits _i take on constant values. Moreover, it holds that 1/2· p^*(λ) ≤φ(λ) ≤ p^*(λ) for any λ∈ I' as shown in Section <ref>. Let øx denote a solution returned by some FPTAS for the traditional knapsack problem that is called on an instance with the scaled profits and let x denote an exact solution to the scaled instance (which, e.g., can be obtained by the dynamic programming scheme as above). Clearly, it holds that

    p(øx) ∑_i=1^n _i ·øx_i ≥ (1 - ε) ·∑_i=1^n _i · x_i p(x).

For any fixed λ∈ I' and an optimal solution x^* for the unscaled problem at λ, we then get the following approximation guarantee for the solution øx:

    p(øx)    = ∑_i=1^n p_i ·øx_i ≥∑_i=1^n M ·p_i/M·øx_i 
       = M ·p(øx) 
       ≥ (1 - ε) · M ·p(x) 
       ≥ (1 - ε) · M ·p(x^*) 
       ≥ (1 - ε) · M ·∑_i=1^n (p_i/M - 1 ) · x^*_i 
       = (1 - ε) ·(p^*(λ) - M ·∑_i=1^n x^*_i ) 
       ≥ (1 - ε) ·(p^*(λ) - ε·φ(λ) ) 
       ≥ (1 - ε) ·(p^*(λ) - ε· p^*(λ) ) 
       ≥ (1 - ε)^2 · p^*(λ) 
       = (1 - 2ε + ε^2) · p^*(λ) 
       ≥ (1 - 2ε) · p^*(λ).


Setting ε' ε/2 then yields the desired approximation guarantee. Hence, although the subproblems were designed in a way such that the basic dynamic programming scheme does not change its behavior, we do not necessarily need to execute it but can also use an FPTAS instead.


	There is an FPTAS for the parametric knapsack problem running in (n^2/ε· A(n,ε)) time, where A(n,ε) denotes the running time of an FPTAS for the traditional knapsack problem. 
Note that it clearly holds that A(n,ε) ∈Ω(n), so the running time of the main procedure will dominate the overheads to compute φ and the set of subintervals.

At present, the best FPTAS for the traditional knapsack problem is given by <cit.> and achieves a running time of

    ( n ·min{log n, log1/ε} + .     
    . 1/ε^2log1/ε·min{ n, 1/εlog1/ε}).

Under the commonly used assumption that n is much larger than 1/ε in practice <cit.>, this running time evaluates to

    ( n log1/ε + 1/ε^3log^2 1/ε),

yielding an FPTAS for the parametric knapsack problem with a strongly polynomial running time of

    ( n^3/εlog1/ε + n^2/ε^4log^2 1/ε).


















































































		














elsarticle-num-names



