\documentclass[a4paper,eepic,11pt]{article} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage{amssymb} \usepackage{graphicx} \usepackage{amsmath} \setcounter{MaxMatrixCols}{10} %TCIDATA{OutputFilter=LATEX.DLL} %TCIDATA{Version=4.00.0.2321} %TCIDATA{LastRevised=Monday, April 14, 2003 17:25:22} %TCIDATA{} %TCIDATA{Language=American English} %TCIDATA{CSTFile=article.cst} \newtheorem{theorem}{Theorem} \newtheorem{acknowledgement}[theorem]{Acknowledgement} \newtheorem{algorithm}[theorem]{Algorithm} \newtheorem{axiom}[theorem]{Axiom} \newtheorem{case}[theorem]{Case} \newtheorem{claim}[theorem]{Claim} \newtheorem{conclusion}[theorem]{Conclusion} \newtheorem{condition}[theorem]{Condition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{criterion}[theorem]{Criterion} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}{Example} \newtheorem{exercise}[theorem]{Exercise} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{notation}[theorem]{Notation} \newtheorem{problem}[theorem]{Problem} \newtheorem{proposition}{Proposition} \newtheorem{transformation}{Transformation} \newtheorem{remark}{Remark} \newtheorem{solution}[theorem]{Solution} \newtheorem{summary}[theorem]{Summary} \newenvironment{proof}[Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}} \begin{document} \title{Hybrid Rounding Techniques for Knapsack Problems\thanks{% Supported by the \textquotedblleft Metaheuristics Network\textquotedblright , grant HPRN-CT-1999-00106, by Swiss National Science Foundation project 20-63733.00/1, \textquotedblleft Resource Allocation and Scheduling in Flexible Manufacturing Systems\textquotedblright , and by SNF grant 2000-61847.00 to J\"{u}rgen Schmidhuber.}} \author{Monaldo Mastrolilli and Marcus Hutter \\ %EndAName {\small IDSIA, Galleria 2, 6928 Manno, Switzerland,} {\small \{monaldo, marcus\}@idsia.ch}} \maketitle \begin{abstract} We address the classical knapsack problem and a variant in which an upper bound is imposed on the number of items that can be selected. We show that appropriate combinations of rounding techniques yield novel and powerful ways of rounding. As an application of these techniques, we present a linear-storage Polynomial Time Approximation Scheme (PTAS) and a Fully Polynomial Time Approximation Scheme (FPTAS) that compute an approximate solution, of any fixed accuracy, in linear time. This linear complexity bound gives a substantial improvement of the best previously known polynomial bounds \cite{Caprara:1998:NFP}. \end{abstract} \section{Introduction} In the classical \textit{Knapsack Problem} (KP) we have a set $N:=\{1,\ldots ,n\}$ of items and a knapsack of limited capacity. To each item we associate a positive profit $p_{j}$ and a positive weight $w_{j}$. The problem calls for selecting the set of items with maximum overall profit among those whose total weight does not exceed the knapsack capacity $c>0$. KP has the following Integer Linear Programming (ILP) formulation: \begin{gather} \text{maximize \ \ \ }\sum_{j\in N}p_{j}x_{j}\text{ \ \ \ \ \ \ \ } \label{eq:ILP1} \\ \text{subject to \ \ }\sum_{j\in N}w_{j}x_{j}\leq c \label{eq:ILP2} \\ \text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }x_{j}\in \{0,1\},% \text{ \ \ }j\in N, \label{eq:ILP3} \end{gather}% where each binary variable $x_{j}$, $j\in N$, is equal to 1 if and only if item $j$ is selected. In general, we cannot take all items because the total weight of the chosen items cannot exceed the knapsack capacity $c$. In the sequel, without loss of generality, we assume that $\sum_{j\in N}w_{j}>c$ and $w_{j}\leq c$ for every $j\in N$. The \textit{k-item Knapsack Problem} (kKP), is a KP in which an upper bound of $k$ is imposed on the number of items that can be selected in a solution. The problem can be formulated as (\ref{eq:ILP1})-(\ref{eq:ILP3}) with the additional constraint \begin{equation} \sum_{j\in N}x_{j}\leq k, \label{eq:ILP4} \end{equation} with $1\leq k\leq n$. KP has widely been studied in the literature, see the book of Martello and Toth \cite{MarToth90} for a comprehensive illustration of the problem. kKP is the subproblem to be solved when instances of the Cutting Stock Problem with cardinality constraints are tackled by column generation techniques. kKP also appears in processor scheduling problems on computers with $k$ processors and shared memory. Furthermore, kKP could replace KP in the separation of cover inequalities, as outlined in \cite{Caprara:1998:NFP}. Throughout our paper let $OPT$ denote the optimal solution value to the given instance and $w(F)=\sum_{j\in F}w_{j}$ and $p(F)=\sum_{j\in F}p_{j}$, where $F\subseteq N$. An algorithm $A$ with solution value $z^{A}$ is called a $(1-\varepsilon )$-\textit{approximation algorithm}, $\varepsilon \in (0,1)$, if $z^{A}\geq (1-\varepsilon )OPT$ holds for all problem instances. We will also call $\varepsilon$ the \textit{performance ratio} of $A$. \paragraph{Known Results} It is well known that KP is NP-hard but pseudopolynomially solvable through dynamic programming, and the same properties hold for kKP \cite% {Caprara:1998:NFP}. Basically, the developed approximation approaches for KP and kKP can be divided into three groups: \begin{enumerate} \item \textit{Approximation algorithms}. For KP the classical $\frac{1}{2}$% -approximation algorithm (see e.g. \cite{app:Lawler:77}) needs only $O(n)$ running time. A performance ratio of $\frac{1}{2}$ can be obtained also for kKP by rounding the solution of the linear programming relaxation of the problem (see \cite{Caprara:1998:NFP}); this algorithm can be implemented to run in linear time when the LP relaxation of kKP is solved by using the method by Megiddo and Tamir \cite{MegTam:93}. \item \textit{Polynomial time approximation schemes} (PTAS) reach any given performance ratio and have a running time polynomial in the length of the encoded input. The best schemes currently known requiring linear space are given in Caprara et al. \cite{Caprara:1998:NFP}: they yield a performance ratio of $\varepsilon$ within $O(n^{\left\lceil 1/\varepsilon \right\rceil -2}+n\log n)$ and $O(n^{\left\lceil 1/\varepsilon \right\rceil -1})$ running time, for KP and kKP respectively. \item \textit{Fully polynomial time approximation schemes} (FPTAS) also reach any given performance ratio and have a running time polynomial in the length of the encoded input and in the reciprocal of the performance ratio. This improvement compared to 1. and 2. is usually paid off by larger space requirements, which increases rapidly with the accuracy $\varepsilon$. The first FPTAS for KP was proposed by Ibarra and Kim \cite{IbarraKim:1975}, later on improved by Lawler \cite{app:Lawler:77} and Kellerer and Pferschy \cite{Kellerer:1998:NFP}. In Caprara et al. \cite{Caprara:1998:NFP} it is shown that kKP admits an FPTAS that runs in $O(nk^{2}/\varepsilon )$ time. \end{enumerate} \paragraph{New Results} Rounding the input is a widely used technique to obtain polynomial time approximation schemes \cite{H95}. Among the developed rounding techniques, arithmetic or geometric rounding are the most successfully and broadly used ways of rounding to obtain a simpler instance that may be solved in polynomial time (see Sections \ref{Sect:arithmetic rounding} and \ref% {Sect:Geometric rounding} for an application of these techniques to kKP). We contribute by presenting a new technical idea. We show that appropriate combinations of arithmetic and geometric rounding techniques yield novel and powerful rounding methods. To the best of our knowledge, these techniques have never been combined together. By using the described rounding techniques, we present a PTAS for kKP requiring linear space and running time $O(n+k\cdot (1/\varepsilon )^{O(1/\varepsilon )})$. Our algorithm is clearly superior to the one in \cite{Caprara:1998:NFP}, and it is worth noting that the running time contains no exponent on $n$ dependent on $% \varepsilon$. Since KP is a special case of kKP, we also speed up the previous result for KP to $O(n\cdot (1/\varepsilon )^{O(1/\varepsilon )})$. Finally we present a faster FPTAS for kKP that runs in $O(n+k/\varepsilon ^{4}+1/\varepsilon ^{5})$ time and has a bound of $O(n+1/\varepsilon ^{4})$ on space requirements. \section{Rounding techniques for kKP\label{Sect:reduced N}} The aim of this section is to transform any input into one with a smaller size and a simpler structure without dramatically decreasing the objective value. We discuss several transformations of the input problem. Some transformations may potentially decrease the objective function value by a factor of $1-O(\varepsilon )$, so we can perform a constant number of them while still staying within $1-O(\varepsilon )$ of the original optimum. Others are transformations which do not decrease the objective function value. When we describe the first type of transformation, we shall say it produces $1-O(\varepsilon )$ \textit{loss}, while the second produces \textit{no} \textit{loss}. Let $P^{H}$ denote the solution value obtained in $O(n)$ time by employing the $1/2$-approximation algorithm $H^{\frac{1}{2}}$ for kKP described in \cite{Caprara:1998:NFP}. In \cite{Caprara:1998:NFP}, it is shown that \begin{equation} 2P^{H}\geq P^{H}+p_{\max }\geq OPT\geq P^{H}, \label{Eq:ineq} \end{equation} where $p_{\max }=\max_{j}p_{j}$. Throughout this section we restrict our attention to feasible solutions with at most $\gamma$ items, where $\gamma$ is a positive integer not greater than $k$. The first observation is that at most an $\varepsilon$-fraction of the optimal profit $OPT$ is lost by discarding all items $j$ where $% p_{j}\leq \varepsilon P^{H}/\gamma$, since at most $\gamma$ items can be selected and $P^{H}\leq OPT$. From now on, consider the reduced set of items with profit values greater than $\varepsilon P^{H}/\gamma$, with $% 1-\varepsilon$ loss. In order to reduce further the set of items, a useful insight is that when profits are identical we pick items in non-decreasing order of weight. Since the optimal profit is at most $2P^{H}$, for each fixed $\bar{p}\in \left\{ p_{1},...,p_{n}\right\}$, we can keep the first $\bar{n}=\min \left\{ \gamma ,\left\lfloor \frac{2P^{H}}{\bar{p}}\right\rfloor \right\}$ items with the smallest weights, and discard the others with no loss. Of course, we cannot hope to obtain a smaller instance if all profits are different. In the following, we show how the number of different profits can be reduced by rounding the original profits. We revise two rounding techniques and show that an appropriate combination of both yields to a better result. We call a profit value $\bar{p}$ \textit{large} if $\bar{p}>\frac{2P^{H}}{\gamma }$, and \textit{small} otherwise. \subsection{Arithmetic rounding\label{Sect:arithmetic rounding}} A sequence $a_{1},a_{2},...$ is called an \textit{arithmetic sequence} if, and only if, there is a constant $d$ such that $a_{i}=a_{1}+d\cdot (i-1)$, for all integers $i\geq 1$. Let us consider the arithmetic sequence $% S_{a}(\gamma )$ obtained by setting $a_{1}=d=\varepsilon P^{H}/\gamma$. We transform the given instance into a more structured one by rounding each profit down to the nearest value in $S_{a}(\gamma )$. Since in the rounded instance the profit of each item is decreased by at most $\varepsilon P^{H}/\gamma$, and at most $\gamma$ items can be selected, the solution value of the transformed instance potentially decreases by $\varepsilon P^{H}$. Of course, by restoring the original profits we cannot decrease the objective function value, and therefore, with $1-\varepsilon$ loss, we can assume that every possible profit is equal to $a_{i}=\frac{\varepsilon P^{H}% }{\gamma }\cdot i$ for some $i\geq 1$. Furthermore, since $p_{\max }=\max_{j\in N}p_{j}\leq P^{H}$, the number of different profits is now bounded by $\left\lfloor \frac{\gamma p_{\max }}{\varepsilon P^{H}}% \right\rfloor \leq \left\lfloor \frac{\gamma }{\varepsilon }\right\rfloor$. The largest number $n_{i}$ of items with profit $a_{i}$, for $% i=1,...,\left\lfloor \frac{\gamma }{\varepsilon }\right\rfloor$, that can be involved in any feasible solution is bounded by \begin{equation*} n_{i}\leq \min \{\gamma ,\left\lfloor \frac{OPT}{\frac{\varepsilon P^{H}}{% \gamma }i}\right\rfloor \}\leq \min \{\gamma ,\left\lfloor \frac{2\gamma }{% \varepsilon i}\right\rfloor \}, \end{equation*} and we can keep the first $n_{i}$ items with the smallest weights, and discard the others with no loss. Now, the number of items with profit $a_{i}$ is at most $\gamma$, if $a_{i}$ is a small profit (i.e. when $% i=1,...,\left\lfloor \frac{2}{\varepsilon }\right\rfloor$), and at most $% \left\lfloor \frac{2\gamma }{\varepsilon i}\right\rfloor$ otherwise ($% i=\left\lfloor \frac{2}{\varepsilon }\right\rfloor +1,...,\left\lfloor \frac{% \gamma }{\varepsilon }\right\rfloor$). Thus, by applying the described arithmetic rounding we have at most $\left\lfloor 2/\varepsilon \right\rfloor \gamma$ items with small profits and $\allowbreak \sum_{i=\left\lfloor \frac{2}{\varepsilon }\right\rfloor +1}^{\left\lfloor \frac{\gamma }{\varepsilon }\right\rfloor }\left\lfloor \frac{2\gamma }{% \varepsilon i}\right\rfloor$ with large profits. Recall that when a summation can be expressed as $\sum_{k=x}^{y}f(k)$, where $f(k)$ is a monotonically decreasing function, we can approximate it by an integral (see, e.g. \cite{CLR92} p. 50): $\int_{x}^{y+1}f(k)dk\leq \sum_{k=x}^{y}f(k)\leq \int_{x-1}^{y}f(k)dk$. Furthermore, we are assuming that $0<\varepsilon <1$, and recall that $\ln (1+x)\geq x/(1+x)$, for $x>-1$% . Therefore, the total number of items in the transformed instance is bounded by \begin{eqnarray*} \left\lfloor \frac{2}{\varepsilon }\right\rfloor \gamma +\sum_{i=\left\lfloor \frac{2}{\varepsilon }\right\rfloor +1}^{\left\lfloor \frac{\gamma }{\varepsilon }\right\rfloor }\left\lfloor \frac{2\gamma }{% \varepsilon i}\right\rfloor &\leq &\frac{2}{\varepsilon }\gamma +\frac{2}{% \varepsilon }\gamma \sum_{i=\left\lfloor \frac{2}{\varepsilon }\right\rfloor +1}^{\left\lfloor \frac{\gamma }{\varepsilon }\right\rfloor }\frac{1}{i} \\ &\leq &\frac{2\gamma }{\varepsilon }(1+\int_{\frac{2}{\varepsilon }-1}^{% \frac{\gamma }{\varepsilon }}\frac{di}{i})=\allowbreak \frac{2\gamma }{% \varepsilon }(1+\ln \gamma -\ln \left( 2-\varepsilon \right) ) \\ &\leq &\frac{2\gamma }{\varepsilon }(1+\ln \gamma )=O(\frac{\gamma }{% \varepsilon }\ln \gamma ). \end{eqnarray*} We see that by applying the described arithmetic rounding we have at most $% 2\gamma /\varepsilon$ items with small profits and $\allowbreak \frac{% 2\gamma }{\varepsilon }\ln \gamma$ with large profits. A natural question is to see if the provided bound is tight. Consider an instance having $\gamma$ items for each distinct profit $\frac{\varepsilon P^{H}}{\gamma }\cdot i$, where $i=1,...,\left\lfloor \frac{\gamma }{% \varepsilon }\right\rfloor$. Observe that by applying the described arithmetic rounding, we have exactly $\left\lfloor 2/\varepsilon \right\rfloor \gamma$ items with small profits and $\allowbreak \sum_{i=\left\lfloor \frac{2}{\varepsilon }\right\rfloor +1}^{\left\lfloor \frac{\gamma }{\varepsilon }\right\rfloor }\left\lfloor \frac{2\gamma }{% \varepsilon i}\right\rfloor$ with large profits. What remains to be shown is to bound the number of items to be $\Omega (\frac{\gamma }{\varepsilon }% \ln \gamma )$: \begin{eqnarray*} \left\lfloor \frac{2}{\varepsilon }\right\rfloor \gamma +\sum_{i=\left\lfloor \frac{2}{\varepsilon }\right\rfloor +1}^{\left\lfloor \frac{\gamma }{\varepsilon }\right\rfloor }\left\lfloor \frac{2\gamma }{% \varepsilon i}\right\rfloor &\geq &\frac{2}{\varepsilon }\gamma -1+\sum_{i=% \frac{2}{\varepsilon }+1}^{\frac{\gamma }{\varepsilon }-1}(\frac{2\gamma }{% \varepsilon i}-1) \\ &\geq &\frac{2}{\varepsilon }\gamma -1+\frac{2}{\varepsilon }\gamma \sum_{i=% \frac{2}{\varepsilon }+1}^{\frac{\gamma }{\varepsilon }-1}\frac{1}{i}-(\frac{% \gamma }{\varepsilon }-2) \\ &\geq &\frac{\gamma }{\varepsilon }(1+2\int_{\frac{2}{\varepsilon }+1}^{% \frac{\gamma }{\varepsilon }}\frac{di}{i})=\allowbreak \frac{\gamma }{% \varepsilon }(1+2\ln \gamma -2\ln \left( 2+\varepsilon \right) ) \\ &=&\Omega (\frac{\gamma }{\varepsilon }\ln \gamma ). \end{eqnarray*} \subsection{Geometric rounding\label{Sect:Geometric rounding}} A sequence $a_{1},a_{2},...$ is called a \textit{geometric sequence} if, and only if, there is a constant $r$ such that $a_{i}=a_{1}\cdot r^{i-1}$, for all integers $i\geq 1$. Let us consider the geometric sequence $S_{g}(\gamma )$ obtained by setting $a_{1}=\varepsilon P^{H}/\gamma$ and $r=\frac{1}{% 1-\varepsilon }$. We round each profit down to the nearest value among those of $S_{g}(\gamma )$. Since $a_{i}=(1-\varepsilon )a_{i+1}$, for $i\geq 1$, each item profit is at most decreased by a factor\footnote{% This is true only for profits larger than $a_{1}$; recall that we are assuming, with $1-\varepsilon$ loss, that all profits are larger than $a_{1}$.} of $1-\varepsilon$, and consequently, the solution value of the transformed instance potentially decreases by the same factor of $% 1-\varepsilon$. Therefore, with $1-2\varepsilon$ loss, we can assume that every possible profit is equal to $a_{i}=\frac{\varepsilon P^{H}}{\gamma }% \cdot (\frac{1}{1-\varepsilon })^{i-1}$ for some $i\geq 1$. Furthermore, since $p_{\max }\leq P^{H}$, the number of different profits is bounded by the biggest integer $\beta$ such that \begin{equation*} \frac{\varepsilon P^{H}}{\gamma }\cdot (\frac{1}{1-\varepsilon })^{\beta -1}\leq P^{H}. \end{equation*}% Since $\ln (\frac{1}{1-\varepsilon })\geq \varepsilon$, we have $\beta -1\leq \frac{\ln (\gamma /\varepsilon )}{\ln (\frac{1}{1-\varepsilon })}\leq \frac{1}{\varepsilon }\ln \frac{\gamma }{\varepsilon }$. In any feasible solution, the largest number $n_{i}$ of items with profit $a_{i}$, for $% i=1,...,\beta$, is bounded by \begin{equation*} n_{i}\leq \min \{\gamma ,\left\lfloor \frac{OPT}{\frac{\varepsilon P^{H}}{% \gamma }\cdot (\frac{1}{1-\varepsilon })^{i-1}}\right\rfloor \}\leq \min \{\gamma ,\left\lfloor \frac{2\gamma }{\varepsilon }(1-\varepsilon )^{i-1}\right\rfloor \}, \end{equation*}% and we can keep the first $n_{i}$ items with the smallest weights, and discard the others with no loss. Let $\alpha =\left\lfloor \frac{\ln \left\lfloor 2/\varepsilon \right\rfloor }{\ln \frac{1}{1-\varepsilon }}% \right\rfloor +1$. Again, the number of items with profit $a_{i}$ is at most $\gamma$, if $a_{i}$ is a small profit (i.e. when $1\leq i\leq \alpha$), and at most $\left\lfloor \frac{2\gamma }{\varepsilon }(1-\varepsilon )^{i-1}\right\rfloor$ otherwise ($i=\alpha +1,...,\beta$). Therefore, the total number of items in the transformed instance is bounded by \begin{equation*} \alpha \gamma +\sum_{i=\alpha +1}^{\beta }\left\lfloor \frac{2\gamma }{% \varepsilon }(1-\varepsilon )^{i-1}\right\rfloor \leq (\frac{1}{\varepsilon }% \ln (2/\varepsilon )+1)\gamma +\allowbreak \frac{2\gamma }{\varepsilon }=O(% \frac{\gamma }{\varepsilon }\ln \frac{1}{\varepsilon }). \end{equation*}% Moreover, we can easily show that this bound is tight. Consider an instance having $\gamma$ items for each distinct profit $\frac{\varepsilon P^{H}}{% \gamma }\cdot (\frac{1}{1-\varepsilon })^{i-1}$, where $i=1,...,\beta$. By applying the described geometric rounding technique, we have exactly $\alpha \gamma$ items with small profits and $\allowbreak \sum_{i=\alpha +1}^{\beta }\left\lfloor \frac{2\gamma }{\varepsilon }(1-\varepsilon )^{i-1}\right\rfloor$ with large profits. What remains to be shown is to bound the number of items to be $\Omega (\frac{\gamma }{\varepsilon }\ln \frac{1}{\varepsilon })$: \begin{eqnarray*} \alpha \gamma +\sum_{i=\alpha +1}^{\beta }\left\lfloor \frac{2\gamma }{% \varepsilon }(1-\varepsilon )^{i-1}\right\rfloor &\geq &\alpha \gamma \geq \frac{\ln \left\lfloor 2/\varepsilon \right\rfloor }{\ln \frac{1}{% 1-\varepsilon }}\gamma \\ &\geq &\gamma \frac{1-\varepsilon }{\varepsilon }\ln \frac{2-\varepsilon }{% \varepsilon }=\Omega (\frac{\gamma }{\varepsilon }\ln \frac{1}{\varepsilon }% ). \end{eqnarray*} We see that by applying the geometric rounding we have at most $\gamma /\varepsilon$ items with large profit, while $O(\frac{\gamma }{\varepsilon }% \ln \frac{1}{\varepsilon })$ items with small profits. Contrary to arithmetic rounding, the set of items that has been reduced most is the set with large profits. This suggests us to combine the described rounding techniques as described in the following subsection. \subsection{Parallel Arithmetic \& Geometric rounding\label{Sect:arith_geo}} We use arithmetic rounding for the set of items with small profits and geometric rounding for large items. Let us say that these two techniques are applied in \textquotedblleft parallel\textquotedblright . More formally, let us consider the \textit{hybrid }sequence $S_{ag}(\gamma )=(a_{1},a_{2},...)$ defined by setting \begin{equation*} a_{i}=\frac{\varepsilon P^{H}}{\gamma }\cdot \left\{ \begin{array}{l} i \\ (\frac{1}{1-\varepsilon })^{\alpha +i-\left\lfloor 2/\varepsilon \right\rfloor -1}% \end{array}% \right. \begin{array}{l} \text{for }i=1,...,\left\lfloor 2/\varepsilon \right\rfloor \text{,} \\ \text{otherwise.}% \end{array}% \end{equation*}% We round each profit down to the nearest value among those of $S_{ag}(\gamma )$. Now, consider each set $Z_{i}$ of items with the same rounded profit value $a_{i}$, and take the first \begin{equation*} n_{i}=\left\{ \begin{array}{l} \gamma \\ \left\lfloor \frac{2\gamma }{\varepsilon }(1-\varepsilon )^{\alpha +i-\left\lfloor 2/\varepsilon \right\rfloor -1}\right\rfloor% \end{array}% \right. \begin{array}{l} \text{for }i=1,...,\left\lfloor 2/\varepsilon \right\rfloor \text{,} \\ \text{otherwise,}% \end{array}% \end{equation*}% items with the smallest weights we get in $Z_{i}$. Selecting the first $% n_{i}$ items with the smallest weights can be done in $O(|Z_{i}|)$ time. That is, $O(|Z_{i}|)$ time is sufficient to select the $n_{i}$-th item with the smallest weight (see \cite{median-finding}) and only $O(|Z_{i}|)$ comparisons are needed to extract the $n_{i}-1$ items with smaller weights. Therefore the amortized time is linear. By using the arithmetic rounding technique for small items, we have at most $% 2\gamma /\varepsilon$ small items with $1-\varepsilon$ loss (see Section % \ref{Sect:arithmetic rounding}). While, by using the geometric rounding technique described in Section \ref{Sect:Geometric rounding} for large items, we have at most $\gamma /\varepsilon$ large items with $% 1-\varepsilon$ loss. The resulting transformed instance has at most $% 3\gamma /\varepsilon$ items with $1-2\varepsilon$ loss. Furthermore, let $% \psi =\beta -\alpha +\left\lfloor 2/\varepsilon \right\rfloor +1$. Observe that the $\psi$-th element of $S_{ag}(\gamma )$ is larger than $P^{H}$, i.e. $a_{\psi }>P^{H}$. Consider any subset $S\subseteq N$ of items with at most $\gamma$ items, and let $x_{i}$ denote the total number of items from $% S$ with profit in interval $[a_{i},a_{i+1})$, $i=1,2,...\psi -1$. Let us call vector $(x_{1},x_{2},...,x_{\psi -1})$ an $S$\textit{-configuration}. It is easy to see that by using the reduced set of items it is always possible to compute a solution having the same $S$-configuration, as any set $S\subseteq N$ with $\gamma$ items. Summarizing: \begin{lemma} \label{Lemma: gamma}For any positive integer $\gamma \leq k$, it is possible to compute in linear time a reduced set $N_{\gamma }\subseteq N$ of items with at most $3\gamma /\varepsilon$ items, such that, for any subset $% S\subseteq N$ with at most $\gamma$ items, there exists a subset $S_{\gamma }\subseteq N_{\gamma }$ such that $S_{\gamma }$ is the subset of $N$ having the same configuration as $S$ and with the least weights. \end{lemma} \begin{corollary} \label{Corollary: gamma}For any subset $S\subseteq N$ with at most $\gamma$ items, there exists a subset $S_{\gamma }\subseteq N_{\gamma }$ with $% w(S_{\gamma })\leq w(S)$, $|S_{\gamma }|=|S|$ and $p(S_{\gamma })\geq p(S)-2\varepsilon \cdot OPT$. \end{corollary} \section{An improved PTAS for kKP} Our PTAS for kKP improves the scheme of Caprara et al. \cite% {Caprara:1998:NFP}, and in fact it strongly builds on their ideas. However, there are several differences where a major one is the use of two reduced sets of items instead of the entire set $N$: let $\ell :=\min \{\lceil 1/\varepsilon \rceil -2,k\}$, where $\varepsilon \leq 1/2$ is an arbitrary small rational number; our algorithm uses sets $N_{k}$ and $N_{\ell }$ computed by using the Arithmetic \& Geometric rounding technique (see Lemma % \ref{Lemma: gamma}) when $\gamma :=k$ and $\gamma :=\ell$, respectively. For any given instance of kKP, the approximation scheme performs the following five steps (S-1)-(S-5). \begin{enumerate} \item[(S-1)] Initialize the solution $A$ to be the empty set and set the corresponding value $P^{A}$ to $0$. \item[(S-2)] Compute the reduced sets $N_{k}$ and $N_{\ell }$. \item[(S-3)] Compute $P^{H}$, i.e. the solution value returned by $H^{\frac{1% }{2}}$ when applied to the whole set of instances. \item[(S-4)] Consider each $L\subseteq N_{\ell }$ such that $|L|\leq \ell$. If $w(L)\leq c$, consider sequence $S_{ag}(\ell )=(a_{1},a_{2},...)$ and let $h$ be the smallest integer such that $\min_{j\in L}p_{j}P^{A}$ let $A:=L\cup T$ and $P^{A}:=p(L)+P^{H}(S)$. \item[(S-5)] Return solution $A$ of value $P^{A}$. \end{enumerate} Observe that in step (S-4), subsets $L$ are computed by considering just the items from $N_{\ell }$. On the other hand, in step (S-4), we remark that the subinstances $S$ are defined by using items from $N_{k}$. \subsection{Analysis of the Algorithm} Step (S-2) can be performed in $O(n)$ time by Lemma \ref{Lemma: gamma}. Step (S-3) runs in $O(n)$ time \cite{Caprara:1998:NFP}. In step (S-4) the algorithm considers $O(|N_{\ell }|+|N_{\ell }|^{2}+...+|N_{\ell }|^{\ell })=O(|N_{\ell }|^{\ell })$ subsets. For each $L$ the definition of subinstance $S$ requires $O(|N_{k}|\cdot \ell )$ time. Algorithm $H^{\frac{1% }{2}}$ applied to subinstance $S$ runs in $O(|S|)=O(|N_{k}|)$ time \cite% {Caprara:1998:NFP}. By Lemma \ref{Lemma: gamma}, $|N_{k}|=O(k/\varepsilon )$ and $|N_{\ell }|=O(\ell /\varepsilon )$. Therefore, step (S-4) is performed in $O(|N_{\ell }|^{\ell }\cdot |N_{k}|\cdot \ell )=O(k\cdot (\frac{\ell }{% \varepsilon })^{\ell +1})=k\cdot (1/\varepsilon )^{O(1/\varepsilon )}$. It follows that the overall running time of the algorithm is $O(n+k\cdot (1/\varepsilon )^{O(1/\varepsilon )})$, and it is not difficult to check that steps (S-1)-(S-5) require linear space. What remains to be shown is that steps (S-1)-(S-5) return a $(1-O(\varepsilon ))$-approximate solution. Consider sequence $S_{ag}(\ell )=(a_{1},a_{2},...)$. Let $\left\{ j_{1},...,j_{\ell },...\right\}$ be the set of items in an optimal solution ordered so that $p_{j_{1}}\geq ...\geq p_{j_{\ell }}\geq ...$, and let $% \lambda \leq \ell$ be the largest integer such that $p_{j_{\lambda }}\geq a_{1}$ (if there is no item in the optimal solution with profit $\geq a_{1}$ then set $\lambda =0$). Let $L^{\ast }=\left\{ j_{1},...,j_{\lambda }\right\}$ be the subset (possibly empty) obtained by picking the first $% \lambda$ items with the largest profits. Consider subinstance $S^{\ast }$ defined by item set \begin{equation*} I_{S^{\ast }}=\{i\in N\backslash L^{\ast }\left\vert \begin{array}{l} p_{i}\leq \min_{j\in L^{\ast }}p_{j}\text{ if }L^{\ast }\neq \varnothing \\ p_{i}\varepsilon P^{H}\right\} $and$\mathcal{S}=\left\{ j:p_{j}\leq \varepsilon P^{H}\right\} $. Let us say that$\mathcal{L}$is the set of \emph{large} items, while$\mathcal{S}$the set of \emph{small} items. Observe that the number of large items in any feasible solutions is not greater than$\lambda =\min \left\{ k,\left\lfloor 2/\varepsilon \right\rfloor \right\} $, since$OPT\leq 2P^{H}$. \subsection{Dynamic programming for large items} In principle, an optimal solution could be obtained in the following way. Enumerate all different solutions for items in$\mathcal{L}$, i.e., consider all different sets$U\subseteq \mathcal{L}$such that$w(U)\leq c$and$% |U|\leq k$. For each of these$U$, compute a set$T\subseteq \mathcal{S}$such that$w(T)+w(U)\leq c$,$|U|+|T|\leq k$and$p(T)$is maximized. Select from these solutions one with the largest overall profit. One of the problems with this approach is that constructing all possible solutions for items in$\mathcal{L}$would require considering$n^{O(1/\varepsilon )}$cases. To avoid the exponential dependence on$1/\varepsilon $(our aim is to obtain a fully polynomial approximation scheme), we will not treat separately all of these solutions. We begin with the description of a basic procedure that generates a list of all interesting'' feasible combinations of profit and number of selected large items. Each such combination is represented by a pair$(a,l)$, for which there is a subset of items$% U\subseteq \mathcal{L}$with$p(U)=a$,$|U|=l$and$w(U)\leq c$. Moreover$% w(U)$is the smallest attainable weight for a subset of large items with profit at least equal to$a$and cardinality at most$l$. This list of all interesting'' feasible combinations is computed by using a pseudopolynomial dynamic programming scheme. Clearly, an optimal solution can be computed by using only the subsets$U$of large jobs associated to each pair$(a,l)$. The time complexity will be then reduced, with$1-O\left( \varepsilon \right) $loss, by applying arithmetic and geometric rounding techniques, as described in Section \ref{Sect:serialGeoArith}. Let$\alpha $be the number of large items, and let$\beta $denote the number of all distinct feasible solution values obtained by considering only large items, i.e.$\beta $is the size of set \begin{equation*} V=\left\{ p(U)|U\subseteq \mathcal{L}\text{ and }w(U)\leq c\ \text{and }% |U|\leq k\right\} . \end{equation*}% A straightforward dynamic programming recursion which has time complexity$% O(\alpha \beta \lambda )$and space complexity$O(\lambda ^{2}\beta )$(see \cite{Caprara:1998:NFP}), can be stated as follows. Let us renumber the set of items such that the first$1,...,|L|$items are large. Denote by function$g_{i}(a,l)$for$i=1,...,|L|$,$a\in V$,$l=1,...,\lambda $, the optimal solution of the following problem: \begin{equation*} g_{i}(a,l)=\min \sum_{j=1}^{i}w_{j}x_{j}:\left\vert \begin{array}{l} \sum_{j=1}^{i}p_{j}x_{j}=a; \\ \sum_{j=1}^{i}x_{j}=l; \\ x_{j}\in \left\{ 0,1\right\} ,j=1,...,i.% \end{array}% \right\} \end{equation*}% One initially sets$g_{0}(a,l)=+\infty $for all$l=0,...,\lambda $,$a\in V$% , and then$g_{0}(0,0)=0$. Then, for$i=1,...,|L|$the entries for$g_{i}$can be computed from those of$g_{i-1}$by using the formula \begin{equation*} g_{i}(a,l)=\min \left\{ \begin{array}{l} g_{i-1}(a,l), \\ g_{i-1}(a-p_{i},l-1)+w_{i}\text{ \ \ if }l>0\text{ and }a\geq p_{i}% \end{array}% \right\} . \end{equation*} Since$\beta =O(P^{H})$the described dynamic programming algorithm is only pseudopolynomial. In order to reduce the time complexity, we first preprocess large items by using a combination of arithmetic and geometric rounding techniques, then we apply the above dynamic programming scheme. We start analyzing the two rounding techniques separately, then we show how to combine them. \subsubsection{Geometric rounding} The time complexity of the described dynamic programming can be reduced by decreasing the number$\alpha $of large items and the number$\beta $of distinct solution values. We observed in Section \ref{Sect:reduced N} that if we want to reduce as much as possible the number of large items it is convenient to use geometric rounding. Consider the geometric sequence$S_{g}(\gamma )$described in Section \ref{Sect:Geometric rounding}. By applying the geometric rounding technique with$\gamma =\lambda $, the number$\alpha $of large items can be reduced from$O(n)$to$O(1/\varepsilon ^{2})$with$1-\varepsilon $loss. The next step is to compute the number of possible solution values after geometric rounding, i.e. the cardinality$\beta $of set$V$after that all profit values of large items have been geometrically rounded. The main result of this section is stated as follows. \begin{theorem} \label{Th:GeoSumBounds}The number of solution values after geometric rounding can be exponential in${\frac{1}{\varepsilon }}$. \end{theorem} By the above theorem it follows that the running time of dynamic programming after geometric rounding is a constant that may depend exponentially on${% \frac{1}{\varepsilon }}$. Therefore, to avoid this exponential dependence on${\frac{1}{\varepsilon }}$, we will look at other rounding techniques. \paragraph{Proof of Theorem \protect\ref{Th:GeoSumBounds}.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In the remaining part of this subsection we prove Theorem \ref% {Th:GeoSumBounds}. The goal is to derive a lower bound on the number of possible solution values after geometric rounding, i.e.\ a lower bound on$% |V|$. Recall that we defined the geometric sequence$a_{i}={\frac{% \varepsilon P^{H}}{\lambda }}({\frac{1}{1-\varepsilon }})^{i-1}$in Section % \ref{Sect:Geometric rounding}, and here we assume that$\gamma =\lambda $. We focus on worst-case analysis. With this aim let us consider an instance$% I $that after geometric rounding has at least$\left\lfloor P^{H}/a_{i}\right\rfloor $items for each distinct profit value$a_{i}$. Moreover, we assume that$w_{j}=p_{j}$for every$j\in \mathcal{L}$,$% c=P^{H} $and$k\geq 1/\varepsilon $. By definition of instance$I$we see that every subset$U$with$p(U)1$. For simplicity of notation we replace$\varepsilon ^{\prime }$with$% \varepsilon $, and we focus on the cardinality of sets of the form \begin{equation*} R_{\varepsilon }^{d}\;:=\;\left\{ y<1:y=\sum_{i=0}^{d-1}c_{i}\varepsilon (1+\varepsilon )^{i},\quad \mathbf{c}\in I\!\!N_{0}^{d}\right\} , \end{equation*} where$I\!\!N_{0}^{d}$is the set of$d$-dimensional vectors$\mathbf{c}% =(c_{0},c_{1},...,c_{d-1})$with non-negative integer components. It is more easy to find lower bounds on the set of vectors \begin{equation} S_{\varepsilon }^{d}\;:=\;\left\{ \mathbf{c}\in I\!\!N_{0}^{d}:\sum_{i=0}^{d-1}c_{i}\varepsilon (1+\varepsilon )^{i}<1\right\} \label{Sdef} \end{equation} itself. To consider$|S_{\varepsilon }^{d}|$instead of$|R_{\varepsilon }^{d}|$is justified by the following Lemma. \begin{lemma} \label{lemOnto} For rational and for transcendental$\varepsilon >0$, the sets$R_{\varepsilon }^{d}$and$S_{\varepsilon }^{d}$have the same cardinality, i.e.\ the mapping$f:S_{\varepsilon }^{d}\rightarrow R_{\varepsilon }^{d}$with$f(\mathbf{c})=\sum_{i=0}^{d-1}c_{i}\varepsilon (1+\varepsilon )^{i}$is one-to-one and onto. \end{lemma} \begin{proof}[\textbf{Proof for transcendental$\protect\varepsilon$}] \begin{equation*} y=y^{\prime }\quad \Leftrightarrow \quad \sum_{i=0}^{d-1}b_{i}x^{i}=0\quad \text{with}\quad b_{i}:=c_{i}-c_{i}^{\prime }\in Z\!\!\!Z\quad \text{and}% \quad x:=1+\varepsilon \end{equation*} A real number is said to be transcendental if it is not the root of a polynomial with integer coefficients. For transcendental$\varepsilon $also$x$is transcendental, which implies$b_{i}\equiv 0$. Hence,$y=y^{\prime }$implies$\mathbf{c}=\mathbf{c}^{\prime }$. Obviously$\mathbf{c}=\mathbf{c}% ^{\prime }$implies$y=y^{\prime }$. This proves that$S_{\varepsilon }^{d}$has the same cardinality as$R_{\varepsilon }^{d}$for transcendental$% \varepsilon $. \textbf{Proof for rational$\varepsilon$.} Assume by contradiction that there are two different vectors$\mathbf{c}\neq \mathbf{c}^{\prime }\in {% I\!\!N}_{0}^d$with same solution value$y=y^{\prime }$. Let$n$be the largest index$i$such that$c_{i}\neq c_{i}^{\prime }$. Furthermore, let$% \varepsilon ={\frac{p}{q}}-1>0$be rational with$p>q\in{I\!\!N} $having no common factors. With$\mathbf{b}:=\mathbf{c}-\mathbf{c}^{\prime } $we have \begin{eqnarray*} 0\; &=&\;[y-y^{\prime }]\;=\;\sum_{i=0}^{d-1}b_{i}\varepsilon(1+\varepsilon )^{i}\; \\ &=&\;\varepsilon\sum_{i=0}^{n}b_{i}{\frac{p^{i}}{q^{i}}}\;=\;{\frac{% \varepsilon}{q^{n}}}\Big[b_{n}p^{n}+q\overbrace{% \sum_{i=0}^{n-1}[b_{i}p^{i}q^{n-i-1}]}^{integer}\Big] \end{eqnarray*} Since the last term$q\sum [...]$is a multiple of$q$,$y-y^{\prime }$can only be zero if also$b_{n}p^{n}$is a multiple of$q$. With$p$also$p^{n}$has no common factor with$q$, hence$b_{n}$must itself be a multiple of$q$% . The sum in (\ref{Sdef}) can only be less than 1 if each term is less than 1, i.e.\$c_{i}\varepsilon (1+\varepsilon )^{i}<1$. This implies \begin{equation} c_{i}<\varepsilon ^{-1}(1+\varepsilon )^{-i}\leq \varepsilon ^{-1}\quad \text{for all}\quad i. \label{ckbnd} \end{equation} Together we get \begin{equation*} 0\leq c_{n}^{_{(}}{\!\displaystyle^{\prime }}^{_{)}}<{\frac{1}{\varepsilon }}% ={\frac{q}{p-q}}From Lemma \ref{lemGeoBnd} we know that (\ref{cleq1}) has at least$% Ce^{B/\varepsilon }$solution vectors$\mathbf{c}$and from Lemma \ref% {lemOnto} that (\ref{cleqgam}) has at least$Ce^{B/\varepsilon }$solution values$y$for rational$\varepsilon $, and the proof of Theorem \ref% {Th:GeoSumBounds} follows. \subsubsection{Arithmetic rounding} Alternatively, we may think to apply arithmetic rounding to the set of large items. Let us consider the arithmetic sequence$S_{a}(\gamma )$described in Section \ref{Sect:arithmetic rounding}. By applying the arithmetic rounding technique with$\gamma =\lambda $, we observe the number of large items can be reduced to be bounded by$O(\frac{1}{\varepsilon ^{2}}\ln \frac{1}{% \varepsilon })$with$1-\varepsilon $loss. Moreover each element of set$V$is equal to$\frac{\varepsilon P^{H}}{\lambda }i$for some$i=\lambda ,\lambda +1,...,2\left\lfloor \lambda /\varepsilon \right\rfloor $. It follows that the size of set$V$is bounded by$O(1/\varepsilon ^{2})$, and the overall time of the dynamic programming algorithm is now$O(\frac{1}{% \varepsilon ^{5}}\ln \frac{1}{\varepsilon })$. We see that in comparison to the geometric rounding and although the number of large items is larger, the arithmetic rounding technique is able to reduce much more the size of set$V$% . However and again, we can take advantage from both techniques by combining them as described in the following. \subsubsection{Serial Geometric \& Arithmetic rounding\label% {Sect:serialGeoArith}} We first apply geometric rounding with$1-\varepsilon $loss. This reduces the number of large items to be bounded by$O(1/\varepsilon ^{2})$. Then, with$1-\varepsilon $loss, we apply arithmetic rounding on the reduced set of large items. Clearly the latter does not increase the number of items and each profit value is now equal to$\frac{\varepsilon P^{H}}{\lambda }i$for some$i=\lambda ,\lambda +1,...,2\left\lfloor \lambda /\varepsilon \right\rfloor $. By using this set of items with profits rounded by using geometric first and arithmetic rounding then, the size of set$V$has a bound of$O(1/\varepsilon ^{2})$, and the overall time of the dynamic programming algorithm is$O(1/\varepsilon ^{5})$. We call this combination a \textit{Serial Geometric \& Arithmetic rounding technique}. \subsection{Adding small items\label{Sect:FPTASsmall}} In the following we show how to add the small items. First, with$% 1-2\varepsilon $loss, we reduce the number of small items to be$% O(k/\varepsilon )$by using the Parallel Arithmetic \& Geometric rounding (see Section \ref{Sect:arith_geo}). Then, for each pair$(a,l)$in the final list, fill in the remaining knapsack capacity$c-g_{|L|}(a,l)$with at most$% k-l$small items, by using algorithm$H^{\frac{1}{2}}$for kKP \cite% {Caprara:1998:NFP}. These small items yield total profit$% P^{H}(c-g_{|L|}(a,l),k-l)$. By inequality (\ref{Eq:ineq}) and by definition of small items, we have \begin{equation} P^{H}(c-g_{|L|}(a,l),k-l)+\varepsilon P^{H}\geq OPT(c-g_{|L|}(a,l),k-l), \label{eq:ineqFPTAS} \end{equation} where$OPT(c-g_{|L|}(a,l),k-l)$is the optimal solution value obtained by using at most$k-l$small items and knapsack capacity$c-g_{|L|}(a,l)$. The approximate solution, a combination of large and small items, is chosen to yield profit$P$, where \begin{equation*} P=\max_{(a,l)}\left\{ a+P^{H}(c-g_{|L|}(a,l),k-l)\right\} \end{equation*} By inequality (\ref{eq:ineqFPTAS}) and since our algorithms considers all the interesting'' pairs$(a,l)$with$1-O(\varepsilon )$loss, it is easy to verify that$P$is$1-O(\varepsilon )$times the optimal solution. To summarize, the steps of the FPTAS are as follows. \begin{enumerate} \item[(S-1)] Partition the set of items into large'' and small''. Apply the Serial Geometric \& Arithmetic rounding technique to the set of large items. Apply the Parallel Arithmetic \& Geometric rounding technique to the set of small items. \item[(S-2)] Solve for the large'' items using dynamic programming: generate a list of all interesting'' feasible combinations$(a,l)$of profit$a$and number$l$of selected large items. \item[(S-3)] For each pair$(a,l)$in the final list, fill in the knapsack by applying algorithm$H^{\frac{1}{2}}$with the reduced set small items. \item[(S-4)] Return the best found solution. \end{enumerate} Step (S-1) can be performed in$O(n)$time. Step (S-2) takes$% O(1/\varepsilon ^{5})$time. Algorithm$H^{\frac{1}{2}}$applied to the reduced set of small items runs in$O(k/\varepsilon )$time \cite% {Caprara:1998:NFP}. In step (S-3) the algorithm considers$O(1/\varepsilon ^{3})$pairs, for each one performing operations that require$% O(k/\varepsilon )$time. It follows that the overall running time of the algorithm is$O(n+k/\varepsilon ^{4}+1/\varepsilon ^{5})$. The space complexity has a bound of$O(n+1/\varepsilon ^{4})$, since the space required by the dynamic programming is$O(\lambda ^{2}\beta )$where$% \lambda =O(1/\varepsilon )$and$\beta =O(1/\varepsilon ^{2})$. \begin{theorem} There is a fully polynomial time approximation scheme for the k-item knapsack problem requiring$O(n+k/\varepsilon ^{4}+1/\varepsilon ^{5})$time and$O(n+1/\varepsilon ^{4})\$ space. \end{theorem} \paragraph{Acknowledgments.} Thanks are due to Klaus Jansen for introducing us to the k-item Knapsack Problem. We are grateful to the referees who pointed out some mistakes in the early version of this paper. \begin{thebibliography}{9} \bibitem{median-finding} M.~Blum, R.~W. Floyd, V.~Pratt, R.~Rivest, and R.~Tarjan. \newblock Time bounds for selection. \newblock {\em Journal of Computer and System Sciences}, 7:448--461, 1973. \bibitem{Caprara:1998:NFP} A.~Caprara, H.~Kellerer, U.~Pferschy, and D.~Pisinger. \newblock Approximation algorithms for knapsack problems with cardinality constraints. \newblock {\em European Journal of Operational Research}, 123:333--345, 2000. \bibitem{CLR92} T.~H. Cormen, C.~E. Leiserson, and R.~L. Rivest. \newblock \emph{Introduction to algorithms}. \newblock MIT Press and McGraw-Hill Book Company, 6th edition, 1992. \bibitem{H95} D.~Hochbaum, editor. \newblock {\em Approximation Algorithms for NP-hard Problems}. \newblock ITP, 1995. \bibitem{Hutter:01fast} M.~Hutter. \newblock The fastest and shortest algorithm for all well-defined problems. \newblock {\em International Journal of Foundations of Computer Science}, 13(3):431--443, 2002. \bibitem{IbarraKim:1975} O.~H. Ibarra and C.~E. Kim. \newblock Fast approximation algorithms for the knapsack and sum of subset problems. % \newblock {\em J. Assoc. Comput. Mach.}, 22:463--468, 1975. \bibitem{Kellerer:1998:NFP} H.~Kellerer and U.~Pferschy. \newblock A new fully polynomial approximation scheme for the knapsack problem. \newblock \emph{APPROX'98}, LNCS 1444:123--134, 1998. \bibitem{app:Lawler:77} E.~L. Lawler. \newblock Fast approximation algorithms for knapsack problems. \newblock {\em Proc. 18th Ann. Symp. on Foundations of Computer Science}, pages 206--218, 1977. \bibitem{MarToth90} S.~Martello and P.~Toth. \newblock {\em Knapsack Problems}. \newblock Wiley, 1990. \bibitem{MegTam:93} N.~Megiddo and A.~Tamir. \newblock Linear time algorithms for some separable quadratic programming problems. \newblock \emph{Operations Research Letters}, 13:203--211, 1993. \end{thebibliography} \end{document}