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}