\documentstyle[12pt]{article}
\pagestyle{empty}

\hoffset -1.5cm

\textwidth 15cm

\begin{document}

\begin{center}
{\huge RAND-Seminar \\*[1cm]
Freitag, 19. Dezember 1997, 14 Uhr s.t.\\*[1cm]
Seminarraum N327}\\*[1cm]
\end{center}

\begin{center}
{\Large \bf Good approximation  algorithms  
for a variant of  {\sc Subset Sum}  problem}

\vspace*{0.5cm}


{\bf \normalsize Cristina Bazgan \\[.5ex]
        L.R.I. Paris}

\end{center}

\vspace*{0.5cm}
\begin{quote}
\baselineskip3ex
\centerline{\bf Abstract}

We are interested in a variant of {\sc Subset Sum}  problem that has in the 
input $n$ positive integers and we search two nonempty disjoint
subsets with:
-the ratio of the sums of the numbers in the two sets minimum
possible, problem called {\sc Ratio Subsets Sum},
-the difference of the sums of the numbers in the two sets minimum
possible, problem called {\sc Difference  Subsets Sum}.

We give a fully polynomial time approximation scheme for 
{\sc Ratio Subsets Sum}.
Also we give an algorithm that finds two subsets with the difference
of the sums at most $K/n^{log n}$ where $K$ is the greatest number of
the instance and we show that {\sc Difference Subsets Sum} is not
$2^{n^c}$-approximable for any constant $c$.

(Joint work with Miklos Santh and Zsolt Tuza)

\hspace*{\fill} $\Box$

\end{quote}

\end{document}


