This is pdfTeX, Version 3.14159-1.10b (Web2C 7.4.5) (format=pdftex 2006.8.17)  30 OCT 2008 17:07
**guoli_ding.tex
(./guoli_ding.tex{/usr/share/texmf/pdftex/config/pdftex.cfg}
! Undefined control sequence.
l.1 \documentclass
                  {rutcor}
? 
! Undefined control sequence.
l.2 \usepackage
               {amsmath,amssymb,euscript,graphicx}
? 
! Undefined control sequence.
l.3 \newcommand
               {\qed}{\hfill\rule{1 ex}{1 ex}}
? 
! Undefined control sequence.
l.3 \newcommand{\qed
                    }{\hfill\rule{1 ex}{1 ex}}
? 
! Undefined control sequence.
l.3 \newcommand{\qed}{\hfill\rule
                                 {1 ex}{1 ex}}
? 
! Undefined control sequence.
l.5 \title
          {
? 
! Undefined control sequence.
l.9 \author
           {
? 
! Undefined control sequence.
l.10 Peter Chen\affiliation
                           {Department of Computer Science, Louisiana State ...

? 
! Undefined control sequence.
l.11 \and
         
? 
! Undefined control sequence.
l.12 Guoli Ding\affiliation
                           {Department of Mathematics, Louisiana State Unive...

? 
! Undefined control sequence.
l.15 \authornames
                 {
? 
! Undefined control sequence.
l.17 \and
         
? 
! Undefined control sequence.
l.21 \acknowledgement
                     {
? 
! Argument of \\ has an extra }.
<inserted text> 
                \par 
<to be read again> 
                   }
l.24 }
      
? 
Runaway argument?
*[\parskip ] \hspace *{1.5em} 
! Paragraph ended before \\ was complete.
<to be read again> 
                   \par 
<to be read again> 
                   }
l.24 }
      
? 
! Undefined control sequence.
l.26 \abstract
              {
? 
! Undefined control sequence.
l.27 ...aced by a weighted set, which we call {\em
                                                   cost}. Second, each eleme...

? 
! Argument of \\ has an extra }.
<inserted text> 
                \par 
<to be read again> 
                   }
l.28 {\bf Keywords:} Set cover, Greedy algorithm.}
                                                  
? 
Runaway argument?
 {\bf Keywords:} Set cover, Greedy algorithm.
! Paragraph ended before \\ was complete.
<to be read again> 
                   \par 
<to be read again> 
                   }
l.28 {\bf Keywords:} Set cover, Greedy algorithm.}
                                                  
? 
! Undefined control sequence.
l.30 \rrr
         {16-2008}
? 
! Undefined control sequence.
l.31 \date
          {}
? 
! Undefined control sequence.
l.33 \begin
           {document}
? 
! Undefined control sequence.
l.34 \maketitle
               
? 
! Undefined control sequence.
l.36 \section
             {Introduction}
? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.40 ...first have some definitions. If $\EuScript
                                                   X$ is a finite collection...

? 
! Undefined control sequence.
l.40 ...lection of sets, then $\overline{\EuScript
                                                   X}$ is the union of all m...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.40 ... is the union of all members of $\EuScript
                                                   X$. If $f$ is a function ...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.42 Let $S$ be a finite set and let $\EuScript
                                                S=\{S_1,S_2, \dots, S_n\}$, ...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.42 ..._i$ is a subset of $S$. We call $\EuScript
                                                   A \subseteq \EuScript S$ ...

? 
! Undefined control sequence.
l.42 .... We call $\EuScript A \subseteq \EuScript
                                                   S$ a {\em cover} of $\EuS...

? 
! Undefined control sequence.
l.42 ...$\EuScript A \subseteq \EuScript S$ a {\em
                                                   cover} of $\EuScript S$ i...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.42 ...q \EuScript S$ a {\em cover} of $\EuScript
                                                   S$ if $\overline{\EuScrip...

? 
! Undefined control sequence.
l.42 ...} of $\EuScript S$ if $\overline{\EuScript
                                                   A} = \overline{\EuScript ...

? 
! Undefined control sequence.
l.42 ...verline{\EuScript A} = \overline{\EuScript
                                                   S}$. The classical {\em s...

? 
! Undefined control sequence.
l.42 ...overline{\EuScript S}$. The classical {\em
                                                   set covering problem} (SC...

? 
! Undefined control sequence.
l.42 .... In applications, there is usually a {\em
                                                   weight} function $w$ from...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.42 ... {\em weight} function $w$ from $\EuScript
                                                   S$ to $R_+$. In such a si...

? 
! Undefined control sequence.
l.42 ...S$ to $R_+$. In such a situation, the {\em
                                                   total weight} of a cover ...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.42 ...e {\em total weight} of a cover $\EuScript
                                                   A$ is defined to be $w(\E...

? 
! Undefined control sequence.
l.42 ...\EuScript A$ is defined to be $w(\EuScript
                                                   A)$. The {\em weighted SC...

? 
! Undefined control sequence.
l.42 ...s defined to be $w(\EuScript A)$. The {\em
                                                   weighted SCP} (WSCP) is t...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.44 ... weight. Third, we only require $\EuScript
                                                   A$ to cover a portion of ...

? 
! Undefined control sequence.
l.44 ...to cover a portion of $\overline{\EuScript
                                                   S}$, instead of the entir...

? 
! Undefined control sequence.
l.44 ...instead of the entire $\overline{\EuScript
                                                   S}$.
? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.46 Let $S$ and $\EuScript
                            S$ be as before. Let $d$ be a function from $S$ ...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.46 ...nd let $\lambda\in [0,1]$. Then $\EuScript
                                                   A\subseteq \EuScript S$ i...

? 
! Undefined control sequence.
l.46 ...,1]$. Then $\EuScript A\subseteq \EuScript
                                                   S$ is called a {\em $\lam...

? 
! Undefined control sequence.
l.46 ...t A\subseteq \EuScript S$ is called a {\em
                                                   $\lambda$-$d$-cover} of $...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.46 ... a {\em $\lambda$-$d$-cover} of $\EuScript
                                                   S$ if $d(\overline{\EuScr...

? 
! Undefined control sequence.
l.46 ...of $\EuScript S$ if $d(\overline{\EuScript
                                                   A})\ge \lambda d(\overlin...

? 
! Undefined control sequence.
l.46 ...cript A})\ge \lambda d(\overline{\EuScript
                                                   S})$. Notice that, when $...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.46 ...positive for all $x\in S$, then $\EuScript
                                                   A$ is a cover if and only...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.48 ...function from $W$ to $R_+$, and $\EuScript
                                                   W = \{W_1,W_2, \dots, W_n...

? 
! Undefined control sequence.
l.48 ...of $W$. We consider each $W_i$ as the {\em
                                                   weight} of $S_i$. For any...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.48 ... {\em weight} of $S_i$. For any $\EuScript
                                                   A \subseteq \EuScript S$,...

? 
! Undefined control sequence.
l.48 .... For any $\EuScript A \subseteq \EuScript
                                                   S$, we define $\EuScript ...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.48 ...ubseteq \EuScript S$, we define $\EuScript
                                                   W(\EuScript A) = \bigcup ...

? 
! Undefined control sequence.
l.48 ...cript S$, we define $\EuScript W(\EuScript
                                                   A) = \bigcup \{W_i: S_i\i...

? 
! Undefined control sequence.
l.48 ...cript A) = \bigcup \{W_i: S_i\in \EuScript
                                                   A\}$ and we call $c(\EuSc...

? 
! Undefined control sequence.
l.48 ...in \EuScript A\}$ and we call $c(\EuScript
                                                   W(\EuScript A))$ the {\em...

? 
! Undefined control sequence.
l.48 ... A\}$ and we call $c(\EuScript W(\EuScript
                                                   A))$ the {\em cost} of $\...

? 
! Undefined control sequence.
l.48 ...all $c(\EuScript W(\EuScript A))$ the {\em
                                                   cost} of $\EuScript A$. I...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.48 ...EuScript A))$ the {\em cost} of $\EuScript
                                                   A$. In particular, if $W ...

? 
! Undefined control sequence.
l.48 ..., then it is easy to see that $c(\EuScript
                                                   W(\EuScript A))$ is exact...

? 
! Undefined control sequence.
l.48 ... easy to see that $c(\EuScript W(\EuScript
                                                   A))$ is exactly $w(\EuScr...

? 
! Undefined control sequence.
l.48 ...t W(\EuScript A))$ is exactly $w(\EuScript
                                                   A)$. Therefore, ``cost" i...

? 
! Undefined control sequence.
l.51 \noindent {\bf Generalized SCP (GSCP):} {\em
                                                  For any given $(S, W, \EuS...

? 
! Undefined control sequence.
l.51 ...CP):} {\em For any given $(S, W, \EuScript
                                                   S, \EuScript W, d, c, \la...

? 
! Undefined control sequence.
l.51 ...r any given $(S, W, \EuScript S, \EuScript
                                                   W, d, c, \lambda)$, find ...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.51 ..., find a $\lambda$-$d$-cover of $\EuScript
                                                   S$ with the minimum cost.}
? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.54 In case $W = \{1, 2, ..., n\}$, $\EuScript
                                                W=\{\{1\},\{2\}, ..., \{n\}\...

? 
! Undefined control sequence.
l.54 ...or all $x\in S$, our GSCP is known as {\em
                                                   partial set cover problem...

? 
! Undefined control sequence.
l.54 ...em partial set cover problem} (PSCP) \cite
                                                  {kearns}, which has the ob...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.54 ...ch has the objective of finding $\EuScript
                                                   A \subseteq \EuScript S$ ...

? 
! Undefined control sequence.
l.54 ...f finding $\EuScript A \subseteq \EuScript
                                                   S$ with $|\overline{\EuSc...

? 
! Undefined control sequence.
l.54 ...eq \EuScript S$ with $|\overline{\EuScript
                                                   A}|\ge \lambda |\overline...

? 
! Undefined control sequence.
l.54 ...Script A}|\ge \lambda |\overline{\EuScript
                                                   S}|$ and such that $w(\Eu...

? 
! Undefined control sequence.
l.54 ...{\EuScript S}|$ and such that $w(\EuScript
                                                   A)$ is minimized.
? 
! Undefined control sequence.
l.56 GSCP is also related to the {\em
                                      submodular set cover problem} (SSCP) \...

? 
! Undefined control sequence.
l.56 ...submodular set cover problem} (SSCP) \cite
                                                  {wolsey}, which we briefly...

? 
! Undefined control sequence.
l.56 .... It is not difficult to verify (see \cite
                                                  {fujito}) that SSCP is a s...

? 
! Undefined control sequence.
l.56 ...ase of GSCP if $U=\cal S$ and $f(\EuScript
                                                   A)=\min\{\lambda d(\bar{\...

? 
! Undefined control sequence.
l.56 ...\EuScript A)=\min\{\lambda d(\bar{\mathcal
                                                   S}), d(\bar{\EuScript A})...

? 
! Undefined control sequence.
l.56 ...mbda d(\bar{\mathcal S}), d(\bar{\EuScript
                                                   A})\}$, for all $\EuScrip...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.56 ...(\bar{\EuScript A})\}$, for all $\EuScript
                                                   A\subseteq \EuScript S$, ...

? 
! Undefined control sequence.
l.56 ...$, for all $\EuScript A\subseteq \EuScript
                                                   S$, which is exactly the ...

? 
! Undefined control sequence.
<recently read> \EuScript 
                          
l.56 ...with $W = \{1, 2, ..., n\}$ and $\EuScript
                                                   W=\{\{1\},\{2\}, ..., \{n...

? 
! Undefined control sequence.
l.56 ...odular function (the function $f(\EuScript
                                                   A)$ defined above, see \c...

? 
! Undefined control sequence.
l.56 ... $f(\EuScript A)$ defined above, see \cite
                                                  {fujito}), SSCP in general...

? 
[1{/usr/share/texmf/dvips/config/pdftex.map}]
! Undefined control sequence.
l.58 \begin
           {figure}[htbp]
? 
! Undefined control sequence.
l.59 \begin
           {center}
? 
! Undefined control sequence.
l.60 \includegraphics
                     [scale=1]{comparison.eps}
? 
! Undefined control sequence.
l.61 \caption
             {GSCP and SSCP are different generalizations of PSCP.}
? 
[2] ){/usr/share/texmf/dvips/tetex/f7b6d320.enc}</usr/share/texmf/fonts/type1/b
luesky/cm/cmbx10.pfb></usr/share/texmf/fonts/type1/bluesky/cm/cmex10.pfb>{/usr/
share/texmf/dvips/tetex/aae443f0.enc}</usr/share/texmf/fonts/type1/bluesky/cm/c
mmi7.pfb>{/usr/share/texmf/dvips/tetex/bbad153f.enc}</usr/share/texmf/fonts/typ
e1/bluesky/cm/cmsy10.pfb></usr/share/texmf/fonts/type1/bluesky/cm/cmsy7.pfb></u
sr/share/texmf/fonts/type1/bluesky/cm/cmr7.pfb></usr/share/texmf/fonts/type1/bl
uesky/cm/cmmi10.pfb></usr/share/texmf/fonts/type1/bluesky/cm/cmr10.pfb>
Output written on guoli_ding.pdf (2 pages, 53271 bytes).