text:
\section{Introduction}
A wireless sensor network (WSN) consists of spatially distributed autonomous sensors to monitor physical or environmental condition, and to cooperatively pass their data through the network. During recent years, WSN has been widely used in many fields, such as environment and habitat monitoring, disaster recovery, health applications, etc. Since there is no fixed or predefined infrastructure in WSNs, frequent flooding of control messages from sensors may cause a lot of redundant contentions and collisions. Therefore, people have proposed the concept of virtual backbone which corresponds to a connected dominating set in a graph (Das and Bhargharan \cite{Das} and Ephremides {\it et al.} \cite{Ephremides}).

Given a graph $G$ with node set $V$ and edge set $E$, a subset of nodes $C\subseteq V$ is said to be a {\em dominating set} (DS) of $G$ if any $v\in V\setminus C$ is adjacent to at least one node of $C$. We say that a dominating set $C$ of $G$ is a {\em connected dominating set} of $G$ if the subgraph of $G$ induced by $C$, denoted by $G[C]$, is connected. Nodes in $C$ are called {\em dominators}, the nodes in $V\setminus C$ are called {\em dominatees}.

Because sensors in a WSN are prone to failures due to accidental damage or battery depletion, it is important to maintain a certain degree of redundancy such that the virtual backbone is more fault-tolerant. In a more general setting, every sensor has a cost, it is desirable that under the condition that tasks can be successfully accomplished, the whole cost of virtual backbone is as small as possible. These considerations lead to the Minimum Node-Weighted $k$-Connected $m$-Fold Dominating Set problem (abbreviated as $(k,m)$-MWCDS), which is defined as follows:

\begin{definition}[$(k,m)$-MWCDS]
{\rm Let $G$ be a connected graph, $k$ and $m$ be two positive integers, $c:V\rightarrow R^{+}$ be a cost function on nodes. A node subset $D\subseteq V$ is an $m$-fold dominating set ($m$-DS) if every node in $V\setminus D$ has at least $m$ neighbors in $D$. It is a $k$-connected $m$-fold dominating set ($(k,m)$-CDS) if furthermore, the subgraph of $G$ induced by $D$ is $k$-connected. The $(k,m)$-MWCDS problem is to find a $(k,m)$-CDS $D$ such that the cost of $D$ is minimized, that is, $c(D)=\sum_{u\in D}c(u)$ is as small as possible.}
\end{definition}

After Dai and Wu \cite{Dai} proposed using $(k,k)$-CDS as a model for fault-tolerant virtual backbone, a lot of approximation algorithms emerged, most of which are on unit disk graphs. In a {\rm unit disk graph} (UDG), every node corresponds to a sensor on the plane, two nodes are adjacent if and only if the Euclidean distance between the corresponding sensors is at most one unit. There are a lot of studies on fault-tolerant virtual backbone in UDG which assume unit weight on each disk. However, for a general graph with a general weight function, related studies are rare.

In this paper, we present a $(H(\delta+m)+2H(\delta-1))$-approximation algorithm for the $(1,m)$-MWCDS problem on a general graph, where $\delta$ is the maximum degree of the graph, and $H(\gamma)=\sum_{1}^\gamma 1/i$ is the Harmonic number. It is a two-phase greedy algorithm. First, it constructs an $m$-fold dominating set $D_1$ of $G$. Then it connects $D_1$ by adding a set of connectors $D_2$. It is well known that if the potential function and the cost function related with a greedy algorithm is monotone increasing and submodular, then an $O(\ln n)$ performance ration can be achieved. Unfortunately, for various minimum CDS problems, no such potential functions are known. Nevertheless, we manage, in this paper, to deal with a nonsubmodular potential function and achieve an $O(\ln \delta)$ performance ratio.

It should be pointed out that for a general graph, Guha and Khuller \cite{Guha} proposed a $1.35\ln n$-approximation for the $(1,1)$-MWCDS problem. Though our constant in $O(\ln n)$ is larger, the parameter $n$ in the performance ratio is replaced by $\delta$. In many cases, $\delta$ might be substantially smaller than $n$. In particular, for an UDG, due to such an replacement, after having found an $m$-DS, the connecting part has a performance ratio at most $3.67$. In \cite{Zou1}, Zou {\it et al.} proposed a method for the connecting part with performance ratio at most $3.875$, which makes use of a $1.55$-approximation algorithm \cite{Robin} for the classic Minimum Steiner Tree problem. If using currently best ratio for Minimum Steiner Tree problem \cite{Byrka}, then their ratio is at most $3.475$. Notice that the algorithm in \cite{Byrka} uses randomized iterative rounding. So, although our ratio 3.67 is a litter larger than $3.475$, our algorithm has the advantage that it is purely combinatorial. Furthermore, we believe that our method is also of more theoretical interests and may find more applications in the study of other related problems.

The rest of this paper is organized as follows. Section \ref{sec.2} introduces related works. Some notation and some preliminary are given in Section \ref{sec.3}. In Section \ref{sec-algorithm}, the algorithm is presented. Section \ref{sec.5} analyzes the performance ratio. Section \ref{secUDG} improves the ratio on unit disk graph. Section \ref{sec.7} concludes the paper.

\section{Related work}\label{sec.2}

The idea of using a connected dominating set as a virtual backbone for WSN was proposed by Das and Bhargharan \cite{Das} and Ephremides {\it et al.} \cite{Ephremides}. Constructing a CDS of the minimum size is NP-hard. In fact, Guha and Khuller \cite{Guha} proved that a minimum CDS cannot be approximated within $\rho\ln n$ for any $0<\rho<1$ unless $NP\subseteq DTIME(n^{O(loglog n)})$. In the same paper, they proposed two greedy algorithms with performance ratios of $2(H(\delta)+1)$ and $H(\delta)+2$, respectively, where $\delta$ is the maximum degree of the graph and $H(\cdot)$ is the harmonic number. This was improved by Ruan {\it et al.} \cite{Ruan} to $2+\ln\delta$. Du {\it et al.} \cite{Du} presented a $(1+\varepsilon)\ln(\delta-1)$-approximation algorithm, where $\varepsilon$ is an arbitrary positive real number.

For unit disk graphs, a polynomial time approximation scheme (PTAS) was given by Cheng {\it et al.} \cite{Cheng}, which was generalized to higher dimensional space by Zhang {\it et al.} \cite{Zhang1}. There are a lot of studies on distributed algorithms for this problem. For a comprehensive study on CDS in UDG, the readers may refer to the book \cite{DuBookCDS}.

Considering the weighted version of the CDS problem, Guha and Khuller \cite{Guha} proposed a $(c_{n}+1)\ln n$-approximation algorithm in a general graph, where $c_{n}\ln k$ is the performance ratio for the node weighted Steiner tree problem ($k$ is the number of terminal nodes to be connected). Later, they \cite{Guha1} improved it to an algorithm of performance ratio at most $(1.35+\varepsilon)\ln n$. For the minimum weight CDS in UDG, Zou {\it et al.} \cite{Zou1} gave a $(9.875+\varepsilon)$-approximation.

The problem of constructing fault-tolerant virtual backbones was introduced by Dai and Wu \cite{Dai}. They proposed three heuristic algorithms for the minimum $(k,k)$-CDS problem. However, no performance ratio analysis was given. A lot of works have been done for the CDS problem in UDG. The first constant approximation algorithm in this aspect was given by Wang {\it et al.} \cite{Wang}, who obtained a 72-approximation for the $(2,1)$-CDS problem in UDG. Shang {\it et al.} \cite{Shang} gave an algorithm for the minimum $(1,m)$-CDS problem and an algorithm for the minimum $(2,m)$-CDS problem in UDG, the performance ratios are $5+\frac{5}{m}$ for $m\leq5$ and $7$ for $m>5$, and $5+\frac{25}{m}$ for $2\leq m\leq5$ and $11$ for $m>5$, respectively. Constant approximation algorithms also exist for $(3,m)$-CDS in UDG \cite{WangWei,WangWei2}. Recently, Shi {\it et al.} \cite{ShiZhang} presented the first constant approximation algorithm for general $(k,m)$-CDS on UDG.

For the fault-tolerant CDS problem in a general graph, Zhang {\it et al.} \cite{Zhang2} gave a $2rH(\delta_r+m-1)$-approximation
for the minimum $r$-hop $(1,m)$-CDS problem, where $\delta_r$ is the maximum degree in $G^r$, the $r$-th power graph of $G$. A node $u$ is $r$-hop dominated by a set $D$ if it is at most $r$-hops away from $D$. In particular, taking $r=1$, the algorithm in \cite{Zhang2} has performance ratio at most $2H(\delta+m-1)$ for the minimum $(1,m)$-CDS problem. This was improved by our recent work \cite{Zhou} to $2+H(\delta+m-2)$. We also gave an $(\ln\delta+o(\ln\delta))$-approximation algorithm for the minimum $(2,m)$-CDS problem \cite{Shi} and the minimum $(3,m)$-CDS problem \cite{ZhangZhou} on a general graph.

For the weighted version of fault-tolerant CDS problem on UDG, as a consequence of recent work \cite{LiJian}, the minimum weight $(1,1)$-CDS problem admits a PTAS. Combining the constant approximation algorithm for the minimum weight $m$-fold dominating set problem \cite{Fukunage} and the 3.475-approximation algorithm for the connecting part \cite{Zou1}, $(1,m)$-MWCDS on UDG admits a constant-approximation. Recently, we \cite{ShiZhang,ZhangShi} gave the first constant approximation algorithm for the general minimum weight $(k,m)$-CDS problem on unit disk graph.

As far as we know, there is no previous work on the approximation of the weighted version of fault-tolerant CDS problem in a general graph.

Notice that in \cite{Zou1}, the $3.875$-approximation for the connecting part is based on the 1.55-approximation algorithm \cite{Robin} for the classic minimum Steiner tree problem. If the best known ratio for the Steiner tree problem is used, which is $1.39$ currently, then their connecting part has performance ratio at most $3.475$. Notice that the $1.39$-approximation for the Steiner tree problem uses randomized iterative rounding. So, although our performance ratio is larger than $3.475$, it has the advantage that it is purely combinatorial.

\section{Preliminaries}\label{sec.3}

In this section, we introduce some notation and give some preliminary results. For a node $u\in V(G)$, denote by $N_G(u)$ the set of neighbors of $u$ in $G$, and $deg_G(u)=|N_G(u)|$ is the degree of node $u$ in $G$. For a node subset $D\subseteq V(G)$, $N_G(D)=\bigcup_{u\in D}N_G(u)\setminus D$ is the neighbor set of $D$, $G[D]$ is the subgraph of $G$ induced by $D$. When there is no confusion in the context, the vertex set of a subgraph will be used to denote the subgraph itself.

For an element set $U$, suppose $f:2^U\mapsto \mathbb R^+$ is a set function on $U$ (called a {\em potential function}). For two element sets $C,D\subseteq U$, let
$$
\bigtriangleup_Df(C)=f(C\cup D)-f(C)
$$
be the marginal profit obtained by adding $D$ into $C$. For simplicity, $\bigtriangleup_uf(C)$ will be used to denote $\bigtriangleup_{\{u\}}f(C)$ when $u$ is a node. Potential function $f$ is {\em monotone increasing} if $f(C)\leq f(D)$ holds for any subsets $C\subseteq D\subseteq V$. It is {\em submodular} if and only if $\bigtriangleup_uf(C)\geq\bigtriangleup_uf(D)$ holds for any $C\subseteq D\subseteq V$ and any $u\in V\setminus D$. A monotone increasing and submodular function $f$ with $f(\emptyset)=0$ is called a {\em polymatroid}. Given an element set $U$ with cost function $c:U\mapsto \mathbb R^+$ and given a polymatroid $f:2^U\mapsto \mathbb R^+$, denote by $\Omega_f=\{C\subseteq U\colon \bigtriangleup_uf(C)=0\ \mbox{for any $u\in U$}\}$. The {\em Submodular Cover} problem is:
\begin{align*}
\min &\ \ c(C)=\sum_{u\in C}c(u)\\
s.t. &\ \ C\in\Omega_f.
\end{align*}

The following is a classic result which can be found in \cite{DuBook} Theorem 2.29.
\begin{theorem}\label{thm-submodular-cover}
The greedy algorithm for the submodular cover problem has performance ratio $H(\gamma)$, where $\gamma=\max\{f(\{u\})\colon u\in U\}$ and $H(\gamma)=\sum_{i=1}^\gamma 1/i$ is the Harmonic number.
\end{theorem}

\section{The Algorithm}\label{sec-algorithm}

\subsection{The Algorithm}

For a node set $C$, denote by $p(C)$ the number of components in $G[C]$. For a node $u\in V\setminus C$, let $N_C(u)$ denote the set of neighbors of $u$ in $C$. Define
$$
q_C(u)=\left\{\begin{array}{ll}\max\{m-|N_C(u)|,0\}, & u\in V\setminus C,\\ 0, & u\in C,\end{array}\right.
$$
and
$$
q(C)=m|V|-\sum_{u\in V}q_C(u).
$$

For a node set $U\subseteq V$, denote by $NC_C(U)$ the set of components of $G[C]$ which are adjacent to $U$. Every component in $NC_C(U)$ is called a {\em component neighbor} of $U$ in $G[C]$. For a node $u\in V$, we shall use $S_u$ to denote some star with center $u$, that is, $S_u$ is a subgraph of $G$ induced by edges between node $u$ and some of $u$'s neighbors in $G$. In particular, a node is a star of cardinality one and  an edge is a star of cardinality two. To abuse the notation a little, we also use $S_u$ to denote the set of nodes in $S_u$. Suppose $S_u\setminus\{u\}=\{u_{1},u_{2},\ldots,u_{s}\}$, where $c(u_{1})\leq c(u_{2})\leq\ldots\leq c(u_{s})$. Define
\begin{equation}\label{eq14-11-14-2}
p'_{C}(S_u)=|NC_{C}(u)|-1+\sum_{i=1}^{s}\min\{1,
-\bigtriangleup_{u_{i}}p(C\cup\{u,u_{1},\ldots,u_{i-1}\})\}.
\end{equation}
Call $e_C(S_u)=p'_C(S_u)/c(S_u)$ the {\em efficiency of $S_u$ with respect to $C$}.

The algorithm is presented in Algorithm \ref{alg10-6-1}.

\begin{algorithm}[h!]
\caption{\textbf{}}
 Input: A connected graph $G=(V,E)$.

Output: A $(1,m)$-CDS $D_G$ of $G$.
\begin{algorithmic}[1]
    \State Set $D_1$ $\leftarrow$ $\emptyset$
    \While{there exists a node $u\in V\setminus D_1$ such that $\bigtriangleup_uq(D_1)> 0$, }
       \State select $u$ which maximizes $\bigtriangleup_u q(D_1)/c(u)$
       \State $D_1 \leftarrow D_1\cup \{u\}$
    \EndWhile
      \State Set $D_2\leftarrow\emptyset$
    \While{there exists a star $S_u\subseteq V\setminus (D_1\cup D_2)$ such that $p_{D_1\cup D_2}'(S_u)> 0$, }
       \State select a star $S_u$ with the largest efficiency with respect to $D_1\cup D_2$.
       \State $D_2 \leftarrow D_2\cup S_u$
    \EndWhile
    \State Output  $D_{G}\leftarrow D_1\cup D_2$
\end{algorithmic}\label{alg10-6-1}
\end{algorithm}

\subsection{The Idea of the Algorithm}
The idea underlying the algorithm is as follows. Potential function $q_{D_1}(u)$ measures how many more times that node $u$ needs to be dominated, and $q(D_1)$ is the total residual domination requirement. As can be seen from Lemma \ref{le10-8-1}, at the end of the first phase, we have an $m$-fold dominating set $D_1$. Then, the second phase aims to connect it by adding a connector set $D_2$. A natural potential function for connection is $p(D_1\cup D_2)$, the number of components of $G[D_1\cup D_2]$. That is, every iteration chooses a node set $S$ to be added into $D_2$ which reduces the number of components by the largest amount until $p(D_1\cup D_2)$ reaches 1. It is a folklore result (see Lemma \ref{lem14-11-22-6}) that simultaneously adding at most two nodes can reduce the number of components (even when ading any single node does not reduce the number of components). So, it is natural to use
\begin{equation}\label{eq14-11-14-1}
\max\{-\bigtriangleup_Sp(D_1\cup D_2)/c(S)\colon S\subseteq V\setminus (D_1\cup D_2),1\leq |S|\leq 2\}
\end{equation}
to work as a criterion for the choice of node set $S$ to be added into $D_2$. However, choosing at most two nodes might yield a solution with very bad performance ratio. Consider the example shown in Fig.\ref{fig11-01-1}, its optimal solution $OPT=\{u,v_1,\ldots,v_d\}$ has cost $opt=1+(d+1)\varepsilon$. If \eqref{eq14-11-14-1} is used as the greedy criterion, then the output is $\bigcup_{i=1}^{d}\{u_{i},v_{i}\}$, whose cost is $c(\bigcup_{i=1}^{d}\{u_{i},v_{i}\})=d(1+\varepsilon)\approx d\cdot opt=\frac{n-2}{3}opt$. To overcome such a shortcoming, an idea is to choose some star $S_u$ to maximize $-\bigtriangleup_{S_u}p(D_1\cup D_2)/c(S_u)$ in each iteration. However, the computation of a most efficient star will take exponential time. This is why we define $p'$ as in \eqref{eq14-11-14-2} to be used in the greedy criterion. On one hand, $p'$ also plays the role of counting the reduction on components. On the other hand, a most efficient $S_u$ to maximize $p'_{D_1\cup D_2}(S_u)/c(S_u)$ can be found in polynomial time, which will be shown in Subsection \ref{subsec4.2}.

\begin{figure*}[!htbp]
\setlength{\unitlength}{1mm}
\begin{center}
\begin{picture}(100,70)
\put(50,65){\circle*{1.5}}
\put(50,55){\circle{1.5}}
\put(40,50){\circle{1.5}}
\put(30,50){\circle{1.5}}
\put(60,50){\circle{1.5}}
\put(70,50){\circle{1.5}}

\put(50,65){\line(0,-1){9.25}}
\put(50,65){\line(-2,-3){9.55}}
\put(50,65){\line(-4,-3){19.35}}
\put(50,65){\line(2,-3){9.55}}
\put(50,65){\line(4,-3){19.35}}

\put(40,40){\circle{1.5}}
\put(30,40){\circle{1.5}}
\put(60,40){\circle{1.5}}
\put(70,40){\circle{1.5}}
\put(40,40.75){\line(0,1){8.5}}
\put(30,40.75){\line(0,1){8.5}}
\put(60,40.75){\line(0,1){8.5}}
\put(70,40.75){\line(0,1){8.5}}

\put(30.5,40.5){\line(4,3){18.9}}
\put(40.5,40.5){\line(2,3){9.25}}
\put(59.5,40.5){\line(-2,3){9.25}}
\put(69.5,40.5){\line(-4,3){18.9}}
\put(48,28){\makebox(4,2)[tl]{\hbox{$\ldots$}}}
\put(48,38){\makebox(4,2)[tl]{\hbox{$\ldots$}}}
\put(30.5,28){$\underbrace{\makebox{}\qquad\qquad\qquad\qquad\qquad\,}$}
\put(50.5,23){\makebox(4,2)[tl]{\hbox{$d$}}}

\put(40,30){\circle*{1.5}}
\put(30,30){\circle*{1.5}}
\put(60,30){\circle*{1.5}}
\put(70,30){\circle*{1.5}}
\put(30,39.25){\line(0,-1){9}}
\put(40,39.25){\line(0,-1){9}}
\put(60,39.25){\line(0,-1){9}}
\put(70,39.25){\line(0,-1){9}}

\put(52,55){\makebox(4,2)[tl]{\hbox{$u$}}}
\put(25,50){\makebox(4,2)[tl]{\hbox{$u_{1}$}}}
\put(35,50){\makebox(4,2)[tl]{\hbox{$u_{2}$}}}
\put(61,50){\makebox(4,2)[tl]{\hbox{$u_{d-1}$}}}
\put(71,50){\makebox(4,2)[tl]{\hbox{$u_{d}$}}}
\put(25,40){\makebox(4,2)[tl]{\hbox{$v_{1}$}}}
\put(35,40){\makebox(4,2)[tl]{\hbox{$v_{2}$}}}

\put(61,40){\makebox(4,2)[tl]{\hbox{$v_{d-1}$}}}
\put(71,40){\makebox(4,2)[tl]{\hbox{$v_{d}$}}}

\end{picture}
\vskip -2.5cm\caption{Solid nodes represent nodes in $C$. The costs on circled nodes are $c(u_{1})=c(u_{2})=\ldots=c(u_{d})=1$,
$c(v_{1})=c(v_{2})=\ldots=c(v_{d})=\varepsilon$, and $c(u)=1+\varepsilon$.}\label{fig11-01-1}
\end{center}
\end{figure*}

\section{The Analysis of the Algorithm}\label{sec.5}

In this section, we analyze the performance ratio of Algorithm \ref{alg10-6-1}.

\subsection{The Analysis of $D_1$}

\begin{lemma}\label{lem14-11-14-3}
Function $q$ is a polymatroid.
\end{lemma}
\begin{proof}
Obviously, $q(\emptyset)=0$. It is easy to see that for any node $u\in V$, function $-q_C(u)$ is monotone increasing and submodular with respect to $C$. So, function $q$, being the summation of a constant function and some monotone increasing and submodular functions, is also monotone increasing and submodular.
\end{proof}

\begin{lemma}\label{le10-8-1}
The final node set $D_1$ in Algorithm \ref{alg10-6-1} is an $m$-fold dominating set of $G$.
\end{lemma}
\begin{proof}
If there exists a node $u\in V\backslash D_1$ with $|N_{D_1}(u)|<m$, then $-\bigtriangleup_uq_{D_1}(u)=-q_{D_1\cup\{u\}}(u)+q_{D_1}(u)=-0+(m-|N_{D_1}(u)|)>0$, and $-\bigtriangleup_uq_{D_1}(v)\geq 0$ for any node $v\in V\setminus \{u\}$ (by the monotonicity of $-q_{D_1}(v)$ with respect to $D_1$). Thus $\bigtriangleup_{u}q(D_1)=-\sum_{v\in V}\bigtriangleup_{u}q_{D_1}(v)>0$, and the algorithm does not terminate at this stage.
\end{proof}

\begin{theorem}\label{thm14-11-25-1}
The final node set $D_1$ in Algorithm \ref{alg10-6-1} has weight $w(D_1)\leq H(m+\delta)\cdot opt$, where $\delta$ is the maximum degree of graph $G$, and $opt$ is the optimal value for the $m$-MWCDS problem.
\end{theorem}
\begin{proof}
By Lemma \ref{lem14-11-14-3} and Lemma \ref{le10-8-1}, the minimum weight $m$-fold dominating set problem is a special submodular cover problem with potential function $q$. So by Theorem \ref{thm-submodular-cover}, we have $w(D_1)\leq H(\gamma)\cdot opt'$, where $opt'$ is the optimal value for the $m$-MWDS problem. Then, the result follows from the observation that $opt'\leq opt$ and $\gamma=\max\limits_{u\in V}\{q(\{u\})\}=\max\limits_{u\in V}\{m|V|-\sum_{v\in V\setminus\{u\}}(m-|N_{\{u\}}(v)|)\}=\max\limits_{u\in V}\{m+d_G(u)\}=m+\delta$.
\end{proof}

\subsection{The Computation of an Optimal Star for Greedy Choice}\label{subsec4.2}

The idea for the definition of $p'_C(S_u)$ is as follows: Adding node $u$ into $C$ will merge those components in $NC_C(u)$ into one component of $G[C\cup \{u\}]$, say $\widetilde C$, which reduces the number of components by $|NC_C(u)|-1$. Then adding nodes in $S_u\setminus \{u\}$ sequentially according to the increasing order of their costs. Notice that \begin{equation}\label{eq14-11-22-5}
-\bigtriangleup_{u_i}p(C\cup\{u_1,\ldots,u_{i-1}\})=|NC_C(u_i)\setminus NC_C(u,u_1,\ldots,u_{i-1})|
\end{equation}
is the number of components newly merged into $\widetilde C$. So, the term in the summation of definition \eqref{eq14-11-14-2} indicates that if adding $u_i$ merges at least one more component, we regard its contribution to $p'_C(S_u)$ as one. The advantage of such a counting is that an optimal star for the greedy criterion is polynomial-time computable. This claim is based on the following lemma. A simple relation will be used in the proof: for four positive real numbers $a,b,c,d$
\begin{equation}\label{eq14-11-16-4}
\frac{a+b}{c+d}\geq \frac{b}{d}\Rightarrow \frac{a}{c}\geq \frac{b}{d}.
\end{equation}

\begin{lemma}\label{le10-30-1}
Suppose $C$ is a dominating set of graph $G$. Then, there exists a most efficient star $S_u$ with respect to $C$ such that $|NC_C(v)|=1$ for every node $v\in S_u\setminus \{u\}$. Furthermore, if we denote by $C_v$ the unique component in $NC_C(v)$, then components in $\{C_v\}_{v\in S_u\setminus\{u\}}$ are all distinct and they are also distinct from those components in $NC_C(u)$.
\end{lemma}
\begin{proof}
Suppose $S_u$ is a most efficient star with $S_u\setminus \{u\}=\{u_1,\ldots,u_s\}$ such that $c(u_1)\leq \ldots\leq c(u_s)$. We first show that for any $i=1,\ldots,s$,
\begin{equation}\label{eq14-11-22-2}
-\bigtriangleup_{u_{i}}p(C\cup\{u,u_{1},\ldots,u_{i-1}\})\geq 1.
\end{equation}
Suppose this is not true. Let $i$ be the first index with $-\bigtriangleup_{u_{i}}p(C\cup\{u,u_{1},\ldots,u_{i-1}\})=0$. Then by \eqref{eq14-11-22-5}, we have $NC_C(u_i)\subseteq NC_C(u,u_1,\ldots,u_{i-1})$ and thus $NC_C(u,u_1,\ldots,u_{i-1})=NC_C(u,u_1,\ldots,u_i)$. It follows that for any $j>i$,
$$
-\bigtriangleup_{u_{j}}p(C\cup\{u,u_{1},\ldots,u_{i-1},u_{i+1},\ldots,u_{j-1}\})=-\bigtriangleup_{u_{i}}p(C\cup\{u,u_{1},\ldots,u_{j-1}\}).
$$
So, for the star $S_u'=S_u\setminus\{u_i\}$, we have $p'_C(S'_u)=p'_C(S_u)$ and thus $p'_C(S'_u)/c(S'_u)>p'_C(S_u)/c(S_u)$, contradicting the maximality of $p_C'(S_u)/c(S_u)$.

As a consequence of \eqref{eq14-11-22-2},
$$
p_C'(S_u)=|NC_C(u)|-1+s.
$$

Suppose there is a node $u_i$ with $|NC_C(u_i)|\geq 2$, we choose $u_i$ to be such that $i$ is as small as possible. Let $S_u'=S_u\setminus \{u_i\}$. Notice that for any $j>i$,
$$
-\bigtriangleup_{u_j}p(C\cup\{u,u_{1},\ldots,u_{i-1},u_{i+1},\ldots,u_{j-1}\})\geq -\bigtriangleup_{u_{i}}p(C\cup\{u,u_{1},\ldots,u_{j-1}\}).
$$
Combining this with \eqref{eq14-11-22-2}, we have
$$
p_C'(S_u')=|NC_C(u)|-1+(s-1)=p_C'(S_u)-1.
$$
By the maximality of $S_u$, we have
$$
\frac{p_C'(S_u')}{c(S_u')}\leq \frac{p_C'(S_u)}{c(S_u)}=\frac{p_C'(S_u')+1}{c(S_u')+c(u_i)}.
$$
Then by \eqref{eq14-11-16-4},
$$
\frac{p_C'(S_u')}{c(S_u')}\leq \frac{1}{c(u_i)}.
$$
It follows that
$$
\frac{p_C'(S_u)}{c(S_u)}=\frac{p_C'(S_u')+1}{c(S_u')+c(u_i)}\leq \frac{\frac{1}{c(u_i)}c(S_u')+1}{c(S_u')+c(u_i)}=\frac{1}{c(u_i)}\leq \frac{p_C'(u_i)}{c(u_i)},
$$
where the last inequality holds because $p_C'(u_i)=|NC_C(u_i)|-1\geq 1$. Hence $u_i$ is a also a most efficient star. It is a trivial star satisfing the requirement of the lemma.

Next, suppose $S_u$ is a nontrivial star in which every $v\in S_u\setminus\{u\}$ has $|NC_C(v)|=1$. Notice that an equivalent statement of \eqref{eq14-11-22-2} is that $|NC_C(u_i)\setminus NC_C(u,u_1,\ldots,u_{i-1})|\geq 1$ for any $i=1,\ldots,s$. The second part of this lemma follows.
\end{proof}

By Lemma \ref{le10-30-1}, a most efficient star with respect to $C$ can be found in the following way. Guessing the center of the star requires time $O(n)$. Suppose $u$ is the guessed center. Let $N^{(u)}=\{v\colon v\ \mbox{is a neighbor of}\ u\ \mbox{in}\ G\ \mbox{and}\ |NC_C(v)|=1\}$. Order the nodes in $N^{(u)}$ as $u_1,\ldots,u_s$ such that $c(u_1)\leq \ldots\leq c(u_s)$. For $i=1,\ldots,s$, scan $u_i$ sequentially. If $u_i$ has $NC_C(u_i)\subseteq NC_C(u,u_1,\ldots,u_{i-1})$, then remove it from $N^{(u)}$. For convenience of statement, suppose the remaining set $N^{(u)}=\{u_1,u_2\ldots,u_t\}$. Then, the node set of a most efficient star centered at $u$ must be of the form $\{u,u_1,u_2,\ldots,u_l\}$ for some $l\in\{0,\ldots,t\}$. So, it suffices to compute the efficiency of the $t+1$ sets $\{u,u_1,\ldots,u_l\}$ for $l=0,\ldots,t$ and choose the most efficient one from them. Clearly, such a computation can be done in polynomial time.

\subsection{Correctness of the Algorithm}

The following result is a folklore in the study of CDS (see, for example, \cite{Wan}).

\begin{lemma}\label{lem14-11-22-6}
Suppose $D$ is a dominating set of $G$ such that $G[D]$ is not connected. Then, two nearest components of $G[D]$ are at most three hops away.
\end{lemma}

\begin{theorem}
The output $D_G$ of Algorithm \ref{alg10-6-1} is a $(1,m)$-CDS.
\end{theorem}
\begin{proof}
By Lemma \ref{le10-8-1}, $D_1$ is an $m$-fold DS, and thus $D_G$ is also an $m$-DS. If $G[D_G]$ is not connected, consider two nearest components of $G[D_G]$, say $G_1$ and $G_2$. Let $P=u_0u_1\ldots u_t$ be a shortest path between $G_1$ and $G_2$, where $u_0\in V(G_1)$ and $u_t\in V(G_2)$. By Lemma \ref{lem14-11-22-6}, we have $t=2$ or $3$. Then, $u_1$ (in the case $t=2$) or $u_1u_2$ (in the case $t=3$) is a star $S_{u_1}$ with $p_{D_G}'(S_{u_1})>0$. The algorithm will not terminate.
\end{proof}

\subsection{Decomposition of Optimal Solution}

The following lemma, as well as its proof, can be illustrated by Fig.\ref{fig11-1-2}.

\begin{lemma}\label{lem10-6-3}
Let $G$ be a connected graph, $C$ be a dominating set of $G$ and $C^{*}$ be a connected dominating set of $G$. Then $C^{*}\backslash C$ can be decomposed into the union of node sets $C^{*}\backslash C=Y_0\cup Y_{1}\cup Y_{2}\cup,\ldots,\cup Y_{h}$ such that:

$(\romannumeral1)$ for $1\leq i\leq h$, subgraph $G[Y_{i}]$ contains a star;

$(\romannumeral2)$ subgraph $G[C\cup Y_{1}\cup Y_{2}\cup,\ldots,\cup Y_{h}]$ is connected;

$(\romannumeral3)$ for $1\leq i\leq h$, $|NC_C(Y_i)|\geq 2$;

$(\romannumeral4)$ any node of $C^{*}\backslash C$ belongs to at most two sets of $\{Y_0,Y_{1},Y_{2},\ldots,Y_{h}\}$.
\end{lemma}
\begin{proof}
Let $H$ be the graph obtained from $G[C\cup C^{*}]$ by contracting every component of $G[C]$ into a super-node (call it a terminal node). Since $G[C\cup C^{*}]$ is connected, $H$ is also connected, and thus $H$ contains a spanning tree $T$. Recursively pruning non-terminal leaves, we obtain a tree $T'$ in which every leaf is a terminal node (see Fig.\ref{fig11-1-2}(a)(b)). Let $Y_0$ be the set of pruned nodes. We may assume that
\begin{equation}\label{eq14-11-23-2}
\mbox{every non-terminal node has at least one terminal neighbor in $T'$.}
\end{equation}
In fact, if this is not true, then we can modify $T'$ into another tree satisfying this assumption. See Fig.\ref{fig11-1-2}(c)(d) for an illustration. In $(c)$, node $u$ does not have a terminal neighbor in $T'$. Since $C$ is a dominating set, $u$ is adjacent with some component of $G[C]$, say the component corresponding to terminal node $v$. Adding edge $uv$ creates a unique cycle in $T'+uv$. Removing the edge on this cycle which is incident with $u$ in $T'$, we have another tree in which $u$ has a terminal neighbor (see Fig.\ref{fig11-1-2}(d)). Notice that the removed edge is between two non-terminal nodes. So, the number of non-terminal nodes which have no terminal neighbors is strictly reduced. Recursively making such a modification results in a tree satisfying assumption \eqref{eq14-11-23-2}.

Tree $T'$ can be viewed as a Steiner tree. By splitting off at non-leaf terminal nodes, $T'$ can be decomposed into full components $T_1',\ldots,T_l'$ (a {\em full component} in a Steiner tree is a subtree in which a node is a leaf if and only if it is a terminal node, see Fig.\ref{eq14-11-23-2}(e)). Let $T_i$ be the subtree of $T_i'$ induced by those non-terminal nodes.

For each $i\in\{1,\ldots,l\}$, let $v_{i}$ be an arbitrary node of $T_{i}$ and view $T_i$ as a tree rooted at $v_i$. For each node $v\in V(T_i)$, let $S_v$ be the star centered at node $v$ which contains all children of $v$ in $T_i$. Let $\mathcal S_i=\{S_v\colon v\in V(T_i)\ \mbox{and}\ |NC_C(S_v)|\geq 2\}$. Let $\mathcal S=\bigcup_{i=1}^l\mathcal S_i$. Then $\{Y_v=V(S_v)\colon S_v\in\mathcal S\}$ is a desired decomposition of $C^*\setminus (C\cup Y_0)$ (see Fig.\ref{eq14-11-23-2}(f)).

It should be noted that property \eqref{eq14-11-23-2} is used to guarantee that no node is missed in the decomposition. For example, in Fig.\ref{eq14-11-23-2}(c) which does not satisfy this assumption, if we choose $x$ to be the root of the lower subtree, then $S_u=uy$ and $S_y=y$ are stars which does not have at least two terminal neighbors in $T'$, and thus they are excluded from $\mathcal S$. But then, node $y$ does not belong to any star in the decomposition.
\end{proof}

\begin{figure*}[!htbp]\setlength{\unitlength}{0.28mm}
 \begin{center}
 \hskip 0cm\begin{picture}(110,120)
 \put(20,110){\circle*{5}}
 \put(0,90){\circle*{5}}
 \put(20,90){\circle{5}}
 \put(40,90){\circle*{5}}
 \put(60,90){\circle{5}}
 \put(80,90){\circle{5}}
 \put(100,90){\circle*{5}}
 \put(40,70){\circle{5}}
 \put(80,70){\circle{3}}\put(80,70){\circle{5}}
 \put(0,50){\circle*{5}}
 \put(20,50){\circle{5}}
 \put(60,50){\circle{5}}
 \put(20,30){\circle{5}}
 \put(60,30){\circle*{5}}
 \put(80,30){\circle{3}}\put(80,30){\circle{5}}
 \put(0,10){\circle*{5}}
 \put(20,10){\circle*{5}}
 \put(60,10){\circle{3}}\put(60,10){\circle{5}}
 \put(80,10){\circle{3}}\put(80,10){\circle{5}}
 \put(100,10){\circle{3}}\put(100,10){\circle{5}}
 \qbezier(20,107)(20,100)(20,93)
 \qbezier(3,90)(10,90)(17,90)
 \qbezier(23,90)(30,90)(37,90)
 \qbezier(43,90)(50,90)(57,90)
 \qbezier(63,90)(70,90)(77,90)
 \qbezier(83,90)(90,90)(97,90)
 \qbezier(40,87)(40,80)(40,73)
 \qbezier(80,87)(80,80)(80,73)
 \qbezier(38,68)(30,60)(22,52)
 \qbezier(42,68)(50,60)(58,52)
 \qbezier(3,50)(10,50)(17,50)
 \qbezier(20,47)(20,40)(20,33)
 \qbezier(60,47)(60,40)(60,33)
 \qbezier(62,48)(70,40)(78,32)
 \qbezier(18,28)(10,20)(2,12)
 \qbezier(20,27)(20,20)(20,13)
 \qbezier(60,27)(60,20)(60,13)
 \qbezier(80,27)(80,20)(80,13)
 \qbezier(82,28)(90,20)(98,12)
 \put(35,-8){(a)}
 \end{picture}
 \hskip 0.6cm\begin{picture}(110,120)
 \put(20,110){\circle*{5}}
 \put(0,90){\circle*{5}}
 \put(20,90){\circle{5}}
 \put(40,90){\circle*{5}}
 \put(60,90){\circle{5}}
 \put(80,90){\circle{5}}
 \put(100,90){\circle*{5}}
 \put(40,70){\circle{5}}
 \put(0,50){\circle*{5}}
 \put(20,50){\circle{5}}
 \put(60,50){\circle{5}}
 \put(20,30){\circle{5}}
 \put(60,30){\circle*{5}}
 \put(0,10){\circle*{5}}
 \put(20,10){\circle*{5}}
 \qbezier(20,107)(20,100)(20,93)
 \qbezier(3,90)(10,90)(17,90)
 \qbezier(23,90)(30,90)(37,90)
 \qbezier(43,90)(50,90)(57,90)
 \qbezier(63,90)(70,90)(77,90)
 \qbezier(83,90)(90,90)(97,90)
 \qbezier(40,87)(40,80)(40,73)
 \qbezier(38,68)(30,60)(22,52)
 \qbezier(42,68)(50,60)(58,52)
 \qbezier(3,50)(10,50)(17,50)
 \qbezier(20,47)(20,40)(20,33)
 \qbezier(60,47)(60,40)(60,33)
 \qbezier(18,28)(10,20)(2,12)
 \qbezier(20,27)(20,20)(20,13)
 \put(35,-8){(b)}
 \end{picture}
 \hskip 0.6cm\begin{picture}(110,60)
 \put(20,110){\circle*{5}}
 \put(0,90){\circle*{5}}
 \put(20,90){\circle{5}}
 \put(40,90){\circle*{5}}
 \put(60,90){\circle{5}}
 \put(80,90){\circle{5}}
 \put(100,90){\circle*{5}}
 \put(40,70){\circle{5}}
 \put(0,50){\circle*{5}}
 \put(20,50){\circle{5}}
 \put(60,50){\circle{5}}
 \put(20,30){\circle{5}}
 \put(60,30){\circle{5}}
 \put(0,10){\circle*{5}}
 \put(20,10){\circle*{5}}
 \put(60,10){\circle*{5}}
 \qbezier(20,107)(20,100)(20,93)
 \qbezier(3,90)(10,90)(17,90)
 \qbezier(23,90)(30,90)(37,90)
 \qbezier(43,90)(50,90)(57,90)
 \qbezier(63,90)(70,90)(77,90)
 \qbezier(83,90)(90,90)(97,90)
 \qbezier(40,87)(40,80)(40,73)
 {\linethickness{0.25mm}\qbezier[18](98,88)(80,70)(62,52)}
 \qbezier(38,68)(30,60)(22,52)
 \qbezier(42,68)(50,60)(58,52)
 \qbezier(3,50)(10,50)(17,50)
 \qbezier(20,47)(20,40)(20,33)
 \qbezier(60,47)(60,40)(60,33)
 \qbezier(18,28)(10,20)(2,12)
 \qbezier(20,27)(20,20)(20,13)
 \qbezier(60,27)(60,20)(60,13)
 \put(30,70){$x$}\put(50,28){$y$}\put(50,47){$u$}\put(97,95){$v$}
 \put(35,-8){(c)}
 \end{picture}
 \vskip 0.8cm
 \begin{picture}(110,120)
 \put(20,110){\circle*{5}}
 \put(0,90){\circle*{5}}
 \put(20,90){\circle{5}}
 \put(40,90){\circle*{5}}
 \put(60,90){\circle{5}}
 \put(80,90){\circle{5}}
 \put(100,90){\circle*{5}}
 \put(40,70){\circle{5}}
 \put(0,50){\circle*{5}}
 \put(20,50){\circle{5}}
 \put(60,50){\circle{5}}
 \put(20,30){\circle{5}}
 \put(60,30){\circle{5}}
 \put(0,10){\circle*{5}}
 \put(20,10){\circle*{5}}
 \put(60,10){\circle*{5}}
 \qbezier(20,107)(20,100)(20,93)
 \qbezier(3,90)(10,90)(17,90)
 \qbezier(23,90)(30,90)(37,90)
 \qbezier(43,90)(50,90)(57,90)
 \qbezier(63,90)(70,90)(77,90)
 \qbezier(83,90)(90,90)(97,90)
 \qbezier(40,87)(40,80)(40,73)
 \qbezier(98,88)(80,70)(62,52)
 \qbezier(38,68)(30,60)(22,52)
 \qbezier(3,50)(10,50)(17,50)
 \qbezier(20,47)(20,40)(20,33)
 \qbezier(60,47)(60,40)(60,33)
 \qbezier(18,28)(10,20)(2,12)
 \qbezier(20,27)(20,20)(20,13)
 \qbezier(60,27)(60,20)(60,13)
 \put(35,-8){(d)}
 \end{picture}
 \hskip 0.6cm\begin{picture}(110,120)
 \put(20,110){\circle*{5}}
 \put(0,90){\circle*{5}}
 \put(20,90){\circle{5}}
 \put(35,90){\circle*{5}}\put(45,90){\circle*{5}}\put(40,85){\circle*{5}}
 \put(60,90){\circle{5}}
 \put(80,90){\circle{5}}
 \put(100,90){\circle*{5}}
 \put(40,70){\circle{5}}
 \put(0,50){\circle*{5}}
 \put(20,50){\circle{5}}
 \put(60,50){\circle{5}}
 \put(20,30){\circle{5}}
 \put(60,30){\circle*{5}}
 \put(0,10){\circle*{5}}
 \put(20,10){\circle*{5}}
 \qbezier(20,107)(20,100)(20,93)
 \qbezier(3,90)(10,90)(17,90)
 \qbezier(23,90)(30,90)(33,90)
 \qbezier(47,90)(50,90)(57,90)
 \qbezier(63,90)(70,90)(77,90)
 \qbezier(83,90)(90,90)(97,90)
 \qbezier(40,83)(40,80)(40,73)
 \qbezier(38,68)(30,60)(22,52)
 \qbezier(42,68)(50,60)(58,52)
 \qbezier(3,50)(10,50)(17,50)
 \qbezier(20,47)(20,40)(20,33)
 \qbezier(60,47)(60,40)(60,33)
 \qbezier(18,28)(10,20)(2,12)
 \qbezier(20,27)(20,20)(20,13)
 \put(15,76){$T_1$}\put(65,76){$T_2$}\put(35,50){$T_3$}
 \put(35,-8){(e)}
 \end{picture}
 \hskip 0.6cm\begin{picture}(110,60)
 \put(20,90){\circle{5}}
 \put(60,90){\circle{5}}
 \put(80,90){\circle{5}}
 \put(40,70){\circle{5}}
 \put(20,50){\circle{5}}\put(20,38){\circle{5}}
 \put(60,50){\circle{5}}
 \put(20,22){\circle{5}}
 \put(20,10){\circle{5}}
 \qbezier(63,90)(70,90)(77,90)
 \qbezier(38,68)(30,60)(22,52)
 \qbezier(42,68)(50,60)(58,52)
 \qbezier(20,35)(20,30)(20,25)
 \put(15,76){$S_1$}\put(65,76){$S_2$}\put(36,50){$S_3$}\put(25,27){$S_4$}\put(25,7){$S_5$}
 \put(35,-8){(f)}
 \end{picture}
\vskip 0.5cm\caption{ An example for the decomposition of $C^*\setminus C$. Solid nodes are terminal nodes which correspond to components of $G[C]$. In $(a)$, double circle nodes are pruned, yielding tree $T'$ in $(b)$. Figures in $(c)$ and $(d)$ are used to show how to obtain a tree satisfying assumption \eqref{eq14-11-23-2}. In $(c)$, the dashed edge $uv$ is in $G$ but not in $T'$. Adding edge $uv$ and removing edge $ux$ results in the tree in $(d)$. Full components of $T'$ are shown in $(e)$. Figure $(f)$ shows the decomposed stars.}\label{fig11-1-2}
\end{center}
\end{figure*}

\subsection{The Performance Ratio}

\begin{theorem}\label{lem10-10-1}
The connector set $D_2$ of Algorithm \ref{alg10-6-1} has cost $c(D_2)\leq 2H(\delta-1)opt$.
\end{theorem}
\begin{proof}
Let $S_{1},S_{2},\ldots,S_{g}$ be the sets chosen by Algorithm \ref{alg10-6-1} in the order of their selection into set $D_2$. Let $D_G^{(0)}=D_1$. For $1\leq i\leq g$, let
$$
D_G^{(i)}=D_G^{(0)}\cup S_{1}\cup \ldots\cup S_{i}.
$$
For $i=1,\ldots,g$, denote
$$
r_{i}=-\bigtriangleup_{S_{i}} p(D_G^{(i-1)})\ \mbox{and}\ w_{i}=\frac{c(S_{i})}{-\bigtriangleup_{S_{i}}p(D_G^{(i-1)})}.
$$

Suppose $\{Y_0,Y_{1},\ldots,Y_{h}\}$ is the decomposition of $OPT\setminus D_1$ as in Lemma \ref{lem10-6-3}, where $Y_i$ is a star centered at node $v_i$. For $i=1,\ldots,g+1$ and $j=1,\ldots,h$, denote
\begin{equation}\label{eq14-11-26-1}
a_{i,j}=p'_{D_G^{(i-1)}}(Y_j).
\end{equation}
For $1\leq j\leq h$, define
$$
f(Y_{j})=\sum_{i=1}^{g}(a_{i,j}-a_{i+1,j})w_i,
$$
and let
\begin{equation}\label{eq11-25-1}
f(OPT)=\sum_{j=1}^{h}f(Y_{j}).
\end{equation}

{\em Claim 1.} For any $j=1,\ldots,h$, $f(Y_j)\leq H(a_{1,j})c(Y_j)$.

Since $S_i$ is chosen according to Lemma \ref{le10-30-1}, the special structure of $S_i$ implies that
$$
p_{D_G^{(i-1)}}'(S_i)=-\bigtriangleup_{S_i}p(D_G^{(i-1)}).
$$
Hence,
$$
w_{i}=\frac{c(S_{i})}{p_{D_G^{(i-1)}}'(S_i)}.
$$
Then, by the greedy choice of $S_i$, we have
\begin{equation}\label{eq14-11-24-3}
w_i=\frac{c(S_i)}{p_{D_G^{(i-1)}}'(S_i)}\leq \frac{c(Y_{j})}{p_{D_G^{(i-1)}}'(Y_{j})}=\frac{c(Y_j)}{a_{i,j}}.
\end{equation}
By the definition of $p'$, it can be seen that $a_{i,j}$ is a decreasing function on variable $i$. Hence $a_{i,j}-a_{i+1,j}\geq 0$. Combining this with \eqref{eq14-11-24-3},
\begin{align*}
f(Y_{j})\
& \leq \ \sum_{i=1}^g (a_{i,j}-a_{i+1,j})\frac{c(Y_{j})}{a_{i,j}}\\
&\leq\  c(Y_j) \sum_{i=1}^g \big(H(a_{i,j})-H(a_{i+1,j})\big)\\
&=\ c(Y_{j}) \big(H(a_{1,j})-H(a_{g+1,j})\big),
\end{align*}
where the second inequality uses the fact that for any integers $a\geq b$,
$$
\frac{a-b}{a}=\sum_{l=b+1}^a\frac{1}{a}\leq\sum_{l=b+1}^a\frac{1}{l}=H(a)-H(b).
$$
Observe that $a_{g+1,j}=0$ since $D_G^{(g)}$ is connected, the claim follows.

{\em Claim 2.} $c(D_2)\leq f(OPT)$.

Notice that $c(D_2)$ and $f(Y_j)$ can be rewritten as
\begin{equation}\label{eq-11-17-1}
c(D_2)=\sum_{i=1}^gr_iw_i=\sum_{i=1}^g\left(\sum_{l=i}^gr_l-\sum_{l=i+1}^gr_l\right)w_i=
\left(\sum_{l=1}^gr_l\right)w_1+\sum_{i=2}^g\left(\sum_{l=i}^gr_l\right)(w_i-w_{i-1})
\end{equation}
and
\begin{equation}\label{eq-11-17-2}
f(Y_j)=a_{1,j}w_1+\sum_{i=2}^ga_{i,j}(w_i-w_{i-1}).
\end{equation}
By the monotonicity of $p'$, we have $p'_{D_G^{(i-1)}}(S_i)\leq p'_{D_G^{(i-2)}}(S_i)$. Combining this with the greedy choice of $S_{i-1}$, we have
$$
w_i=\frac{c(S_i)}{p'_{D_G^{(i-1)}}(S_i)}\geq \frac{c(S_i)}{p'_{D_G^{(i-2)}}(S_i)}\geq \frac{c(S_{i-1})}{p'_{D_G^{(i-2)}}(S_{i-1})}=w_{i-1}.
$$
In other words, $w_i-w_{i-1}\geq 0$ for $i=1,\ldots,g$. Then, by \eqref{eq11-25-1}, \eqref{eq-11-17-1}, and \eqref{eq-11-17-2}, it can be seen that to prove Claim 2, it suffices to prove that for $i=1,\ldots,g$,
\begin{equation}\label{eq14-11-24-6}
\sum_{j=1}^ha_{i,j}\geq \sum_{l=i}^gr_l.
\end{equation}
The right hand side is
$$
\sum_{l=i}^gr_l=\sum_{l=i}^g-\bigtriangleup_{S_l}p(D_G^{(l-1)})=\sum_{l=i}^g\big(p(D_G^{(l-1)})-p(D_G^{(l)})\big)=p(D_G^{(i-1)})-p(D_G^{(g)})=p(D_G^{(i-1)})-1.
$$
So, proving \eqref{eq14-11-24-6} is equivalent to proving
\begin{equation}\label{eq14-11-24-7}
\sum_{j=1}^hp'_{D^{(i-1)}_G}(Y_j)+1\geq p(D_G^{(i-1)}).
\end{equation}
This inequality can be illustrated by Fig.\ref{figzz}. In this figure, $OPT$ is decomposed into four stars. A comprehension for the value $p'_{D}(Y_1)=3$ is that in Fig.\ref{figzz}(c), the double circled components are merged into the triangled component. Call the new component as $\widetilde C$. Then, the comprehension of $p'_D(Y_2)=3$ is that in Fig.\ref{figzz}(d), double circled components are merged into the triangled component. Notice that this triangled component is contained in $\widetilde C$, and thus we can regard it as $\widetilde C$ in our comprehension. Continue this procedure sequentially in such a way that $Y_1\cup\ldots\cup Y_l$ is connected for $l=1,\ldots,4$. Finally, all components of $G[D]$ are merged into one component, the reduction on the number of components is $p(D)-1$. Notice that the inequality might be strict because some components are counted more than once in the summation part. For example, the component labeled by $u_4$ is repetitively counted.

\vskip 0.2cm \begin{figure*}[!htbp]
\begin{center}
\begin{picture}(100,140)
\put(0.0,10.0){\circle*{5}}
\put(30.0,10.0){\circle*{5}}
\put(60.0,10.0){\circle*{5}}
\put(90.0,10.0){\circle*{5}}
\put(30.0,40.0){\circle{5}}
\put(90.0,40.0){\circle{5}}
\put(0.0,70.0){\circle*{5}}
\put(30.0,70.0){\circle{5}}
\put(90.0,70.0){\circle{5}}
\put(0.0,100.0){\circle*{5}}
\put(60.0,100.0){\circle{5}}
\put(30.0,130.0){\circle*{5}}
\put(60.0,130.0){\circle*{5}}
\put(90.0,130.0){\circle*{5}}
\qbezier(2,12)(15.0,25.0)(28,38)
\qbezier(30.0,12)(30.0,25.0)(30.0,37)
\qbezier(58,12)(45.0,25.0)(32,38)
\qbezier(90.0,13)(90.0,25.0)(90.0,37)
\qbezier(30.0,43)(30.0,55.0)(30.0,67)
\qbezier(90.0,43)(90.0,55.0)(90.0,67)
\qbezier(3,70.0)(15.0,70.0)(27,70.0)
\qbezier(28,72)(15.0,85.0)(2,98)
\qbezier(32,72)(45.0,85.0)(58,98)
\qbezier(88,72)(75.0,85.0)(62,98)
\qbezier(58,102)(45.0,115.0)(32,128)
\qbezier(60.0,103)(60.0,115.0)(60.0,127)
\qbezier(62,102)(75.0,115.0)(88,128)
{\linethickness{0.3mm}\qbezier[13](30.0,73)(30.0,100.0)(30.0,127)
\qbezier[13](88,72)(75.0,100.0)(62,128)
\qbezier[13](90.0,73)(90.0,100.0)(90.0,127) }
\put(58,90){$v_1$}\put(35,68){$v_2$}\put(35,38){$v_3$}\put(78,65){$v_4$}\put(78,35){$v_5$}
\put(26,135){$u_1$}\put(56,135){$u_2$}\put(86,135){$u_3$}\put(-15,98){$u_4$}\put(-15,68){$u_5$}
\put(-15,8){$u_6$}\put(15,5){$u_7$}\put(45,8){$u_8$}\put(75,8){$u_9$}
\put(35,-8){(a)}
\end{picture}\hskip 0cm\begin{picture}(100,140)
\put(30.0,30.0){\circle{5}}\put(30.0,10.0){\circle{5}}
\put(90.0,30.0){\circle{5}}
\put(30.0,70.0){\circle{5}}\put(30.0,60.0){\circle{5}}
\put(90.0,70.0){\circle{5}}\put(90.0,60.0){\circle{5}}
\put(60.0,100.0){\circle{5}}
\qbezier(30.0,33)(30.0,45.0)(30.0,57)
\qbezier(90.0,33)(90.0,45.0)(90.0,57)
\qbezier(32,72)(45.0,85.0)(58,98)
\qbezier(88,72)(75.0,85.0)(62,98)
\put(55,105){$S_1$}\put(35,40){$S_2$}\put(35,8){$S_3$}\put(75,40){$S_4$}
\put(55,-8){(b)}
\end{picture}
\hskip 0.8cm\begin{picture}(100,140)
\put(0.0,40.0){\circle*{5}}
\put(30.0,40.0){\circle{5}}
\put(90.0,40){\circle{5}}
\put(0.0,70){\circle*{5}}\put(0.0,70){\circle{8}}
\put(60.0,70){\circle{5}}
\put(30.0,100){\circle*{5}}\put(30.0,100){\circle{8}}
\put(60.0,100){\circle*{5}}\put(60.0,100){\circle{8}}
\put(90.0,100){\circle*{5}}{\large\put(84.5,97){$\bigtriangleup$}}
\qbezier(3,40)(15.0,40)(27,40)
\qbezier(28,42)(15.0,55.0)(2,68)
\qbezier(32,42)(45.0,55.0)(58,68)
\qbezier(88,42)(75.0,55)(62,68)
\qbezier(58,72)(45.0,85)(32,98)
\qbezier(60.0,73)(60.0,85)(60.0,97)
\qbezier(62,72)(75.0,85.0)(88,98)
{\linethickness{0.3mm}\qbezier[13](30.0,43)(30.0,70)(30.0,97)
\qbezier[13](88,42)(75.0,70)(62,98)
\qbezier[13](90.0,43)(90.0,70)(90.0,97) }
\put(55,-8){(c)}
\end{picture}

\vskip 0.9cm\begin{picture}(100,100)
\put(30.0,10.0){\circle*{5}}
\put(60.0,10.0){\circle*{5}}
\put(0.0,10.0){\circle*{5}}\put(0.0,10.0){\circle{8}}
\put(30.0,40.0){\circle{5}}
\put(0.0,70.0){\circle*{5}}\put(0.0,70.0){\circle{8}}
\put(30.0,70.0){\circle{5}}
\put(0.0,100){\circle*{5}}{\large\put(-5.5,97){$\bigtriangleup$}}
\qbezier(2,12)(15.0,25.0)(28,38)
\qbezier(30.0,12)(30.0,25.0)(30.0,37)
\qbezier(58,12)(45.0,25.0)(32,38)
\qbezier(30.0,43)(30.0,55.0)(30.0,67)
\qbezier(3,70.0)(15.0,70.0)(27,70.0)
\qbezier(28,72)(15.0,85.0)(2,98)
\put(18,-8){(d)}
\end{picture}
\hskip 0.5cm\begin{picture}(70,100)
\put(30.0,40){\circle*{5}}\put(30,40){\circle{8}}
\put(60.0,40){\circle*{5}}\put(60,40){\circle{8}}
\put(0.0,40){\circle*{5}}{\large\put(-5.5,37){$\bigtriangleup$}}
\put(30.0,70){\circle{5}}
\qbezier(2,42)(15.0,55)(28,68)
\qbezier(30.0,42)(30.0,55)(30.0,67)
\qbezier(58,42)(45.0,55)(32,68)
\put(18,-8){(e)}
\end{picture}
\hskip 0cm\begin{picture}(100,100)
\put(90.0,10.0){\circle*{5}}\put(90.0,10.0){\circle{8}}
\put(90.0,40.0){\circle{5}}
\put(90.0,70.0){\circle{5}}
\put(60.0,100){\circle*{5}}{\large\put(54.8,97){$\bigtriangleup$}}
\put(90.0,100){\circle*{5}}{\large\put(84.6,97){$\bigtriangleup$}}
\qbezier(90.0,13)(90.0,25.0)(90.0,37)
\qbezier(90.0,43)(90.0,55.0)(90.0,67)
{\linethickness{0.3mm}\qbezier[9](88,72)(75,85)(62,98)\qbezier[7](90,73)(90,85)(90,97)}
\put(85,-8){(f)}
\end{picture}\vskip 0.5cm\caption{An illustration for inequality \eqref{eq14-11-24-7}. Solid circles indicate components.}\label{figzz}
\end{center}
\end{figure*}

Claim 2 is proved.

By Lemma \ref{lem10-6-3} $(\romannumeral4)$, we have
\begin{equation}\label{eq14-11-27-8}
\sum_{i=1}^{h}c(Y_{i})\leq 2opt.
\end{equation}
Then by Claim 1, Claim 2, and the observation that $a_{1,j}\leq \delta-1$, we have
$$
c(D_2)\leq \sum_{j=1}^{h}c(Y_j)H(\delta-1)\leq 2H(\delta-1)opt.
$$
The theorem is proved.
\end{proof}

Combining Theorem \ref{thm14-11-25-1} and Theorem \ref{lem10-10-1}, we have the following result.

\begin{theorem}\label{th10-18-2}
Algorithm \ref{alg10-6-1} is a polynomial-time $\big(H(\delta+m)+2H(\delta-1)\big)$-approximation for the $m$-MWCDS problem.
\end{theorem}

\section{Implementation on Unit Disk Graphs}\label{secUDG}

Notice that the maximum degree $\delta$ in the performance ratio of the second part of the algorithm comes from $a_{1,j}\leq \delta-1$. So, to improve the approximation factor when the graph under consideration is a unit disk graph, we improve the upper bound for $a_{1,j}$ first. We use notation $T_1,\ldots,T_l$ in the proof of Lemma \ref{lem10-6-3}. Recall that each $T_i$ has $V(T_i)\subseteq C^*\setminus C$ and  is decomposed into some stars, and the final decomposition of $C^*\setminus C$ is the union of these stars and a set of pruned nodes. We shall use $\|\cdot\|$ to denote Euclidean length.

\begin{lemma}\label{lem14-11-27-7}
In a unit disk graph, there exists a set of subtrees $T_1,\ldots,T_l$ in the proof of Lemma \ref{lem10-6-3} such that any node $v\in V(T_i)$ has $|NC_C(v)|+deg_{T_i}(v)\leq 5$.
\end{lemma}
\begin{proof}
Construct a spanning tree of $G[C\cup C^*]$ as follows. First, replace each component of $G[C]$ by a spanning tree of that component, which is called a {\em tree component}. Then, find a minimum length tree $T$ which spans all nodes of $C^*\setminus C$ and all tree components, where ``minimum length'' is with respect to Euclidean distance. For convenience of statement, we shall call a tree which spans all nodes of $C^*\setminus C$ and all tree components as a {\em valid tree}. Each component of $G[C]$ is called a component node of such a tree and is dealt with as a whole in the following. Similarly to the proof of Lemma \ref{lem10-6-3}, by pruning leafs in $C^*\setminus C$ and by splitting off at component nodes, we obtain a set of full components $T_1',\ldots,T_l'$. Let $T_i$ be the subtree of $T_i'$ with component nodes removed. We choose tree $T$ such that
\begin{equation}\label{eq14-11-27-3}
\sum_{i=1}^l\sum_{u\in V(T_i)}deg_{T_i}(u)\ \mbox{is as small as possible.}
\end{equation}

Suppose there is a node $v\in V(T_i)$ with $|NC_C(v)|+deg_{T_i}(v)=t>6$, assume $NC_C(v)\cup N_{T_i}(v)=\{x_1,\ldots,x_t\}$, where $x_j$ is a node in $C^*\setminus C$ or a node in a component neighbor of $v$ (if $v$ is adjacent with more than one node of a component neighbor, only one node of that component neighbor is chosen to appear in $\{x_1,\ldots,x_t\}$), and $x_1,\ldots,x_t$ are in a clockwise order around node $v$. Since $t>6$, there is an index $j$ with $\angle x_jvx_{j+1}<\pi/3$ ($x_{t+1}$ is viewed as $x_1$). Then $\|x_jx_{j+1}\|<\max\{\|vx_j\|,\|vx_{j+1}\|\}$, say $\|x_jx_{j+1}\|<\|vx_j\|$. Replacing edge $vx_j$ by $x_jx_{j+1}$, we obtain another valid tree whose Euclidean length is shorter than $T$, a contradiction. So,
\begin{equation}\label{eq14-11-27-6}
\mbox{every node $v\in V(T_i)$ has $|NC_C(v)|+deg_{T_i}(v)\leq 6$.}
\end{equation}
A node $u$ with $|NC_C(v)|+deg_{T_i}(v)=6$ is called {\em bad}.

Similar argument shows that for any bad node $v\in V(T_i)$, $\angle x_jvx_{j+1}=\pi/3$ for $j=1,\ldots,6$ and $\|vx_1\|=\cdots=\|vx_6\|$. In other words, $x_1,\ldots,x_6$ locate at the corners of a regular hexagon with center $v$. First, suppose node $v$ has a component neighbor, say $x_1$ is in a component neighbor of $v$. If $x_2\in C$, then $x_2$ must be in a same component of $G[C]$ as $x_1$, because $\|x_1x_2\|=\|vx_1\|\leq 1$, contradicting our convention that one component has at most one node appearing in $\{x_1,\ldots,x_6\}$. So, $x_2\in C^*\setminus C$. Then, $\widetilde T=T-\{vx_2\}+\{x_1x_2\}$ is a valid tree with the same length as $T$. Notice that $\sum_{i=1}^l\sum_{u\in V(T_i)}deg_{T_i}(u)$ is decreased by two (edge $x_1x_2$ does not contribute to the degree sum since one of its end is in a component neighbor and thus does not belong to $T_i$), contradicting the choice of $T$ (see \eqref{eq14-11-27-3}). So, for $j=1,\ldots,6$, $x_j\in C^*\setminus C$. Since $\widetilde T=T-\{vx_{j-1},vx_{j+1}\}+\{x_jx_{j-1},x_jx_{j+1}\}$ is also a valid tree whose length is the same as $T$, we have $|NC_C(x_j)|+deg_{\widetilde T_i}(x_j)\leq 6$. By noticing that $deg_{\widetilde T_i}(x_j)=deg_{T_i}(x_j)+2$ (since both $x_{j-1},x_{j+1}\in C^*\setminus C$), we have
\begin{equation}\label{eq14-11-27-5}
|NC_C(x_j)|+deg_{T_i}(x_j)\leq 4.
\end{equation}
This inequality holds for any $j=1,\ldots,6$. Notice that $\widehat T=T-\{vx_1\}+\{x_1x_2\}$ is a valid tree with the same length as $T$ and $\sum_{i=1}^l\sum_{u\in V(\widehat T_i)}deg_{\widehat T_i}(u)=\sum_{i=1}^l\sum_{u\in V(T_i)}deg_{T_i}(u)$. By property \eqref{eq14-11-27-6} and \eqref{eq14-11-27-5}, we have
$$
|NC_C(u)|+deg_{\widehat T_i}(u)=\left\{\begin{array}{ll}|NC_C(u)|+deg_{T_i}(u)-1\leq 5, & u=v,\\|NC_C(u)|+deg_{T_i}(u)+1\leq 5, & u=x_1\ \mbox{or}\ x_2,\\ |NC_C(u)|+deg_{T_i}(u)\leq 6, & u\neq v,x_1,x_2.\end{array}\right.
$$
So, the number of bad nodes in $\widehat T$ is strictly reduced. By recursively executing such an operation, we have a tree satisfying the requirement of this lemma.

Recall that condition \eqref{eq14-11-23-2} plays an important role in the decomposition. This does no pose any difficulty here, because by the modification method in the proof of Lemma \ref{lem10-6-3}, if $u\in C^*\setminus C$ is not adjacent with any component neighbor in $T'$, then we may just add an edge between $u$ and a component neighbor, and remove an edge between $u$ and another node in $C^*\setminus C$. Such an operation does not increase the value of $|NC_C(u)|+deg_{T_i}(u)$.
\end{proof}

\begin{theorem}
When applied to unit disk graphs, the node set $D_2$ produced by Algorithm \ref{alg10-6-1} has cost $c(D_2)\leq 3.67opt$.
\end{theorem}
\begin{proof}
Let $T_1,\ldots,T_l$ be the subtrees in Lemma \ref{lem14-11-27-7}. Choose node $v_i=\arg\max\{c(v)\colon v\in V(T_i)\}$ to be the root of $T_i$. Decompose $C^*\setminus C$ as in the proof of Lemma \ref{lem10-6-3}. Let $\{Y_v^{(i)}\}$ be the set of stars coming from the decomposition of $T_i$. To avoid ambiguity, we use $a_{1,Y_v^{(i)}}$ to denote $p'_{D_1}(Y_v^{(i)})$ (which is $a_{1,j}$ in the proof of Theorem \ref{lem10-10-1}). By Lemma \ref{lem14-11-27-7}, if $v=v_i$, then $a_{1,Y_v^{(i)}}\leq |NC_{D_1}(v)|-1+ deg_{T_i}(v)\leq 4$; if $v\neq v_i$, then  $a_{1,Y_v^{(i)}}\leq |NC_{D_1}(v)|-1+deg_{T_i}(v)-1\leq 3$ (this is because the parent of $v$ is not in $Y_v$ if $v\neq v_i$).

Notice that $v_i$ belongs to exactly one star in the decomposition of $C^*\setminus C$. Hence inequality \eqref{eq14-11-27-8} can be improved to
\begin{equation}\label{eq14-11-27-9}
\sum_{i=1}^l\sum_{Y_v^{(i)}}c(Y_v^{(i)})+\sum_{i=1}^lc(v_i)\leq 2opt.
\end{equation}
Combining Lemma \ref{lem14-11-27-7} with Claim 1 and Claim 2 of Theorem \ref{lem10-10-1},
\begin{equation}\label{eq14-11-27-10}
c(D_2)\leq \sum_{i=1}^l\sum_{Y_v^{(i)}}c(Y_v^{(i)})H(a_{1,Y_v^{(i)}})\leq \sum_{i=1}^l\left(H(4)c(Y_{v_i}^{(i)})+H(3)\sum_{Y_v^{(i)},v\neq v_i}c(Y_v^{(i)})\right).
\end{equation}
Since $D_1$ is an $m$-fold dominating set, every $v_i$ has at least one component neighbor. Then by Lemma \ref{lem14-11-27-7}, $deg_{T_i}(v_i)\leq 4$, and thus $Y_{v_i}^{(i)}$ has at most five nodes. Since $v_i$ has the maximum cost in $T_i$, we have $c(Y_{v_i}^{(i)})\leq 5c(v_i)$. So,
$$
H(4)c(Y_{v_i}^{(i)})=H(3)c(Y_{v_i}^{(i)})+\frac{c(Y^{(i)}_{v_i})}{4}\leq H(3)c(Y_{v_i}^{(i)})+5c(v_i)/4<H(3)\big(c(Y_{v_i}^{(i)})+c(v_i)\big).
$$
Combining this inequality with \eqref{eq14-11-27-9} and \eqref{eq14-11-27-10},
$$
c(D_2)\leq H(3)\left(\sum_{i=1}^l\sum_{Y_v^{(i)}}c(Y_v^{(i)})+\sum_{i=1}^lc(v_i)\right)\leq 2H(3)opt<3.67opt.
$$
The theorem is proved.
\end{proof}

\section{Conclusion}\label{sec.7}

In this paper, we presented a $(H(\delta+m)+2H(\delta-1))$-approximation algorithm for the minimum weight $(1,m)$-CDS problem, where $\delta$ is the maximum degree of the graph. Compared with the $1.35\ln n$-approximation algorithm for the minimum $(1,1)$-CDS problem \cite{Guha1}, our constant is larger. However, since in many cases, the maximum degree is much smaller than the number of nodes, our result is an improvement on the performance ratio in some sense. In particular, the replacement of $n$ by $\delta$ in the performance ratio makes it possible to obtain a 3.67-approximation for the connecting part when the topology of the network is a unit disk graph. In fact, Zou {\it et al.} obtained a $2.5\rho$-approximation for the connecting part in a unit disk graph, where $\rho$ is the performance ratio for the minimum Steiner tree problem. If the best $\rho=1.39$ is used, their algorithm has performance ratio $3.475$. Notice that the $1.39$-approximation algorithm for the minimum Steiner tree problem uses a combination of iterated rounding and random rounding. Our algorithm has the advantage of purely combinatorial and deterministic. Furthermore, we expect our method to have a theoretical value which can be used to deal with other problems.

\section*{Acknowledgements}
This research is supported by NSFC (61222201,11531011), SRFDP
(20126501110001), and Xingjiang Talent Youth Project (2013711011). It is accomplished when the second author is visiting National Chiao Tung University, Taiwan, sponsored by ``Aiming for the Top University Program'' of the National Chiao Tung University and Ministry of Education, Taiwan.

redpajama_set_name: RedPajamaArXiv


Bank of America Corp Chief Executive Kenneth Lewis, whose bank sold $13.47 billion of common stock this month, on Wednesday said the worst of the economic downturn has likely passed and that conditions will not worsen as much as feared.
"We are on the cusp of what will turn out to be a slow but sustainable economic recovery," Lewis said at a conference in London. "There will continue to be a lot of pain ... but I think the worst is most likely behind us." He projected modest U.S. and European economic growth in the second half of 2009.
Lewis, whose bank bought Merrill Lynch & Co on January 1, also said corporate and investment banking pay practices must be "reformed," with pay being tied to performance and banks being able to "claw back" pay from people who took on too much risk.


text:
Q: Object Oriented Bayesian Spam Filtering? I was wondering if there is any good and clean object-oriented programming (OOP) implementation of Bayesian filtering for spam and text classification? This is just for learning purposes.

A: Maybe https://ci-bayes.dev.java.net/ or http://www.cs.cmu.edu/~javabayes/Home/node2.html?
I never played with it either.

A: Check out Chapter 6 of Programming Collective Intelligence

A: Here is an implementation of Bayesian filtering in C#: A Naive Bayesian Spam Filter for C# (hosted on CodeProject).

A: nBayes - another C# implementation hosted on CodePlex

A: I definitely recommend Weka which is an Open Source Data Mining Software written in Java:

Weka is a collection of machine learning algorithms for data mining tasks. The algorithms can either be applied directly to a dataset or called from your own Java code. Weka contains tools for data pre-processing, classification, regression, clustering, association rules, and visualization. It is also well-suited for developing new machine learning schemes.

As mentioned above, it ships with a bunch of different classifiers like SVM, Winnow, C4.5, Naive Bayes (of course) and many more (see the API doc).
Note that a lot of classifiers are known to have much better perfomance than Naive Bayes in the field of spam detection or text classification.
Furthermore Weka brings you a very powerful GUI…

A: In French, but you should be able to find the download link :)
PHP Naive Bayesian Filter

redpajama_set_name: RedPajamaStackExchange


Members of the El Luengo Community Council have been working toward creating a learning environment conducive for educational strengthening for their youth. This dream is quickly materialising through the recent development at the community centre, after receiving a grant from the Digicel Foundation's Extraordinary Projects Impacting Communities (EPIC) which funds community initiatives.
The Community Council partnered with the Digicel Foundation to find ways to use education as a mechanism for sustainable development. The funding was used to purchase furniture and equipment such as chairs, desks, white boards, books as well as computers to outfit a lab.
Located in Maracas St. Joseph, the El Luengo residents volunteered their time building the computer lab, constructing a bookcase, painting, setting up the computers and installing additional security features at the community centre.
Mary Reyes, President of the Community Council was elated to have received the funding, and attributed the success of the programme to the commitment and drive of the villagers.
Computer literacy classes will be conducted at the community centre and the group plans to use a blended approach to learning, with the hopes of reducing school drop outs and encourage more parental involvement. The space will be utilized in other income-generating initiatives, to off-set the cost of running the community centre.


paoandmanu . Asexylatex. GabriellaStark. MiaSummerss.
StevenBradleyMILFG1rlXAquiles01Emiko .thisgirlwithmaskLadyLullabyAlibirMiaSummerss .CatherineHilDalilaHoffmanShyVellGenyRock .PaeoniaZahiraSelketAndreasStoneRosien .FISTINGHOLESXXXIannJamesBarrySlick20actionsexfuxx .LinLaceONATAYLORSHARAIDyourLOVEspell69 .MaggiHotPenisKonigMarianaOzpinaNATIECANE .StevenBradleythisgirlwithmaskOlesyaXAsexylatex .LatinLoversCAOrdinaryWebManversatileANDREWLilianaA .LinLaceFISTINGHOLESXXXa0MeltWithMeLissaKain .RickiWhiteOlesyaXFitnessBernycindycindy .
SHARAIDGeraldin21MatureJuliaIzabelaStarX .MidnightDyamondRoxyAndDrilleralin9421pilot .KonyHottestSexyNat3ZahiraSelketBelleRusseau .PaeoniaAquiles01AsexylatexGeraldin21 .AntonellaWBelleRusseauXseDuctiveGoDDesPRINCESSisVIRGIN .actionsexfuxxAlibirRosienLucasWhitmore .MaggiHotGabriellaStarkSatiSeXioNAntonellaW .a0MeltWithMeRoxyAndDrillerAngelAnelliseZahiraSelket .versatileANDREWJoeArdyMILFG1rlXOlesyaX .MILFG1rlXNATIECANECrazyStasyaSensualKarissa .NATIECANESatiSeXioNmicheellxSensualKarissa .


What is better Bugzilla or Appenate? The best IT Management Software is a solution that can handle your company's specific needs. You can identify which solution works really with your company if you examine different products before you decide which one is the best.
As an example, Bugzilla and Appenate are scored at 7.9 and 8.0, respectively, for general quality and performance. Similarly, Bugzilla and Appenate have a user satisfaction rating of 97% and 100%, respectively, which reveals the general response they get from customers. Moreover, talk to a regular customer of the software and solicit their feedback regarding the application in question.
As of now, the most popular solutions in our IT Management Software category are: Cloudflare, Norton Security, Avira Antivirus Server.
Appenate helps you create powerful and beautiful mobile applications, including intuitive data collection tools.
Every time you compare various IT Management Software services you shouldn't simply explore their list of features and available pricing packages. Keep in mind the software should be meeting your standards and company so the more flexible their offer the better. Learn which platforms are supported by Bugzilla and Appenate and make sure you will get mobile support for whichever devices you work on in your company. It may also be a good idea to learn which languages and countries are supported, as this might be a key element for many companies.


As rugged and tough as they come, Cat® lift trucks are renowned for non-stop performance. Just as you can rely on our trucks, you can also rely on our comprehensive warranty protection.
Cat® Lift Plus offers the most comprehensive range of product support and customer service programs in the lift truck industry. This flexible long-term protection covers our lift truck's entire powertrain and any contingent damage. Coverage extends to every major component related to the powertrain – transmission, driveline, and drive axle. On the electric lift trucks, covers include control panel, drive systems elements and motor. Remember, when the going get tough our cover gets tougher.
Cat® Lift Trucks offers a range of services that support our potential and current customers. Click here to request that your dealer contact you for a customized and personal presentation.


text:
musicareview.com
IQ Certificate
Hot Songs of January 2020
Godzilla (feat. Juice WRLD)
You should be sad
B.I.T.C.H.
Life Is Good (feat. Drake)
hot girl bummer
blackbear
Sonya Belousova & Giona Ostinelli
This Land
Gary Clark Jr.
Higher (feat. Nipsey Hussle & John Legend)
Letter To Nipsey (feat. Roddy Ricch)
Those Kinda Nights (feat. Ed Sheeran)
It's So Hard to Say Goodbye to Yesterday
Music reviews of the latest albums and tracks. Reviews from various critics and music publications on new releases in a variety of genres...
Material Colors
Encyclopedia and Thesaurus
Online Typing Test
musicareview.com © 2016 - 2020. All Rights Reserved. Made in Estonia, with love and HTML5.

redpajama_set_name: RedPajamaCommonCrawl


I want to thank you so much for the wonderful job you did on giving me all of the stills from the MTA bus videos on the People v. Martinez case.
The Martinez case was a case where my client (a gang member) got on a bus and was confronted by two rival gang members. My client pulled a handgun and shot one of the other persons multiple times. My client was charged with attempted willful, deliberate and premeditated murder with a gang enhancement. Our defense was sefl-defense. Thanks to the terrific frame-by-frame breakdown of the videos which you provided to me, I was able to show the jury that, indeed, the other two persons were the aggressors and that my client shot in self-defense. The jury acquitted my client.
I will highly recommend your services to any other criminal defense attorneys who might need the type of service you provide. Again, thank you for your excellent work.


The ATS US-2000 TRW-DMS-MP measures the stack's width, height, length and lateral misalignment directly on the transport conveyor belt and positions the printer accordingly. The individual print data is retrieved from the central server based on the stack number. The allocation of the laundry to different customers is facilitated by the information on the laundry stacks, thus reducing personnel costs.


text:
UK MARKET
US MARKET
Smartsheet Partner
Sevan Multi-Site Solutions Ranked on Inc. Magazine's List of the Midwest's 2021 Fastest-Growing Private Companies
Leave a Comment / Press Releases / By Charlotte Youell
DOWNERS GROVE, Ill. (March 17, 2021)—Inc. Magazine named Sevan Multi-Site Solutions, Inc. (Sevan)—a global leader in innovative design, program management, construction services and data analytics—on its 2021 Inc. 5000 Regionals: Midwest list of fastest growing private companies.
"Sevan is honored to be ranked on this list alongside many other strong, successful companies," Sevan's President and CEO Jim Evans said. "We are committed to developing innovative solutions and serving as a trusted partner to companies across the world. We look forward to continuing to provide excellence for our people, clients and partners as we grow our Midwest and global footprint."
Inc.'s 2021 Regionals: Midwest highlights the fastest-growing private companies in Illinois, Indiana, Iowa, Kansas, Michigan, Minnesota, Missouri, Nebraska, North Dakota, Ohio, South Dakota and Wisconsin. This list recognizes innovative achievements of regional companies in generating sustainable growth and jobs, and is an esteemed honor for growing private businesses.
"This list proves the power of companies in Midwest states no matter the industry," Inc. Editor-in-Chief Scott Omelianuk said. "The impressive revenues and growth rates prove the insight and diligence of CEOs and that these businesses are here to stay."
Companies on the Midwest list grew, on average, 199 percent between 2017 and 2019 — even when the broader United States economy grew just 10 percent. In 2019 alone, the businesses listed employed more than 43,000 people and added more than $11 billion to the Midwest economy. Those based in the Chicago, Detroit and Cincinnati areas brought in the highest revenue overall.
Congratulations to all named on Inc. Magazine's list of the Midwest's fastest-growing private companies!
In 2020, Sevan was recognized as an Employee-Rated Great Place to Work® for the 7th consecutive year and ranked No. 124 on the Financial Times FT 1000 list of America's Fastest-Growing Companies. Also in 2020, Sevan ranked No. 16 on Engineering News-Record (ENR)'s Top 50 Program Management Firms and No. 34 on ENR's Top 100 Construction Management-for-Fee Firms. Visit our website to learn more about Sevan, our award rankings and acquisitions.
Sevan is a construction and project management firm that leverages innovative technology to deliver excellence to clients. Sevan is headquartered near Chicago in Downers Grove, Illinois with 400+ employees and has an international office in London.
About Sevan
The vision of Sevan Multi-Site Solutions is to be the best in the world at delivering innovative design, program management, construction services and data analytics to organizations with multiple sites. Sevan has a passion for sustaining people, the environment and its clients' businesses. Sevan helps iconic global brands, including 7-Eleven, AAFES, Albertsons, Amtrak, BP, Chipotle, DaVita, HCA Healthcare, Hallmark, HEB, Jiffy Lube, Kroger, Marathon, McDonald's, Office Depot, Starbucks, Sunoco, Walgreens Boots Alliance, Walmart and Zaxby's. Sevan rolls out multi-site initiatives efficiently, predictably and transparently. Applying breakthrough technology solutions, Sevan optimizes construction of new builds, rebuilds, remodels and renovations. Sevan has licensed architects in 49 states as well as D.C., Canadian provinces, Guam and the Northern Mariana Islands. Sevan has professional engineers on staff and general contractor licenses in more than 25 states. Since Sevan's inception in 2011, the team has refreshed more than 21,000 retail stores and 14,000 restaurants and completed more than 28,000 surveys. Sevan Elevate, a program that reinforces and continuously improves safety and sustainability across the company, is designed to impactfully deliver excellence to Sevan's people and clients. To read more about Sevan, visit www.sevansolutions.com.
For more information, please contact Hafsa Mahmood by calling +1 312.285.0590 or via e-mail at hafsa.mahmood@sevansolutions.com.
3025 Highland Parkway
UK + EUROPE
The Cart Shed, Amberley Court,
Amberley Lane
Milford, Surrey GU8 5EB, UK
Copyright © 2023 Sevan Solutions. All rights reserved.


Hello, Beauties! What do you do when your joy gets dull? JOY: the secret sauce to losing weight and keeping it off. What happens when it becomes less joyful? Can joy lose its potency? If you feel panic swelling in your chest, take a deep breath. I know how hard you worked to identify JOY and then embrace it. Nothing has gone wrong. It is the way of humans for things we use all the time to lose their punch.
To prove that point to your brain, think about other things that you love! My new iPhone X was magnificent in the beginning. But now nine months later, it's just another phone. That love relationship with the most perfect man was intoxicating in the beginning. Now five years later, you still know how wonderful he is but the intoxication is harder to find.
It is the way of humans to find new inspiration and then over time find that it is less and less alluring. Did the joy get less potent or does familiarity breed contempt?
You have probably also experienced this phenomenon with food. In an attempt to feed yourself better, you embrace a new food. My examples are turkey jerky and kale chips. I even bought a dehydrater to make them. I genuinely love them both but I can't tell you the last time I had either one. Somewhere along the way, they fell off of the things I prep for myself every week.
Here's the danger. When your joy sources get dull they leave the door open for old crappier habits. Chips and fast food suddenly remind you mentally of how much you love them.
It's not about hunger, it's about JOY. And for so many of us, those old foods that keep us fat have a deep association with comfort and joy.
Be so plugged into yourself that an internal alarm goes off when your joy battery is so low you are susceptible to crap food and disconnecting from yourself.
For me, it feels like lethargy – dull – an absence of any sharp positive emotion.
Second danger? Thinking that feeling serves you.
You aren't in danger. Life is pretty good. But, you feel flat. It is a subtle way of hiding from yourself. Don't rock the boat. The negative that you've gotten so used to feeling is gone, but vibrancy and thriving are missing.
Are you willing to trade GOOD for GREAT?
Your body is patiently waiting for you to claim your greatness, to know from the inside out that JOY is your birthright. The only thing you need in order to feel it, claim it as your own, is to be a breathing human being.
so that we can start defining your new JOY menu.
Who will you be by Christmas?
I can't wait to see what you create for yourself!
I love my you my Voluptuous Beauties!


Fix Site design horribleness with the stylish plugin | blarg!
click 'install now', install it, and restart Firefox.
Go to the site and right click on the icon. Select "Write Style For".
From the submenu, you want to select the whole domain without the 'www'. In this case it would be "for: mstetsondesign.blogspot.com".
You'll get a 'write style' dialog.
That says we want to set the body element's default font back to black, and use !important to override any other stylesheets or attribute level CSS.
That's it. the next time that page loads, the fonts should be a nice readable black.
Aaron, thank you for the suggestion. I went in made the grey a little darker... see what you and Celeste think. I am always up for a little critiquing, plus I'd really hate to be the culprit for astigmatism.
well.. you blog.. but you never figure anyone reads it... never underestimate the power of google to bring people to your door.
Also, your site was chosen at random, from a pile of people who do that. Hope you don't take it personally.
Three-and-a-half months later, and the blog is still unreadable.


← Can You Transform Stress into Ease with a Single Thought?
Self-care is one of my seven key strategies for relieving stress and is the simplest and most effective way to PREVENT stress and overwhelm from taking hold in the first place. In fact, it is a naturally integral part of all seven of them.
Yet, for most of us, self-care is the first thing to go during the craziness of the holiday season. For women like myself, we still have to take care of work, business, family and so forth as usual, on top of the added demands of the season – shopping, parties, baking, card-writing, decorating, and gift-wrapping to name but a few. And while many of these are fun things to do, it often feels like they are putting us over the edge in our already packed schedule and to-do list.
In a workshop I ran recently, one participant described overwhelm as taking stress to the next level. If you're already feeling stressed from work and running your home, the holidays can definitely take us into overwhelm.
In fact, you may feel you have so much to do, you don't have time for self-care.
You need it now more than ever, so you can cope with all the extra demands on you.
Looking after yourself first means you'll be better able to make reasoned decisions about what you need and want to do to be effective, productive and happy this holiday season. You'll have more energy and be more available for your loved ones AND your work. You can be your best self!
Eat a healthy and nutritious diet as much as possible, allowing for treats, of course!
Get enough sleep. Apparently, the majority of adults don't get enough. I find that if I don't get seven to eight hours I don't function well.
Move! I walk (and occasionally run!) outside virtually every day. The exercise and the fresh air both help clear my head. In fact, walking is when I often get my best ideas. I also make a point to get up and move around every so often if I'm doing a lot of computer work.
Have a cup of tea – or sometimes a glass or wine – with a good friend.
And my all-time favorite, Constructive Rest!
I teach this simple and powerful self-care practice to all my clients. It's a way of taking a few minutes time out of your day to rest and restore yourself mentally and physically as you lie down in a semi-supine position. In fact, I think so highly of this practice that a few years ago I created the 30-Day Constructive Rest Challenge, in which I encourage everyone to commit to doing it for a few minutes every day for 30 days, so they can truly experience the benefits for themselves.
Fundamental to my teaching, however, is helping you cultivate the type of thoughts, body awareness and attention to help you relieve stress in the moment. It's this practice of mindfulness and presence that you can apply any time and anywhere, so you have the internal tools to help you effectively reduce stress and find more ease whatever you are doing.
You do not even have to take time out of your day to practice this sort of self-care – it simply requires a little thought and attention while you are doing what you do already!
The holiday season is crazy busy for most of us. I urge you to make YOU a priority this season. By doing so you will have more energy, strength and resilience to get things done AND have fun! It will not only help you be more productive, but will also give you time to be more discerning about what really matters and what does not.
So, whatever holiday you celebrate (or don't!), I wish for you some time for yourself – to do the things that nourish you – and in turn you will lessen, or prevent, overwhelm and stress and burnout before they start.


Just for your information, when you have the insurance from the government, it is normally based on your need, but if you would like to acquire more, it's necessary for you to pay the extra fee on your own. Coinsuranceis the proportion of the price of covered services that you're accountable for paying after the insurance does its part. Insurance That's Right For You It is understandable that every couple has different objectives and needs, so matching the right degree of coverage is a significant choice to make regardless of your circumstance.
Individuals are becoming highly concerned about their wellness. Health insurance makes it possible to cover your care. It is a policy that ensures individuals that they would get expenses reimbursement or cashless treatment while availing medical treatment. Various men and women utilize health insurance differently, and on occasion a careful cost analysis is essential to figure out the very best option. Therefore, after you have health insurance, it doesn't mean you need to ignore your healthy since you feel you already receive any coverage. If you select the private medical insurance, you need to choose what you only require. Deciding upon the appropriate Florida health insurance for your family members can be challenging, but Blue Cross Blue Shield of Florida delivers an assortment of options to help consumers select the right degree of coverage and premium.
The premiums could be higher, but families that need a whole lot of health services can save yourself money. In that case, they do count toward a deduction for medical expenses. As a consequence, their premiums could be at least partially tax-deductible, based on their whole income and their complete medical expenses.
The medical insurance charge is going to be taken out of the student's account when the selection form was validated. While it's challenging to plan for unexpected expenses, comparing your expected procedures and expenses for the following year, will be able to help you understand any extra out-of-pocket expenses you might incur. Out-of-pocket costs are your complete expenses for medical care that aren't paid by your wellbeing insurance policy plan. Getting to the reason for your problem faster also saves your time and money.
The policy has to be in a position to give you tax benefits under the appropriate section of law. A term life policy is ideal for brief amounts of time wherein the excess security is necessary. You might also buy a new policy during Open Enrollment that may qualify for a subsidy. A whole life insurance plan will be more expensive in the very long run but it has the most return for the cost. The second duty is to determine that whether the health insurance plan satisfies your requirements with the ideal suitability. Initially, it's the duty of every person to find out the sort of coverage and whether it's affordable for you or not. There are several reasons that may easily tell the significance of having a private medical insurance for young couples.
Your insurance program will pay for the rest. The medical insurance plan you hold must deal with the particular demands of your family and yours. It is crucial to choose the ideal health insurance policy plan as would suitably fit individual requirements. An effective medical insurance program that is available at a very low cost is going to be a large and meaningful present for your spouse.
Do not become influenced by the new offer except you want it. Your very best choice will depend upon your financial plan, coverage demands, and where you reside. The most suitable choice is dependent on the wellness needs of you and your children, and it may also be dependent upon the direction you like to budget for health care expenses. There are many choices that could assist you in receiving the best health insurance program. WEA Select provides real added benefits to you, our members which other carriers simply can't match.
The organization proceeds to bring improvements and innovations to the procedure for buying health insurance. In some instances, your insurance company might not pay for your care in case you go to a physician or hospital that's not in your wellbeing insurance policy plan. The insurance provider pays for the treatment whenever the medical condition is covered by the health insurance policy policy. For the very same services that you would pay $2070 and the insurance carrier would cover $160.
If you are in possession of a medical emergency you need to go to the closest hospital emergency room. If you get a medical emergency, you should visit the closest hospital emergency room. It is crucial to know that in the event you have a health emergency, you need to go to the closest hospital emergency room.


Colorado-based Pangea Organics made a noticeable splash in the natural cosmetics/bodycare market about two years ago with its new brand identity. Collaborating with internationally-acclaimed branding firm IDEO, Pangea focused on packaging to accompany the high quality organic products it produces.
Much in the same way Aveda has worked to transform its packaging, Pangea operates with the added benefits of independence. Today Pangea's now highly acclaimed molded fiber packaging and brown apothecary style bottles have allowed the brand the ability to shape its own identity and customer base.
Pangea's molded fiber clamshell and boxing for its facial care products have an industrial look to them that stands out on the shelf. The packaging's minimalist style is what makes it stand out. To the touch the packaging feels like a rough industrial piece of linen. All of these elements visual and sensory combine to make a noticeable design.
Success on the shelf is the number one goal of packaging and Pangea has this element down to a science.
Staying ahead of the curve is important for any brand and Pangea's focus on its branding image was right on the mark. The apothecary style glass and plastic bottles it uses for some of its products is at the height of fashion these days. Interior designers scour flea markets looking for old apothecary bottles for clients – Pangea offers them as part of their brand allowing the products to fit into even the most discriminating customer's home decor. Cosmetic/bodycare packaging can be fashionable.
The company's #2 HDPE brown plastic bottles are screen printed rather than using labels.
The challenge of new interesting packaging design coupled with the need to protect the contents of the package was something Pangea approached with great care.
On the molded fiber box packaging Pangea worked with UFP Technologies, Inc. a leading manufacturer of custom engineered packaging materials based in Georgetown, MA.
Before Pangea, molded fiber packaging was commonly used as an inexpensive effective custom protective packaging solution for electronics, consumer goods and items in glass like wine.
In collaboration with UFP Technologies, Pangea created a 100% compostable, biodegradable and plantable package that loosely resembles an egg crate. In fact the technology used in drying the newspaper and water mixture is from the egg crate industry. Its biodegradable and reusable properties make it a viable option in sustaining the environment which was a core element in the concept design.
The packaging is manufactured with zero waste at UFP's molded fiber division in Clinton, Iowa and created from 100% post-consumer newsprint-without glues and dyes.
Always looking to be unique Pangea wanted to embed medicinal herb seeds in the molded fiber paperboard. Consumers can grow medicinal herbs by soaking the box for one minute and planting it in about 1" deep of soil. The whole concept revolves around the idea of packaging having multiple uses and its life cycle continuing beyond its initial purpose.
All of Pangea's bar soaps, as well as its entire skin care line will be packaged in the seeded boxes. Bar soaps will contain Amaranth seeds while facial care packages will contain edible Genovese Sweet Basil seeds.
Today Pangea is working with Behrman Communcations who specialize in creative, strategic brand building. Looking forward to seeing what Pangea's next move is.


Project SLOPE is committed to the advancement of research in college mathematics and two-year college mathematics faculty research. The efforts of the project will include multiple modes of dissemination to diverse audiences within the communities of Mathematics, Mathematics Education, Two-Year Colleges and the Scholarship of Teaching and Learning.
Papers, presentations and other shared outcomes from Project SLOPE will be included in this page as they occur.
A three-part symposium, titled, The Scholarship of Teaching and Learning (SoTL) in College Mathematics was presented at the 43rd AMATYC Annual Conference.
Dewar, J. (2017, November). Exploring teaching and learning in college mathematics.
Symposium keynote presented at the 43rd AMATYC Annual Conference, San Diego, CA.
Dewar, J. & Sitomer, A. (2017, November). Embarking on inquiry in your classroom. Symposium workshop presented at the 43rd AMATYC Annual Conference, San Diego, CA.
Breit-Goodwin, M. & Smith, J.T. (2017, November). Moving from reflective teaching to classroom inquiry. Symposium workshop presented at the 43rd AMATYC Annual Conference, San Diego, CA.
A summary of the AMATYC Symposium on the Scholarship of Teaching and Learning (SoTL) in College Mathematics, and an announcement of Project SLOPE was made in the AWM Newsletter Education Column in January/February 2018 Issue.
Dewar, J. (2018). Teaching mathematics in open-door institutions. Association for Women in Mathematics (AWM) Newsletter 48(1), 13 - 15.
Announcements of Project SLOPE and the Project SLOPE led symposium on the Scholarship of Teaching and Learning (SoTL) in College Mathematics were presented in the 2017 United States Regional Report of ISSOTL.
International Society for the Scholarship of Teaching and Learning. (2017). 2017 United States Regional Report. Retrieved from https://www.issotl.com/regional-reports.


text:
using System;

namespace Hydra.Framework
{
	/// <summary>
	/// Resolves a <see cref="System.Type"/> by name.
	/// </summary>
	/// <remarks>
	/// <p>
	/// The rationale behind the creation of this interface is to centralise
	/// the resolution of type names to <see cref="System.Type"/> instances
	/// beyond that offered by the plain vanilla
	/// <see cref="System.Type.GetType(string)"/> method call.
	/// </p>
	/// </remarks>
	public interface ITypeResolver
	{
		/// <summary>
		/// Resolves the supplied <paramref name="typeName"/> to a
		/// <see cref="System.Type"/>
		/// instance.
		/// </summary>
		/// <param name="typeName">
		/// The (possibly partially assembly qualified) name of a
		/// <see cref="System.Type"/>.
		/// </param>
		/// <returns>
		/// A resolved <see cref="System.Type"/> instance.
		/// </returns>
		/// <exception cref="System.TypeLoadException">
		/// If the supplied <paramref name="typeName"/> could not be resolved
		/// to a <see cref="System.Type"/>.
		/// </exception>
		Type Resolve(string typeName);
	}
}

redpajama_set_name: RedPajamaGithub


I love my hair and this is the second time I have ordered from Alimice. Is soft, natural, and so pretty.
I love hair! It's great. No shedding and no tangling!
Good hair. Ordered from them before but I don't remember this hair getting so tangly so quick. I'll probably stick to straight.
I was a bit skeptical about this hair until I saw the review done by Malibu Doll Face. So I ordered it and I love this hair. The shipping was very fast. I will definitely order this hair again.


Please report your complaint in as much details as possible. Snow Federal Retirement Seminars & ChFEBC, Inc., staff will request additional information if needed. A personal interview, if it appears necessary, may also be requested. One of the functions of Snow Federal Retirement Seminars & ChFEBC, Inc., review board is the evaluation of complaints. Please be assured that your complaint will be investigated vigorously and thoroughly.
Please fill out the form below, and we will respond to you as soon as possible.


The Kasten small parts shelving system with its basic elements and a multitude of accessories is guaranteed to meet all kinds of small parts storage needs. The Kasten small parts shelving concept is based on two standard uprights and a range of shelves with different load bearing capacities.
The basic elements of the Kasten small parts shelving system provide single level as well as multilevel shelving systems up to 18 meters high fully automated central warehouses and distribution centres.


"Voice Signal – a voice recognition package, one of the market's finest as of today. While at the standby screen you can call up voice commands by tapping and holding "0". With this application you can dial a number from your contact book, bring up some menu items and other commands. No prior voice training is required, the handset assumes your current menu language for the needs of this app. Compared with a similar app from Nokia, found in its smartphones, this package is well superior and on top that makes fewer mistakes when dialing a number."
Are you talking in general or about this model? Samsung do have voice command, Its called "anyvoice". Unique thing about it is that you dont even have to pre-record you commands.
Ok. There's an imposter in here.
Actually, I find this phone attractive. Brilliant design, it looks expensive (I hope it isn't that much. LOL!). Nice set of features, but WiFi would've made this phone to die for.
Any one knows how is the sound quality?
this phone.....its really gud luking...and the graphics are owsome...well no wifi..no xenon flash..no GPS....no 3.5 mm jacks.....much disabilities ...but still gud...when will it b available in pakistan?
i want to see voice comand's in samsung phones,thay have the look the design and almost the features.
No Wi-Fi, No EDGE and no combine 3G at 850 & 2100 and use thin Al case. Way to go Samsung. Start reading your compatitors Spec. before coming out with these phones Samsung.
Samsung seems like is focusing to bring as many as more phone to market than anyone else. They also focus in making the most thin phone in market. But all forget that now mostly everyone use Wi-Fi and they should start putting that on thier phones and start making better quality phone than they do now and improve the battery life. Also Samsung does not offer worldwide 3G phone at 850, 1900 and 2100 at same time. Samsung step back and look what are your problems before keep making more and more phones.
Sony ericsson is way behind in terms of pic quality when compared to dis one. NOKIA AND SAMSUNG RULE DA WORLD. If they gonna combine wid each other, then it will be un-beatable venture!
Just read the review of one of da best mobile fones on the best web site. very good fone, excelling functionality, camera and good looks and design at da same time... waiting for its launch in Pakistan... love u gsm arena. you of course r da best!
i noticed that GSMarena has incomplete spec. listings for SOUL.. other website has why they dont have it here?
wow GSMarena made 3 reviews just for SOUL.


Do you love Christmas? Maybe you want to change the fairy garden setup during the holidays to reflect Christmas, or perhaps you love the holiday so much that you want it to be Christmas year round in the garden. When you have the right decorations, such as those available here, you can make this happen! Consider some of the miniature artificial snowy trees, along with some of the great miniatures, such as Santa, angels, elves, Christmas fairies, and more. There is even a Christmas cottage that you might want to bring into your fairy garden. You have plenty of wonderful holiday options.


Even the most secure system has weaknesses. Even the best encryption can be broken. These are golden laws of cybersecurity, rules which every expert knows by heart. Unfortunately, those rules might come into play sooner than any of us realize, according to the head of IBM Research, Arvind Krishna. The reason? Quantum computing.
A revolutionary new technology that's still very much in its nascent stages, quantum computing leverages the fact that subatomic particles can exist in more than one state at a time.
Traditional computers store data in bits, which can exist in one of two states: one or zero. Quantum computers, however, use a new unit of measurement, a single atom known as a qubit (literally "quantum bit"), which "greatly increases the computational power of a system."
Wired Magazine puts forth an excellent analogy for understanding how qubits function as opposed to bits. Picture a sphere. A bit can only exist on one of the sphere's two poles; a qubit, on the other hand, can exist at any point on the sphere. This allows qubits to store and process information faster and more efficiently than modern systems which, in turn, means that a quantum computer can perform operations like debugging millions of lines of code in just a few seconds.
There is a problem with that, though: one of the things a quantum computer is especially well-suited for is numerical analysis. Since large numerical values are the foundation of modern cryptography, this also makes quantum computers ideal for breaking even the strongest forms of encryption. It's a scary thought, made all the more frightening by the fact that this could happen in as little as five years.
"Anyone that wants to make sure their data is protected for longer than 10 years should move to alternate forms of encryption now," Krishna explained.
Quantum computing will break virtually every type of encryption currently used by both businesses and consumers. And if such technology were to make it into the hands of a criminal enterprise or enemy nation-state...?
I'm certain you can do the math.
It's not all doom and gloom, thankfully. There's an alternative mode of encryption which could theoretically prove unbreakable by quantum systems. It's known as lattice cryptography. Not only is it more efficient than modern public-key based encryption methods, but its basis in linear algebra also makes it nearly unbreakable through attack methods other than quantum computing.
In short, it's our best defense against quantum systems once they come into the market. But that's not going to happen in the very near future; for now, at least, we're okay with sticking to the tried-and-true.
Quantum computing is a frightening prospect on paper. The idea of a system that could render most modern security protocols obsolete within a few years is an intimidating one. But it's not like this will be the first time something like this has happened, nor will it be the last.
Technology has always evolved quickly and the business world has (more or less) always managed to keep pace. This will be no different.
Older Post2018 FIFA World Cup: Open Season For Malicious Threats?