\batchmode
\documentclass[11pt]{article}
\makeatletter
\usepackage{fullpage}


\providecommand{\group}[1]{\left<#1\right>} 

\providecommand{\edge}[1]{\left<#1\right>} 

\providecommand{\opt}{\mbox{\sl opt}} 

\renewcommand{\epsilon}{\varepsilon}

\providecommand{\sgn}{\mbox{\rm sgn}} 


\newenvironment{newproblem}[1]{{#1}
\begin{list}{}{\leftmargin\leftmargini\itemsep0pt\parsep0pt}}{\end{list}} 


\providecommand{\instance}{\item[{\sc Instance:}] } 

\providecommand{\certificate}{\item[{\sc Solution:}] } 

\providecommand{\measure}{\item[{\sc Measure:}] } 

\providecommand{\good}{\item[{\em Good News:}] } 

\providecommand{\bad}{\item[{\em Bad News:}] } 

\providecommand{\comment}{\item[{\em Comment:}] } 

\providecommand{\GandJ}[1]{\item[{\em Garey and Johnson:}]\ #1} 


\providecommand{\minedgecoloring}{{\sc Minimum Edge Coloring}} 

\providecommand{\minsetcover}{{\sc Minimum Set Cover}} 

\providecommand{\maxtwosat}{{\sc Maximum 2-Satisfiability}} 


\title{
How to find the best approximation results\\
-- a follow-up to Garey and Johnson\footnote{
Published in ACM SIGACT News, December 1998.
}}


\author{Pierluigi Crescenzi\thanks{
Dipartimento di Sistemi ed Informatica,
Universit\`a di Firenze,
Via Cesare Lombroso 6/17, 50134 Firenze, Italy,
{\tt piluc@dsi.unifi.it}}
\and Viggo Kann\thanks{
Department of Numerical Analysis and Computing Science,
Royal Institute of Technology,
SE-100 44 Stockholm, Sweden,
{\tt viggo@nada.kth.se}\hfill\break
Copyright \copyright\ Pierluigi Crescenzi and Viggo Kann, 1998}}
\date{}



\usepackage[dvips]{color}
\pagecolor[gray]{.7}



\makeatletter

\makeatletter
\count@=\the\catcode`\_ \catcode`\_=8 
\newenvironment{tex2html_wrap}{}{} \catcode`\_=\count@
\makeatother
\let\mathon=$
\let\mathoff=$
\ifx\AtBeginDocument\undefined \newcommand{\AtBeginDocument}[1]{}\fi
\newbox\sizebox
\setlength{\hoffset}{0pt}\setlength{\voffset}{0pt}
\addtolength{\textheight}{\footskip}\setlength{\footskip}{0pt}
\addtolength{\textheight}{\topmargin}\setlength{\topmargin}{0pt}
\addtolength{\textheight}{\headheight}\setlength{\headheight}{0pt}
\addtolength{\textheight}{\headsep}\setlength{\headsep}{0pt}
\setlength{\textwidth}{349pt}
\newwrite\lthtmlwrite
\makeatletter
\let\realnormalsize=\normalsize
\global\topskip=2sp
\def\preveqno{}\let\real@float=\@float \let\realend@float=\end@float
\def\@float{\let\@savefreelist\@freelist\real@float}
\def\end@float{\realend@float\global\let\@freelist\@savefreelist}
\let\real@dbflt=\@dbflt \let\end@dblfloat=\end@float
\let\@largefloatcheck=\relax
\def\@dbflt{\let\@savefreelist\@freelist\real@dbflt}
\def\adjustnormalsize{\def\normalsize{\mathsurround=0pt \realnormalsize
 \parindent=0pt\abovedisplayskip=0pt\belowdisplayskip=0pt}\normalsize}%
\def\lthtmltypeout#1{{\let\protect\string\immediate\write\lthtmlwrite{#1}}}%
\newcommand\lthtmlhboxmathA{\adjustnormalsize\setbox\sizebox=\hbox\bgroup\kern.05em }%
\newcommand\lthtmlvboxmathA{\adjustnormalsize\setbox\sizebox=\vbox\bgroup\kern.05em %
 \let\ifinner=\iffalse }%
\newcommand\lthtmlboxmathZ{\@next\next\@currlist{}{\def\next{\voidb@x}}%
 \expandafter\box\next\egroup}%
\newcommand\lthtmlmathtype[1]{\def\lthtmlmathenv{#1}}%
\newcommand\lthtmllogmath{\lthtmltypeout{l2hSize %
:\lthtmlmathenv:\the\ht\sizebox::\the\dp\sizebox::\the\wd\sizebox.\preveqno}}%
\newcommand\lthtmlfigureA[1]{\let\@savefreelist\@freelist
       \lthtmlmathtype{#1}\lthtmlvboxmathA}%
\newcommand\lthtmlfigureZ{\lthtmlboxmathZ\lthtmllogmath\copy\sizebox
       \global\let\@freelist\@savefreelist}%
\newcommand\lthtmldisplayA[1]{\lthtmlmathtype{#1}\lthtmlvboxmathA}%
\newcommand\lthtmldisplayB[1]{\edef\preveqno{(\theequation)}%
  \lthtmldisplayA{#1}\let\@eqnnum\relax}%
\newcommand\lthtmldisplayZ{\lthtmlboxmathZ\lthtmllogmath\lthtmlsetmath}%
\newcommand\lthtmlinlinemathA[1]{\lthtmlmathtype{#1}\lthtmlhboxmathA
  \vrule height1.5ex width0pt }%
\newcommand\lthtmlinlineA[1]{\lthtmlmathtype{#1}\lthtmlhboxmathA}%
\newcommand\lthtmlinlineZ{\egroup\expandafter\ifdim\dp\sizebox>0pt %
  \expandafter\centerinlinemath\fi\lthtmllogmath\lthtmlsetinline}
\newcommand\lthtmlinlinemathZ{\egroup\expandafter\ifdim\dp\sizebox>0pt %
  \expandafter\centerinlinemath\fi\lthtmllogmath\lthtmlsetmath}
\newcommand\lthtmlindisplaymathZ{\egroup %
  \centerinlinemath\lthtmllogmath\lthtmlsetmath}
\def\lthtmlsetinline{\hbox{\vrule width.1em\kern-.05em\vtop{\vbox{%
  \kern.1em\copy\sizebox}\ifdim\dp\sizebox>0pt\kern.1em\else\kern.3pt\fi
  \ifdim\hsize>\wd\sizebox \hrule depth1pt\fi}}}
\def\lthtmlsetmath{\hbox{\vrule width.1em\kern-.05em\vtop{\vbox{%
  \kern.1em\kern0.8 pt\hbox{\hglue.17em\copy\sizebox\hglue0.8 pt}}\kern.3pt%
  \ifdim\dp\sizebox>0pt\kern.1em\fi \kern0.8 pt%
  \ifdim\hsize>\wd\sizebox \hrule depth1pt\fi}}}
\def\centerinlinemath{%
  \dimen1=\ifdim\ht\sizebox<\dp\sizebox \dp\sizebox\else\ht\sizebox\fi
  \advance\dimen1by.5pt \vrule width0pt height\dimen1 depth\dimen1 
 \dp\sizebox=\dimen1\ht\sizebox=\dimen1\relax}

\def\lthtmlcheckvsize{\ifdim\ht\sizebox<\vsize 
  \ifdim\wd\sizebox<\hsize\expandafter\hfill\fi \expandafter\vfill
  \else\expandafter\vss\fi}%
\makeatletter \tracingstats = 1 


\begin{document}
\pagestyle{empty}\thispagestyle{empty}%
\lthtmltypeout{latex2htmlLength hsize=\the\hsize}%
\lthtmltypeout{latex2htmlLength vsize=\the\vsize}%
\lthtmltypeout{latex2htmlLength hoffset=\the\hoffset}%
\lthtmltypeout{latex2htmlLength voffset=\the\voffset}%
\lthtmltypeout{latex2htmlLength topmargin=\the\topmargin}%
\lthtmltypeout{latex2htmlLength topskip=\the\topskip}%
\lthtmltypeout{latex2htmlLength headheight=\the\headheight}%
\lthtmltypeout{latex2htmlLength headsep=\the\headsep}%
\lthtmltypeout{latex2htmlLength parskip=\the\parskip}%
\lthtmltypeout{latex2htmlLength oddsidemargin=\the\oddsidemargin}%
\makeatletter
\if@twoside\lthtmltypeout{latex2htmlLength evensidemargin=\the\evensidemargin}%
\else\lthtmltypeout{latex2htmlLength evensidemargin=\the\oddsidemargin}\fi%
\makeatother

% !!! IMAGES START HERE !!!

\stepcounter{section}
\stepcounter{section}
\stepcounter{section}

\setbox%

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline316}%
$G=\left<V,E\right>$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline322}%
$E_1,E_2,\ldots,E_k$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline324}%
$1\le i\le k$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline332}%
$-\varepsilon $%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline334}%
$\varepsilon >0$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline336}%
$+(0.8/\mbox{\sl opt})$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{tex2html_wrap516}%
\fbox{\box0}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figure99}%
\begin{figure}
\begin{center}
\begin{picture}
(275,185)(-32,-22)
\put(0,-13){\vector(0,1){176}}
\put(0,-13){\vector(1,0){240}}
\put(-4,-5){\makebox(0,0)[rb]{others}}\put(1,-5){\framebox (217,6)[lb]{}}
\put(-4,10){\makebox(0,0)[rb]{Ireland}}\put(1,10){\framebox (18,6)[lb]{}}
\put(-4,23){\makebox(0,0)[rb]{Italy}}\put(1,25){\framebox (30,6)[lb]{}}
\put(-4,40){\makebox(0,0)[rb]{Canada}}\put(1,40){\framebox (30,6)[lb]{}}
\put(-4,55){\makebox(0,0)[rb]{UK}}\put(1,55){\framebox (37,6)[lb]{}}
\put(-4,70){\makebox(0,0)[rb]{France}}\put(1,70){\framebox (44,6)[lb]{}}
\put(-4,83){\makebox(0,0)[rb]{Japan}}\put(1,85){\framebox (47,6)[lb]{}}
\put(-4,100){\makebox(0,0)[rb]{Sweden}}\put(1,100){\framebox (52,6)[lb]{}}
\put(-4,113){\makebox(0,0)[rb]{Germany}}\put(1,115){\framebox (108,6)[lb]{}}
\put(-4,128){\makebox(0,0)[rb]{USA
(com)}}\put(1,130){\framebox (188,6)[lb]{}}
\put(-4,143){\makebox(0,0)[rb]{USA
(edu)}}\put(1,145){\framebox (229,6)[lb]{}}
\put(50,-15){\line(0,1){4}}
\put(100,-15){\line(0,1){4}}\put(100,-22){\makebox(0,0){10\%}}
\put(150,-15){\line(0,1){4}}
\put(200,-15){\line(0,1){4}}\put(200,-22){\makebox(0,0){20\%}}
\end{picture}
\end{center}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{paragraph}
{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline356}%
$(4/3-\varepsilon )$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline358}%
$(1+\ln 
n)$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

\stepcounter{paragraph}
{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline360}%
$\leq 4/3$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline362}%
$\leq 3/2$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{section}

\end{document}
