text:
\section{Introduction} \label{sec:intro}

Graph data are prevalent in a lot of application domains such as social, biological and mobile networks. Typically, the entities in realities are modeled by graph nodes, and the relationships between entities are modeled by graph edges. Uncertainty is evident in graph data due to a variety of reasons.

Therefore, the methods for querying and mining uncertain graph data are of paramount importance.

Graph clustering is a fundamental problem in graph data mining, where the goal is to partition the graph nodes into some clusters, such that the nodes in each cluster is ``close'' to each other according to some distance measure. Among the numerous problem definitions on graph clustering, the $k$-median and $k$-center problems are perhaps the most celebrated ones which have been studied for decades~\cite{Vazirani2001}. In a traditional graph (without uncertainty), the goal of the $k$-median problem is to find $k$ centering nodes in the network such that the average distance between each node to the centering nodes is maximized, while the goal of the $k$-center problem is to find a set of $k$ nodes for which the largest distance of any point to its closest vertex in the $k$-set is minimum.

Surprisingly, although the $k$-median and $k$-center problems have been extensively studied in the literature, their counterpart problems in uncertain graphs have not been investigated until a recent study by Ceccarello et al.~\cite{Ceccarello17}. Following a large body of work on uncertain graphs, the work in~\cite{Ceccarello17} models an uncertain graph as a traditional graph augmented by existence probabilities associated to the edges. They use the connection probabilities as the distance measure between the nodes, and formulated the $k$-median and $k$-center problems as follows. In the $k$-median problem, they aim to partition the graph nodes into $k$ subsets (clusterings) with a centering node in each of them, such that the average connection probability between each node and its corresponding centering node is maximized. In the $k$-center problem, they aim to maximize the minimum connection connectivity between a node and its centering node. It can be seen that the definitions of their $k$-median and $k$-center problems are in spirit similar to those for the traditional graphs, so they can be considered as the reinterpretations of the $k$-median and $k$-center problems in traditional graphs.

In contrast to the traditional $k$-median and $k$-center problems, there are two unique challenges for clustering uncertain graphs. First, it is a \#P hard problem to compute the connection probability between any two nodes in an uncertain graph. Second, the distance measure described above does obey the triangle inequality, which is required by almost all of the traditional $k$-center and $k$-median algorithms. Therefore, even if we have an oracle for computing the connection probabilities, the traditional $k$-median and $k$-center algorithms cannot be applied to our case.

Based on the above observations, the work in~\cite{Ceccarello17} provide new algorithms for graph clustering problem in uncertain graphs. However, the approximation ratio of their algorithms are far from satisfactory.

\vspace{2.5mm} \noindent
{\bf Contributions.} Motivated by the deficiency of existing techniques, we propose new approximation algorithms for the $k$-median and $k$-center problems in uncertain graphs. Our contributions are summarized as follows.

(1) For the $k$-median problem:

We prove that the $k$-median problem is NP-hard, and propose an approximate algorithm with a $1-1/e$ approximation ratio. We also propose efficient sampling algorithms that achieves a $1-1/e-\epsilon$ approximation ratio when there does not exist an oracle for computing the connection probabilities.

(2) For the $k$-center problem:

We prove that the $k$-center problem is NP-hard to approximate within any bounded ratio. We first propose a simple algorithm with the approximation ratio of $\mathrm{OPT}_k^c$, and then provide a bi-criteria approximation algorithm that achieve $1-\epsilon$ approximation ratio using at most $\mathcal{O}(k\log\frac{n}{\epsilon})$ centering nodes. We also propose algorithms for the $k$-center problem without the connection oracle.

\section{Preliminaries} \label{sec:prelim}

\subsection{Problem Definitions} \label{sec:prelim-IM}

An uncertain graph is represented by $G = (V, E)$ where $V$ is the set of nodes and $E$ is the set edges, with $|V|=n$ and $|E|=m$. We assume that each node in $V$ has a unique node ID in $[1,n]$. Each edge $e\in E$ is associated with a number $p(e)\in (0,1]$ denoting the probability that $e$ exists. For any two nodes $u$ and $v$ in $V$, we use $\mathrm{Pr}[u\sim v]$ to denote the probability that $u$ and $v$ is connected in $G$. For simplicity, we follow the work in~\cite{Ceccarello17} to assume that $G$ is an undirected graph, but our approach can be readily extended to the case of directed graphs, which will be explained later.

A \textit{$k$-clustering} of $G$ can be represented by a tuple $\mathcal{C}=\langle C, Q_1,Q_2,\cdots,Q_k\rangle$, where $C=\{c_1,\cdots,c_k\}$ is the set of \textit{centering nodes} and  $\{Q_1,Q_2,\cdots,Q_k\}$ is a partition of the nodes in $V$ satisfying $c_i\in Q_i$ for all $i\in [k]$. For any $i\in [k]$ and any $v\in Q_i$, we call the node pair $(c_i,v)$ as a \textit{cluster link} of $\mathcal{C}$. We call the set of all clustering links in $\mathcal{C}$ as the \textit{signature} of $\mathcal{C}$, and we use $\mathcal{S}_k^{G}$ to denote the set of signatures of all possible $k$-clusterings of $G$. Note that any two different $k$-clusterings must have different signatures, and we can construct a $k$-clustering from any $A\in \mathcal{S}_k^G$. Therefore, we will also call any $A\in \mathcal{S}_k^G$ as a $k$-clustering. Given any $A\in \mathcal{S}_k^G$, we define
\begin{eqnarray}
&&\mathit{KM}(A)={\sum\nolimits_{(u,v)\in A}{\mathrm{Pr}}[u\sim v]}/{n}\\
&&\mathit{KC}(A)=\min\nolimits_{(u,v)\in A}\mathrm{Pr}[u\sim v]
\end{eqnarray}
With the above definitions, the $k$-median and $k$-center problems can be formally defined as follows:

\begin{definition}
The $k$-median (KMD) problem aims to identify an optimal solution $A^o$ to the following optimization problem:
\begin{eqnarray}
        {\mathbf{Maximize}}&&~~\mathit{KM}(A) \qquad\qquad\qquad\qquad \mathbf{[KMD]}\nonumber\\
        \mathbf{s.t.}&&~~A\in \mathcal{S}_k^G \nonumber
\end{eqnarray}
The $k$-center (KCT) problem aims to identify an optimal solution $B^o$ to the following optimization problem:
\begin{eqnarray}
        {\mathbf{Maximize}}&&~~\mathit{KC}(B) \qquad\qquad\qquad\qquad \mathbf{[KCT]}\nonumber\\
        \mathbf{s.t.}&&~~B\in \mathcal{S}_k^G \nonumber
\end{eqnarray}
\end{definition}

For convenience, we use $\mathrm{OPT}_{k}^m$ to denote $\mathit{KM}(A^o)$, and use $\mathrm{OPT}_{k}^c$ to denote $\mathit{KC}(B^o)$.

\begin{comment}
\subsection{Existing Solutions} \label{sec:prelim-existing}

According to the well-known fact proved in~\cite{}, it is NP-hard to compute $\mathrm{Pr}[u\sim v]$ for any two different nodes $u$ and $v$ in an uncertain graph $G$. Moreover, it is indicated in~\cite{} that $\mathrm{Pr}[u\sim v]$ is not a \textit{metric}, i.e., the following ``triangle inequality'' does not hold:
\begin{eqnarray}
\forall u,v, w \in V: \mathrm{Pr}[u\sim w]\leq \mathrm{Pr}[u\sim v] + \mathrm{Pr}[v\sim w]
\end{eqnarray}
Due to these reasons, the traditional $k$-median and $k$-center problems cannot be applied to our case, as these algorithms generally works under a metric space where the ``distance'' of any two nodes can be computed in polynomial time.

To the best of our knowledge, only the work in~\cite{} has studied the $k$-median and $k$-center problems in uncertain graphs. They first propose algorithms under the case that there exists a connectivity oracle for computing the connection probability between any two nodes in the network, and then propose more practical algorithms without this connectivity oracle. Their results are summarized as follows.

When there is an connectivity oracle, the work~\cite{} conjectures that the $k$-median problem is NP-hard, and proves that the $k$-center problem is NP-hard. They provide an approximation algorithm that achieves an approximation ratio of

\begin{lemma}
When there is a connectivity oracle, the al
\end{lemma}

The first solution to adaptive IM is by \cite{golovin2011adaptive}. It assumes that $b = 1$ (i.e., each batch consists of only one seed node), and adopts a greed approach as follows. Given $G$, it first identifies the node $v_1$ whose expected spread ${\mathbb E}\xspace[I_G(\{v_1\})]$ on $G$ is the largest, and selects it as the first seed. Then, it observes the nodes that are influenced by $v_1$ (which are in accordance to the possible world $w_0$), and removes them from $G$. Let $G_2$ denote the subgraph of $G$ induced by the remaining nodes. After that, for the $i$-th ($i > 1$) batch, it (i) selects the node $v_i$ that with the maximum expected spread ${\mathbb E}\xspace[I_{G_i}(\{v_i\})]$ on $G_i$, (ii) observes the influence of $v_i$ on $G_i$, and then (iii) generates a new graph $G_{i+1}$ by removing from $G_i$ those nodes that are influenced by $v_i$. For convenience, we refer to $G_i$ as the $i$-th {\it residue graph}, and let $G_1 = G$.

Let $OPT_{k, b}$ denote the expected spread of the optimal solution to the adaptive IM problem parameterized with $k$ and $b$. Golovin \textit{et.al.}~\cite{golovin2011adaptive} show that the above greedy approach returns a solution whose expected spread is at least $(1-1/e) \cdot OPT_{k, 1}$. This approximation guarantee, however, cannot be achieved in polynomial time because (i) in the $i$-th batch, it requires identifying a node $v_i$ with the maximum largest expected spread ${\mathbb E}\xspace[I_{G_i}(\{v_i\})]$ on $G_i$, but (ii) computing the exact expected spread of a node is \#P-hard in general \cite{ChenWW2010}.

To remedy the above deficiency, Vaswani~\textit{et.al.} \cite{vaswani2016adaptive} propose a relaxed approach that allows errors in the estimation of expected spreads. In particular, they assume that for any node set $S$ and any residue graph $G_i$, we can derive an estimation $\tilde{{\mathbb E}\xspace}[I_{G_i}(S)]$ of ${\mathbb E}\xspace[I_{G_i}(S)]$, such that
\begin{equation} \label{eqn:prelim-alpha}
c^\bot \cdot {\mathbb E}\xspace[I_{G_i}(S)] \le \tilde{{\mathbb E}\xspace}[I_{G_i}(S)] \le c^\top \cdot {\mathbb E}\xspace[I_{G_i}(S)],
\end{equation}
with $c^\top/c^\bot$ bounded from above by a parameter $\eta$. They show that, by feeding such estimated expected spreads to the greedy approach in \cite{golovin2011adaptive}, it can achieve an approximation guarantee of ${1 - \exp\left(-1/\eta\right)}$. In addition, they show that the greedy approach can be extended to the case when $b > 1$, with one simple change: in the $i$-th batch, instead of selecting only one node, we select a size-$b$ seed set $S_i$ whose estimated expected spread on $G_i$ is at least $1 - 1/e$ fraction of the largest estimated expected spread on $G_i$. In that case, they show that the resulting approximation guarantee is ${1-\exp\left(-\frac{(1-1/e)^2}{\eta}\right)}$.

Unfortunately, the accuracy requirement in Equation~\ref{eqn:prelim-alpha} is so stringent that no existing algorithm for evaluating expected spread can meet the requirement without incurring prohibitive computation costs. To understand this, observe that when ${\mathbb E}\xspace[I_{G_i}(S)]$ is very small, Equation~(\ref{eqn:prelim-alpha}) allows only a tiny amount of estimation error in $\tilde{{\mathbb E}\xspace}[I_{G_i}(S)]$, in which case the derivation of $\tilde{{\mathbb E}\xspace}[I_{G_i}(S)]$ is extremely challenging. Due to this issue, Vaswani~and Lakshmanan \cite{vaswani2016adaptive} propose to trade accuracy for efficiency and adopt algorithms that do not enforce Equation~\ref{eqn:prelim-alpha}, but fail to establish any non-trivial approximation guarantees accordingly.

\end{comment}

\section{Solving the $k$-median problem} \label{sec:frame}

\subsection{Hardness of the $k$-Median Problem}

The prior work~\cite{Ceccarello17} has conjectured that the $k$-median problem is NP-hard. We prove this conjecture in the following theorem, by a reduction from the NP-hard Dominating Set problem:

\begin{theorem}
The $k$-median problem is NP-hard, even if there exists an oracle for computing $\forall u,v\in V: \Pr[u\sim v]$.
\label{thm:hardnesskmedian}
\end{theorem}
\begin{proof}
We prove the theorem by a reduction from the NP-hard \textit{dominating set} problem~\cite{Vazirani2001}. Given any undirected graph $G=(V,E)$ with $|V|=n$ and any integer $k$, the decision version of the dominating set problem asks whether there exists $S\subseteq V$ with $|S|= k$ such that each node in $V\backslash S$ is adjacent to certain node in $S$. Given such an instance $G$ of the dominating set problem, we can construct an uncertain graph by setting $p(e)=q=\frac{1}{n(n-k+2)}$ for each $e\in E$. Suppose that there exists a polynomial-time algorithm $\mathcal{A}_{opt}$ to optimally solve the $k$-median problem. So we can run it on the uncertain graph $G$ described above, and get an optimal $k$-clustering with its signature denoted by $\tilde{A}$. In the sequel, we will prove that: the graph $G$ has a dominating set $S$ satisfying $|S|= k$ if and only if $\mathit{KM}(\tilde{A})\geq k+(n-k)q$

If the graph $G$ has a dominating set $S$ satisfying $|S|= k$, then we can use $S$ as the set of center nodes, and hence we must have $\mathit{KM}(\tilde{A})\geq k+(n-k)q$. Conversely, if $G$ does not have a dominating set $S$ satisfying $|S|= k$, then there must exist a cluster link $(u,v)$ in $\tilde{A}$ such that $u$ and $v$ are not adjacent, and hence we get
\begin{eqnarray}
\mathrm{Pr}[u\sim v]\leq nq^2+ n^2q^3 + n^3 q^4 +\cdots \leq \frac{nq^2}{1-nq},
\end{eqnarray}
where $n^iq^{i+1}$ is an upper bound for the probability that $u$ is connected to $v$ through $i+1$ hops. Moreover, for any $(u',v')\in \tilde{A}\backslash \{(u,v)\}$ satisfying $u'\neq v'$, we must have
\begin{eqnarray}
\mathrm{Pr}[u'\sim v']\leq q+{nq^2}/{(1-nq)}
\end{eqnarray}
Therefore, we have
\begin{eqnarray}
\mathit{KM}(\tilde{A})&\leq& k+ (n-k-1)\left(q+\frac{nq^2}{1-nq}\right)+\frac{nq^2}{1-nq}\nonumber\\
&<& k+(n-k)q
\end{eqnarray}
The above reasoning implies that, if $\mathcal{A}_{opt}$ exists, then the dominating set problem can also be optimally solved in polynomial time. Hence, the theorem follows.
\end{proof}

\subsection{$k$-Median Algorithms with an Oracle}

In this section, we assume that there exists a \textit{connectivity oracle}, i.e., $\mathrm{Pr}[u\sim v]$ can be computed in polynomial time for any $u\in V$ and $v\in V$.

It is highly non-trivial to find an approximation solution to the $k$-median problem, as it has a large searching space $\mathcal{S}_k^G$ with the cardinality of ${n\choose k}k^{n-k}$. However, we find that the $k$-median problem can be transformed into a submodular maximization problem with a much-reduced searching space, as described below.

For any $C\subseteq V$ and any $v\in V$, we define
\begin{eqnarray}
f_v(C)=\max\{\mathrm{Pr}[u\sim v]\mid u\in C\};~F(C)=\sum\limits_{v\in V}f_v(C)
\end{eqnarray}

\begin{algorithm} [t]
        $C\leftarrow \emptyset$\\
        \While{$|C|<k$}{
            Find $u\in V\backslash C$ such that $g(C\cup\{u\})-g(C)$ is maximized;\\
            $C\leftarrow C\cup\{u\}$
        }
  \Return{$C$}
  \caption{$\mathsf{Greedy}(G, k,g(\cdot))$}
    \label{alg:greedyalgorithm}
\end{algorithm}

It is noted that, for any $A\in \mathcal{S}_k^G$, there must exist certain $C\subseteq V$ such that $|C|=k$ and $F(C)\geq \mathit{KM}(A)$. Moreover, given any $C\subseteq V$, we can easily construct a $k$-clustering $A$ such that $C$ is the set of centering nodes in $A$ and $F(C)=\mathit{KM}(A)$.  Therefore, the $k$-Median problem can be transformed into the following equivalent optimization problem:
  \begin{eqnarray}
        {\mathbf{Maximize}}&&~~\sum\nolimits_{v\in V}f_v(C) \qquad\qquad\qquad\qquad \mathbf{[KMD1]}\nonumber\\
        \mathbf{s.t.}&&~~|C|= k;~~C\subseteq V \nonumber
  \end{eqnarray}
Moreover, we find that the [KMD1] problem is actually a submodular maximization problem, as shown by the following theorem:

\begin{theorem}
For any $v\in V$, the function $f_v(\cdot)$ is a monotone and submodular function defined on $2^V$.
\label{thm:submodularitythm}
\end{theorem}
It is a well-known fact that monotone submodular maximization problems can be addressed by a greedy algorithm with a $1-1/e$ approximation ratio. Therefore, we can use a greedy algorithm (shown in Algorithm~\ref{alg:greedyalgorithm}) to find a $1-1/e$ approximation to [KMD1] and hence to the $k$-median problem. i.e.:

\begin{theorem}
Using the $\mathsf{Greedy}(G, k,F(\cdot))$ algorithm, we can find a solution with a $1-1/e$ approximation ratio ti the $k$-median problem.
\end{theorem}

Besides, we can also provide a $1/k$ approximation to the $k$-median problem. Consider the following problem:

\begin{eqnarray}
        {\mathbf{Maximize}}&&~~\sum_{u\in C}\sum_{v\in V}\Pr[u\sim v] \qquad\qquad\qquad \mathbf{[KMD2]}\nonumber\\
        \mathbf{s.t.}&&~~|C|= k;~~C\subseteq V \nonumber
\end{eqnarray}

We have the following theorem:

\begin{theorem}
Suppose that $C^{\dag}$ is an optimal solution to the [KMD2] problem. We have $F(C^{\dag})\geq (1/k)\mathit{KM}(A^o)$.
\end{theorem}
\begin{proof}
Suppose that $C^o_{km}$ is the set of centering nodes in $A^o$. We have
\begin{eqnarray}
&&F(C^{\dag})=\sum\nolimits_{v\in V}\max\{\mathrm{Pr}[u\sim v]\mid u\in C^{\dag}\} \nonumber\\
&\geq& \sum\nolimits_{v\in V}(1/k)\sum\nolimits_{u\in C^{\dag}} \Pr[u\sim v] \nonumber\\
&\geq& (1/k)\sum\nolimits_{v\in V}\sum\nolimits_{u\in C^o_{km}} \Pr[u\sim v] \nonumber\\
&\geq& (1/k)\mathit{KM}(A^o) \nonumber
\end{eqnarray}
Hence, the theorem follows.
\end{proof}

\subsection{$k$-Median Algorithms without Oracle}

In this section, we consider a more practical setting where the connection oracle is absent. We will first provide a basic sampling algorithm to address the $k$-median problem, and then provide some more efficient algorithms.

\subsubsection{A Basic Sampling Algorithm for $k$-Median}

A random sample $R$ of $G$ is a graph generated by removing each edge $e$ in $G$ with the probability of $1-p(e)$. For any $u,v\in V$ and any random sample $R$ of $G$, let $X_R(u\sim v)=1$ when $u$ and $v$ is connected in $R$, and $X_R(u\sim v)=0$ when $u$ and $v$ is not connected in $R$. For any set $\mathcal{R}$ of random samples of $G$, define
\begin{eqnarray}
\wht{\mathrm{Pr}}}[{\mathcal{R},u\sim v]=\sum\nolimits_{R\in \mathcal{R}}X_R(u\sim v)/|\mathcal{R}|\nonumber\\
{\wht{\mathit{KM}}}({\mathcal{R}},A)={\sum\nolimits_{(u,v)\in A}\wht{\mathrm{Pr}}[{\mathcal{R}}, u\sim v]}/{n}\nonumber
\end{eqnarray}
It can be seen that $\wht{\mathrm{Pr}}[{\mathcal{R}},u\sim v]$ and $\wht{\mathit{KM}}(\mathcal{R},A)$ are unbiased estimations of ${\mathrm{Pr}}[u\sim v]$ and $\mathit{KM}(A)$, respectively. Similarly, for any $A\in \mathcal{S}_k$, any $C\subseteq V$ and any $v\in V$, we define
\begin{eqnarray}
&&\wht{f}_v(\mathcal{R},C)=\max\{\wht{\mathrm{Pr}}}[{\mathcal{R},u\sim v]\mid u\in C\}\nonumber\\
&&\wht{F}(\mathcal{R},C)=\sum\nolimits_{v\in V}\wht{f}_v(\mathcal{R},C)\nonumber
\end{eqnarray}

\begin{algorithm} [t]
  $C^*\leftarrow \mathsf{Greedy}(G,k,\wht{F}(\mathcal{R},\cdot));~~ A^*\leftarrow D(\mathcal{R},C^*)$\\
  \Return{$A^*$}
    \caption{$\mathsf{SearchKM}(G,k,\mathcal{R})$}
    \label{alg:searchkm}
\end{algorithm}

As computing the connection probabilities is NP-hard, it is hard to find the cluster links even if we know the set of centering nodes in an optimal solution. To bypass this difficulty, we create a mapping between $V_k=\{C|C\subseteq V\wedge |C|=k\}$ and $\mathcal{S}_k^G$ to reduce the number of generated samples for identifying the cluster links. More specifically, given any set $\mathcal{R}$ of random samples, each node set $C\in V_k$ is mapped to a unique $k$-clustering $D(\mathcal{R},C)$ in $\mathcal{S}_k^G$, such that any cluster link $(c,v)\in D(\mathcal{R},C)$ (with $c\in C$) that satisfies: 1) $\wht{\mathrm{Pr}}[\mathcal{R},c\sim v]=\wht{f}_v(\mathcal{R},C)$; 2) The node ID of $c$ is minimized under condition 1).

With the above definitions, we design the $\mathsf{SearchKM}$ algorithm to find an approximate solution. Given a set $\mathcal{R}$ of random samples, the $\mathsf{SearchKM}$ algorithm first calls the $\mathsf{Greedy}$ algorithm to find a set $C^*$ of center nodes, and then returns $A^*=D(\mathcal{R},C^*)$ as an approximate solution. To ensure that $A^*$ has a good approximation ratio, we give the following theorem to determine a upper-bound for the number of generated samples:
\begin{theorem}
If $|\mathcal{R}|\geq T_{max}$ where
\begin{eqnarray}
T_{max}= \left\lceil \frac{2(2e-1)(e\epsilon+2e-1)}{3e^2\epsilon^2\mathrm{OPT}_{k}^m}\ln\frac{{n\choose k}+1}{\delta}\right\rceil=\mathcal{O}\left(\frac{n}{\epsilon^2}\log\frac{n}{\delta}\right),\nonumber
\end{eqnarray}
then the $\mathsf{SearchKM}(G,k,\mathcal{R})$ algorithm returns a $(1-1/e-\epsilon)$-approximate solution $A^*$ to the $k$-median problem with probability of at least $1-\delta$.
\label{thm:samplingubforkmedian}
\end{theorem}

\subsubsection{Accelerations}

The $\mathsf{SearchKM}$ algorithm can be further accelerated by leveraging the submodularity of the function $\wht{F}(\mathcal{R},\cdot)$, as shown by the $\mathsf{SearchKM+}$ algorithm. The $\mathsf{SearchKM+}$ algorithm maintains a value $\mathit{UB}(v)$ for each $v\in V$, which denotes an upper bound for the marginal gain of $v$ with respect to the currently selected node set $C^*$. Initially, $\mathsf{SearchKM+}$ calls $\mathsf{GetFirstNode}(\mathcal{R})$ to calculate $\mathit{UB}(v)=\wht{F}(\mathcal{R},\{v\})$ for all $v\in V$, and then add $u^*=\arg\max_{u\in V}\mathit{UB}(v)$ into $C^*$. After that, it sorts $V$ into the node list $W$ according to the non-increasing order of $\forall v\in V: \mathit{UB}(v)$, and re-compute $\mathit{UB}(v)$ only when necessary.

It can be seen that the idea of $\mathsf{SearchKM+}$ is similar in spirit to the ``lazy greedy'' algorithm proposed in~\cite{LeskovecKGFVG2007}. However, the lazy greedy algorithm has not considered the ``cold start'' problem, i.e., how to efficiently compute the upper bound of the marginal gain of any node in $V$ (i.e., $\mathit{UB}(v)$) in the initialization phase. In our case, a naive approach for computing the initial value of $\mathit{UB}(v)$ requires $\mathcal{O}(n)$ time for any $v\in V$, as we need to calculate $\wht{f}_u(\mathcal{R},\{v\})$ for each $u\in V$. However, using the $\mathsf{GetFirstNode}$ procedure, we only need $\mathcal{O}(1)$ time to compute $\mathit{UB}(v)$.

The $\mathsf{SearchKM+}$ algorithm can be further accelerated by borrowing some ideas from the OPIM sampling framework proposed in~\cite{Tang2018}. The resulted algorithm is shown in Algorithm~\ref{alg:opimkm}. We can prove:

\begin{theorem}
With probability of at least $1-\delta$, the $\mathsf{SamplingKM}$ algorithm returns a $k$-clustering with a $1-1/e-\epsilon$ approximation ratio. The expected number of random samples generated in $\mathsf{SamplingKM}$ is at most $\mathcal{O}(\frac{1}{\epsilon^2\mathrm{OPT}_k^m}\ln\frac{1}{\delta})$.
\end{theorem}

\begin{algorithm} [t]
        $(u,W)\leftarrow \mathsf{GetFirstNode}(\mathcal{R});~~C^*\leftarrow \{u\}$\\
        \While{$|C^*|<k$}{
            $(u,W)\leftarrow \mathsf{GetNextNode}(W,\wht{F}(\mathcal{R},\cdot),C^*)$\\
            $C^*\leftarrow C^*\cup\{u\}$
        }
  \Return{$C^*$}
    \caption{$\mathsf{SearchKM+}(G,k,\mathcal{R})$}
    \label{alg:searchkm}
\end{algorithm}

\begin{algorithm} [t]
        \ForEach{$v\in V$}{
            $\mathit{UB}(v)\leftarrow$ the summation of the sizes of the connected components in $\mathcal{R}$ that contain $v$;
		}
        Sort $V$ into the node list $W$ according to the non-increasing order of $\mathit{UB}(v):v\in W$;\\
      Remove the first node $w_1$ from $W$;\\
    \Return{$(w_1,W)$}
    \caption{$\mathsf{GetFirstNode}(\mathcal{R})$}
    \label{alg:bisearch}
\end{algorithm}

\begin{algorithm} [t!]

        \For{$i\leftarrow 1$ \KwTo $|W|$}{
            $\mathit{UB}(w_i)\leftarrow g(C\cup \{w_i\})-g(C)$\\
            \lIf{$\mathit{UB}(w_i)\geq \mathit{UB}(w_{i+1})$}{\textbf{break}}
		}
    Re-sort the nodes in $W$ according to the non-increasing order of $\mathit{UB}(v): v\in W$\\
    Remove the first node $w_1$ from $W$;\\
    \Return{$(w_1,W)$}
    \caption{$\mathsf{GetNextNode}(W,g(\cdot),C)$}
    \label{alg:bisearch}
\end{algorithm}

\section{A Batched Sampling Algorithm} \label{sec:batch}

\begin{algorithm}[ht!]
     \label{alg:opimkm}
	\caption{$\mathsf{SamplingKM}(G,k,\epsilon,\delta)$}
    $T_{max}\leftarrow \frac{2(2e-1)(e\epsilon+2e-1)n}{3e^2\epsilon^2 k}\ln\frac{{n\choose k}+1}{\delta};~~T\leftarrow T\cdot \epsilon^2 k/n$\\
	Generate two sets $\mathcal{R}_{1}$ and $\mathcal{R}_{2}$ of random samples of $G$, such that $|\mathcal{R}_{1}|$ = $|\mathcal{R}_{2}|$ = $T$\;
	$i_{max} \gets \lceil \log_{2} (T_{max}/T) \rceil $\;
	\For{$i \gets 1$ $\mathbf{to}$ $i_{max}$}{
		            $A^*\leftarrow \mathsf{SearchKM}(G,k,\mathcal{R}_1)$ \\
                    $a\gets \ln (3 i_{max}/\delta);~~\theta\leftarrow |\mathcal{R}_1|$\\
	 				$\mathrm{lb}(A^*)\gets \left(\sqrt{\wht{\mathit{KM}}(\mathcal{R}_2, A^*)} - \sqrt{\frac{a}{6\theta}}\right)^{2} - \frac{a}{6\theta}$\\
                    $\mathrm{ub}(A^o)\gets  \left( \sqrt{\frac{\wht{\mathit{KM}}(\mathcal{R}_1, A^*)}{1 - 1/e} + \frac{2a}{3\theta}} + \sqrt{\frac{a}{6\theta}} \right)^2 - \frac{a}{6\theta}$\\
	  				\If{ $\mathrm{lb}(A^*)/\mathrm{ub}(A^o) \ge 1-1/e-\epsilon $ $\mathbf{or}$ $ i=i_{max}$}{$\mathbf{return}$ $A^{*}$}
	     			double the sizes of $\mathcal{R}_{1}$ and $\mathcal{R}_{2}$ with new random samples;
     	}
\end{algorithm}

\section{Solving the k-center problem}

In this section, we address the $k$-center problem both with a connection oracle assumption and without it.

\subsection{k-Center Algorithms with an Oracle}

\subsubsection{A Simple Algorithm}
\label{sec:asimplealgorithm}

The work in~\cite{Ceccarello17} has proved that the connection probabilities of any three nodes $u,v,w\in V$ must satisfy
\begin{eqnarray}
\Pr[u\sim w]\geq \Pr[u\sim v]\cdot \Pr[v\sim w]
\end{eqnarray}
Let $d(u,v)=-\ln \Pr[u\sim v]$ and $d_v(C)=\min_{u\in C}d(u,v)$, so we have
\begin{eqnarray}
d(u, w)\leq  d(u, v)+ d(v,w)
\end{eqnarray}
which implies that $d(\cdot)$ is a metric. Consider the following problem:
  \begin{eqnarray}
        {\mathbf{Minimize}}&&~~\max_{v\in V} d_v(C) \qquad\qquad\qquad\qquad \mathbf{[KCT0]}\nonumber\\
        \mathbf{s.t.}&&~~|C|= k;~~C\subseteq V \nonumber
  \end{eqnarray}
It can be seen that the set of centering nodes in $B^o$ is also an optimal solution to the [KCT0] problem. Note that [KCT0] is a metric $k$-center problem, so it can be addressed by a simple greedy algorithm with a 2 approximation ratio~\cite{williamson2011design}. More specifically, the greedy algorithm initializes by selecting an arbitrary node, and then iteratively selects a node which is furthest to the currently selected nodes until $k$ nodes are selected. With this greedy algorithm, we can find $B^*\in \mathcal{S}_k^G$ such that $-\ln \mathit{KC}(B^*)\leq -2\ln \mathit{KC}(B^o)$, which implies that
\begin{eqnarray}
\mathit{KC}(B^*)\geq (\mathrm{OPT}_k^c)^2  \label{eqn:arofgreedykcenter}
\end{eqnarray}

\subsubsection{A Bi-Criteria Approximation Algorithm}
\label{sec:bisearchwithoracle}

Note that the approximation ratio proposed by~\eqref{eqn:arofgreedykcenter} can be arbitrarily bad, as $\mathrm{OPT}_k^c$ can be arbitrarily small. Therefore, we ask whether there exists an algorithm with a bounded approximation ratio for the $k$-center problem. Unfortunately, we find that:

\begin{theorem}
Unless P=NP, no polynomial-time algorithm can find a solution to the $k$-center problem within any approximation ratio $\alpha>0$, even if there exists a connectivity oracle.
\label{thm:inapprofkcenter}
\end{theorem}

As the $k$-center problem is NP-hard to approximate, we further ask the question whether there exists a \textit{bi-criteria approximation algorithm} for it, i.e., we permit such an algorithm to use more than $k$ center nodes, such that it can approach $\mathrm{OPT}_k^c$.
However, the following theorem reveals that, we cannot achieve a large connectivity probability unless we allow the usage of a ``sufficiently large'' number of centering nodes:

\begin{theorem}
Unless P=NP, no algorithm can find a $l$-clustering $B$ in polynomial time, such that $\mathit{KC}(B)\geq \mathrm{OPT}_{k}^c$ and $l<k\ln n$.
\label{thm:kcboundedbylnn}
\end{theorem}

Based on Theorem~\ref{thm:kcboundedbylnn}, we propose a bi-criteria approximation algorithm with nearly tight approximation ratios. First, we re-formulate the [KCT] problem into the following [KCT1] problem:
  \begin{eqnarray}
        {\mathbf{Maximize}}&&~~\min_{v\in V} f_v(C) \qquad\qquad\qquad\qquad \mathbf{[KCT1]}\nonumber\\
        \mathbf{s.t.}&&~~|C|= k;~~C\subseteq V \nonumber
  \end{eqnarray}
It can be seen that, for any $k$-clustering $B\in \mathcal{S}_k^G$, we must have $\mathit{KC}(B)\leq \min_{v\in V} f_v(C_B)$, where $C_B$ denotes the set of centering nodes in $B$. Therefore, the [KCT1] problem is equivalent to the [KCT] problem.

\begin{algorithm} [ht!]
		$[q_1,q_2]\leftarrow [0,1]; C^*\leftarrow \emptyset$ \label{ln:setab}\\
		\Repeat{$q_1\geq(1-\epsilon_2)q_2$}
		{
			 $C\leftarrow \emptyset;~~q\leftarrow \frac{q_1+q_2}{2}$\\
            $L(q,\cdot)\gets \sum_{v\in V}\min\{q,f_v(\cdot)\}$\\
            \Repeat{$L(q,C)\geq nq-\epsilon_1 q$}
                {
                    $v^*\leftarrow \arg\max_{u\in V\backslash C}[L(q,C\cup \{u\})-L(q,C)]$;\\
                    $C\leftarrow C\cup \{v^*\}$\\
                    \lIf{$|C|>\lceil\ln\frac{n}{\epsilon_1 } \rceil k$}{\textbf{break}}
                }

			\eIf{$|C| \leq \lceil\ln\frac{n}{\epsilon_1 } \rceil k$ \label{ln:judgeca}}
			{
				$C^*\leftarrow C;~~ q_1 \leftarrow q$ \label{ln:setS}
			}
			{
				$q_2 \leftarrow q$ \label{ln:setb}
			}

		}\label{ln:repeatends}
  \Return{$C^*$}
    \caption{$\mathsf{SearchKC}(\epsilon_1,\epsilon_2, f_v(\cdot))$}
    \label{alg:bisearch}
  \end{algorithm}

Recall that the $f_v(\cdot)$ is monotone and submodular for any $v\in V$. Therefore, the [KCT1] problem is similar to the ``robust submodular maximization'' problem studied in~\cite{krause2008robust}. However, the algorithms and performance bounds proposed in~\cite{krause2008robust} are only suitable for the case where the considered submodular function is integer-valued, while the function $f_v(\cdot)$ in our case is generally non-integral. Therefore, we adapt the algorithms proposed in~\cite{krause2008robust} to our case and prove new performance bounds, as described in the following.

Our algorithm is based on a ``potential function'' $L$ defined as follows:
\begin{eqnarray}
\forall q\in (0,1], \forall C\subseteq V: L(q,C)=\sum\nolimits_{v\in V}\min\{q,f_v(C)\}
\end{eqnarray}
As $f_v()$ is a submodular function, it can be verified that $L(q,\cdot)$ is also a submodular function for any $q\in (0,1]$. Moreover, the function $L$ has a remarkable property that it can be used to find an upper bound of $\mathrm{OPT}_k^c$, as clarified by the following lemma:
\begin{lemma}
Let $C=\mathsf{Greedy}(\lceil\ln\frac{n}{\epsilon_1 } \rceil k, L(q,\cdot))$. If $L(q,C)< nq-\epsilon_1q$, then $q$ must be an upper bound of $\mathrm{OPT}_k^c$.
\label{lma:judgegreedy}
\end{lemma}

Note that $L(q,C)\geq nq-\epsilon_1 q$ implies that $\min_{v\in V} f_v(C)\geq (1-\epsilon_1) q$. So Lemma~\ref{lma:judgegreedy} actually tells that, if $q<\mathrm{OPT}_k^c$, then we can use function $L$ and the $\mathsf{Greedy}$ procedure to find a clustering $B$ with at most $\lceil\ln\frac{n}{\epsilon_1 } \rceil k$ centering nodes such that $\wht{KC}(B)\geq (1-\epsilon_1)q$. Conversely, if such a clustering cannot be obtained, then we must have $\mathrm{OPT}_k^c\leq q$.

With Lemma~\ref{lma:judgegreedy}, we can use a binary searching process to find an approximate solution to [KCT1], as shown by the $\mathsf{SearchKC}$ algorithm. In the $\mathsf{SearchKC}$ algorithm, we maintain a searching interval $[q_1,q_2]$ (initialized to $[0,1]$), and use Lemma~\ref{lma:judgegreedy} to judge whether $q=\frac{q_1+q_2}{2}$ is an upper bound of $\mathrm{OPT}_k^c$. If we find that $\mathrm{OPT}_k^c\leq q$, then we halves $[q_1,q_2]$ by setting $q_2=q$. Otherwise, we also halves $[q_1,q_2]$ by setting $q_1=q$. As such, we always have
\begin{eqnarray}
\mathrm{OPT}_k^c \leq q_2;~|C^*|\leq \lceil\ln\frac{n}{\epsilon_1 } \rceil k;~\min_{v\in V} f_v(C)\geq (1-\epsilon_1) q_1
\end{eqnarray}
throughout the binary searching process, where the last inequality is due to $L(q_1,C)\geq nq-\epsilon_1 q$. Note that the binary searching process stops when $q_1\geq (1-\epsilon_2)q_2$. So we immediately get the following theorem:

\begin{theorem}
For any $\epsilon, \epsilon_1,\epsilon_2\in (0,1)$ satisfying $1-\epsilon=(1-\epsilon_1)(1-\epsilon_2)$, the $\mathsf{SearchKC}$ algorithm can find a solution that achieves $(1-\epsilon)\mathrm{OPT}_k^c$, using at most $ \left\lceil \ln\frac{n}{\epsilon_1}\right\rceil k$ centers. This algorithm has no more than $\lceil\log_2 \frac{1}{\epsilon_2\cdot \mathrm{OPT}_k^c}\rceil$ iterations.
\end{theorem}

\subsection{$k$-Center Algorithms without an Oracle}

\subsubsection{Approximation Algorithm using Sampling}

In this section, we study whether the algorithm suggested in Sec.~\ref{sec:asimplealgorithm} can be implemented without a connection oracle. Define
\begin{eqnarray}
\wht{d}({\mathcal{R}},u,v)= -\ln \wht{\Pr}[\mathcal{R},u\sim v];~\wht{d}(\mathcal{R},v,C)=\min_{u\in C}\wht{d}({\mathcal{R}},u,v)\nonumber
\end{eqnarray}
With this definition, we propose an approximation algorithm as follows:

\begin{algorithm} [ht!]
		Select an arbitrary node $v\in V$ and add it into $C^*$\\
		\While{$|C^*|< k$}
		{
            Find $v^*\in V\backslash C^*$ such that $\wht{d}(\mathcal{R},v^*,C^*)$ is maximized;\\
            $C\leftarrow C\cup \{v^*\}$\\

		}\label{ln:repeatends}
    $B^*\gets D(\mathcal{R},C^*)$\\
  \Return{$C^*,B^*$}
    \caption{$\mathsf{SearchKC\_1}(G, k, \mathcal{R})$}
    \label{alg:searchkc1}
  \end{algorithm}

Next, we study the problem of how to determine the cardinality of $\mathcal{R}$ such that the $k$-clustering $B^*$ returned by the $\mathsf{SearchKC\_1}$ algorithm can achieve a good approximation ratio. We give the following theorem:

\begin{theorem}
Given any $\epsilon,\epsilon_1,\epsilon_2,\delta\in (0,1)$ satisfying $\epsilon=\epsilon_1+\epsilon_2$, and given any set $\mathcal{R}$ of random samples of $G$ satisfying
\begin{eqnarray}
|\mathcal{R}|\geq \max\left\{ \frac{2(1+\epsilon_1)}{3\epsilon_1^2(\mathrm{OPT}_k^c)^2}\ln\frac{n(n-1)}{\delta}, \frac{2(1-\epsilon_1)}{3\epsilon_2^2(\mathrm{OPT}_k^c)^2}\ln\frac{n(n-1)}{\delta} \right\},\nonumber
\end{eqnarray}
the $\mathsf{SearchKC\_1}(G, k, \mathcal{R})$ can return a $k$-clustering $B^*$ satisfying $\mathit{KC}(B^*)\geq (1-\epsilon)(\mathrm{OPT}_k^c)^2$ with probability of at least $1-\delta$.
\label{thm:samplenum1}
\end{theorem}

As $\mathrm{OPT}_k^c$ is unknown, we present an algorithm that iteratively ``guesses'' $\mathrm{OPT}_k^c$ until a good solution is found, as shown by Algorithm~\ref{alg:samplingkc1}.

\begin{algorithm} [t]
   \KwIn{$\epsilon=\epsilon_1+\epsilon_2$
		$\mathcal{R}\leftarrow \emptyset;\mathcal{R}'\leftarrow \emptyset;i\gets 0$ \label{ln:setab}\\
		\Repeat{$z(u,v)\geq q$}
		{
            $i\gets i+1;~q\leftarrow 2^{-i};~\delta\gets \frac{6\delta}{\pi^2 i^2};~\mathcal{R}\gets \mathcal{R}\cup \mathcal{R}'$\\
			$\ell\gets \max\left\{ \frac{2(1+\epsilon_1)}{3\epsilon_1^2 q^2}\ln\frac{2n(n-1)}{\delta},\frac{2(1-\epsilon_1)}{3\epsilon_2^2 q^2}\ln\frac{2n(n-1)}{\delta}\right\}$;\\
            \If{$|\mathcal{R}|<\ell$}{
                    Add more random samples into $\mathcal{R}$ until $|\mathcal{R}|\geq \ell$\\

            }
            $(C^*,B^*)\gets \mathsf{SearchKC\_1}(G, k, \mathcal{R})$\\
            Generate another set $\mathcal{R}'$ of random samples such that $|\mathcal{R}'|=|\mathcal{R}|$\\
            \ForEach{$(u,v)\in B^*\wedge u\neq v$}{
                $a\gets \ln\frac{2(n-k)}{\delta};~\theta\gets |\mathcal{R}'|$\\
                $z(u,v)\gets \left(\sqrt{\wht{\Pr}[\mathcal{R}', u\sim v]} - \sqrt{\frac{a}{6\theta}}\right)^{2} - \frac{a}{6\theta}$
            }
            $(u^*,v^*)\gets \arg\min_{(u,v)\in B^*\wedge u\neq v} z(u,v)$

		}\label{ln:repeatends}
  \Return{$(C^*,B^*)$}
    \caption{$\mathsf{SamplingKC\_1}(\epsilon_1,\epsilon_2,\epsilon,\delta)$}
    \label{alg:samplingkc1}
  \end{algorithm}

\subsubsection{Sampling for Bi-Criteria Approximation}
A straightforward idea is that, we first generate a set $\mathcal{R}$ of random samples, and then call the $\mathsf{SearchKC}$ algorithm by replacing the function $f_v(\cdot)$ by $\wht{f}_v(\mathcal{R},\cdot)$. After the $\mathsf{SearchKC}$ algorithm returns a set $C^*$ of centering nodes, we use $B^*=D(\mathcal{R},C^*)$ as an approximate solution to the $k$-center problem. Clearly,   if $|\mathcal{R}|$ is sufficiently large, then $B^*$ should achieve an approximation ratio close to that we can get with an connectivity oracle. The key problem in this approach, however, is how to determine the cardinality of $\mathcal{R}$. In the following theorem, we propose an upper bound for the number of random samples needed to be generated:

\begin{theorem}
Let $\epsilon_1,\epsilon_2,\epsilon_3,\epsilon$ and $\delta$ be any numbers in $(0,1)$ that satisfy $(1-\epsilon)(1+\epsilon_3)=(1-\epsilon_1)(1-\epsilon_2)(1-\epsilon_3)$.
Let $\mathcal{R}$ be any set of random samples of $G$ such that $$|\mathcal{R}|\geq \frac{2(1+\epsilon_3)}{3\epsilon_3^2 (1-\epsilon) \mathrm{OPT}_k^c}\ln\frac{n^2+n-2k}{2\delta}.$$
Then, we can use the $\mathsf{SearchKC}$ algorithm to find a $k$-clustering $B^*$ with no more than $\lceil \ln \frac{n}{\epsilon_1}\rceil k$ centering nodes such that $\mathit{KC}(B^*)\geq (1-\epsilon)\mathrm{OPT}_{k}^c$ with probability of at least $1-\delta$.
\label{thm:samplingubforkcenter}
\end{theorem}

As $\mathrm{OPT}_k^c$ is unknown, we need to find a lower bound of $\mathrm{OPT}_k^c$ to determine the cardinality of $\mathcal{R}$. Recall that we have used a trivial lower bound $k/n$ for $\mathrm{OPT}_k^m$ in the $k$-median problem. However, it is hard to find an ideal lower bound for $\mathrm{OPT}_k^c$. A trivial lower bound for $\mathrm{OPT}_k^c$ is the production of the existence probabilities of all the edges in $E$, but this lower bound could be too small and hence results in a large number of generated random samples. In the sequel we will provides more efficient algorithm for $k$-Center.

\begin{algorithm} [t]
   \KwIn{$(1-\epsilon)(1+\epsilon_3)=(1-\epsilon_1)(1-\epsilon_2)(1-\epsilon_3)$
		$[q_1,q_2]\leftarrow [0,1]; C^*\leftarrow \emptyset; \mathcal{R}\leftarrow \emptyset;i\gets 0$ \label{ln:setab}\\
		\Repeat{$q_1\geq (1-\epsilon_2)q_2$}
		{
            $i\gets i+1;~q\leftarrow \frac{q_1+q_2}{2};~\delta\gets \frac{6\delta}{\pi^2 i^2}$\\
			$\ell\leftarrow \lceil\frac{2(1+\epsilon_3)}{3\epsilon_3^2 (1-\epsilon)q}\ln\frac{n^2+n-2k}{2\delta}\rceil$;\\
            \If{$|\mathcal{R}|<\ell$}{
                    Add more random samples into $\mathcal{R}$ until $|\mathcal{R}|=\ell$\\

            }
			$q'\leftarrow (1-\epsilon_3)q;~~(u,W)\leftarrow \mathsf{GetFirstNode\_1}(q',\mathcal{R})$\\
            $C\leftarrow \{u\};~~\eta\leftarrow \mathit{UB}(u);$\\%~~g(\cdot)\gets \wht{L}_{\mathcal{R}}(q,\cdot);$\\
            \While{$\wht{L}_{\mathcal{R}}(q',C)<nq'-\epsilon_1 q'\wedge |C|<\lceil\ln\frac{n}{\epsilon_1 } \rceil k$}
                {
                    $( u,W)\leftarrow \mathsf{GetNextNode}(W,\wht{L}_{\mathcal{R}}(q',\cdot),C)$;\\
                    $C\leftarrow C\cup \{u\}$
                }

			\eIf{$|C| \leq \lceil\ln\frac{n}{\epsilon_1 } \rceil k\wedge \wht{L}_{\mathcal{R}}(q',C)\geq nq'-\epsilon_1 q'$ \label{ln:judgeca}}
			{
				$C^*\leftarrow C;~~ q_1 \leftarrow q;~~B^*\gets D(\mathcal{R},C^*)$ \label{ln:setS}
			}
			{
				$q_2 \leftarrow q$ \label{ln:setb}
			}

		}\label{ln:repeatends}
  \Return{$(C^*,B^*)$}
    \caption{$\mathsf{SearchKC+}(\epsilon_1,\epsilon_2,\epsilon_3,\epsilon,\delta)$}
    \label{alg:samplingbisearch}
  \end{algorithm}

\begin{algorithm} [ht!]
    Compute the node list $W$ and the values of $\forall v\in V: \mathit{UB}(v)$ using Lines 1-3 of $\mathsf{GetFirstNode}(\mathcal{R})$\\
    $(u,W)\leftarrow \mathsf{GetNextNode}(W,\wht{L}_{\mathcal{R}}(q,\cdot),\emptyset)$\\
    \Return{$(u,W)$}
    \caption{$\mathsf{GetFirstNode\_1}(q,\mathcal{R})$}
    \label{alg:bisearch}
\end{algorithm}

We first study whether we can apply the OPIM framework~\cite{Tang2018} to accelerate our algorithm.
For any $B\in \mathcal{S}_k^G$, any $C\subseteq V$ and any $v\in V$, we define
\begin{eqnarray}
&&{\wht{\mathit{KC}}}({\mathcal{R}},B)={\min\nolimits_{(u,v)\in B}\wht{\mathrm{Pr}}[{\mathcal{R}}, u\sim v]}\nonumber
\end{eqnarray}
Let $(u^o,v^o)$ denote a cluster link in $B^o$ such that $\wht{\Pr}[\mathcal{R}, u^o\sim v^o]= {\wht{\mathit{KC}}}({\mathcal{R}},B^o)$.
The OPIM framework requires that we can find an upper bound of $\wht{\Pr}[\mathcal{R}, u^o\sim v^o]$ using $B^*$, under the purpose that we can get an upper bound of $\mathrm{OPT}_k^c$. This idea, however, cannot be applied to the $k$-center problem. To explain, note that $\wht{\mathrm{Pr}}[\mathcal{R},u^o\sim v^o]$ could be larger than $\wht{KC}(\mathcal{R},{B}^o)$, while we can only guarantee that $\wht{KC}(\mathcal{R},{B}^o)$ is no more than $\wht{\mathrm{Pr}}[\mathcal{R},u\sim v]$ for all $(u,v)\in B^*$. Therefore, it is possible that $\wht{\mathrm{Pr}}[\mathcal{R},u^o\sim v^o]$ is larger than the estimated probability of any cluster link in $B^*$. Therefore, the OPIM framework cannot be applied to the $k$-center problem.

Based on the above observation, we propose a method to judge whether $q\geq \mathrm{OPT}_k^c$ using a relatively small number of random samples. For any $q\in (0,1]$ and any $C\subseteq V$, we define
\begin{eqnarray}
\wht{L}_{\mathcal{R}}(q,C)=\sum\nolimits_{v\in V}\min\{q,\wht{f}_v(\mathcal{R},C)\}
\end{eqnarray}
and we prove the following lemma:

\begin{lemma}
Let $q, \delta$ be any numbers in $(0,1)$ and $\mathcal{R}$ be any set of weakly dependant random samples of $G$. If $\mathrm{OPT}_k^c>q$ and  $|\mathcal{R}|\geq \frac{2(1+\epsilon_3)}{3\epsilon_3^2 q}\ln\frac{n-k}{\delta}$, then we must have $$\Pr[\wht{L}_{\mathcal{R}}(q,C)\geq (n-\epsilon_1)(1-\epsilon_3)q]\geq 1-\delta,$$ where $C=\mathsf{Greedy}(\lceil\ln\frac{n}{\epsilon_1 } \rceil k, \wht{L}_{\mathcal{R}}(q,\cdot))$.
\label{lma:judgegreedyinrandomworld1}
\end{lemma}

Note that we must have $\wht{KC}(\mathcal{R},B^o)\geq (1-\varepsilon_3)\mathrm{OPT}_k^c$ with probability of at least $1-\delta$ when $|\mathcal{R}|\geq \frac{2(1+\epsilon_3)}{3\epsilon_3^2 q}\ln\frac{n-k}{\delta}$. So the proof of Lemma~\ref{lma:judgegreedyinrandomworld1} is similar to that of Lemma~\ref{lma:judgegreedy}.

With Lemma~\ref{lma:judgegreedyinrandomworld1}, we propose a binary searching process similar to that in Algorithm~\ref{alg:bisearch} to find a bi-criteria approximation solution to the $k$-center problem, as shown by the $\mathsf{SearchKC+}$ algorithm.

Similar to the $\mathsf{SearchKC}$ algorithm, the $\mathsf{SearchKC+}$ algorithm also maintains a searching interval $[q_1,q_2]$ and halves this interval in each iteration. The main difference between $\mathsf{SearchKC}$ and $\mathsf{SearchKC+}$ is that we have replaced the function ${L}(q,\cdot)$ by $\wht{L}_{\mathcal{R}}(q,\cdot)$ and used Lemma~\ref{lma:judgegreedyinrandomworld1} to guide the direction of the binary searching process. More specifically, in each iteration $i$, we set $q=\frac{q_1+q_2}{2}$, and generate a set $\mathcal{R}$ of $\frac{2(1+\epsilon_3)}{3\epsilon_3^2 q}\ln\frac{n-k}{\delta}$ random samples. Then we greedily select at most $\ln$ nodes into $C$. If $\wht{L}_{\mathcal{R}}(q,C)\geq (n-\epsilon_1)(1-\epsilon_3)q$, then we can judge that $\mathrm{OPT}_k^c>q$, and the probability that such a judgement is wrong is no more than $\frac{6\delta}{\pi^2 i^2}$ due to Lemma~\ref{lma:concentrationbound}. By the union bound, the probability that we have searched the wrong direction is no more than $\sum_{i=1}^\infty \frac{6\delta}{\pi^2 i^2} =\delta$. If we never search the wrong direction, then we use similar reasoning with that in Sec.~\ref{sec:bisearchwithoracle} to know that we have got a good approximation solution. More specifically, we can prove:

\begin{theorem}
For any $\epsilon, \epsilon_1,\epsilon_2, \epsilon_3\in (0,1)$ satisfying $1-\epsilon=(1-\epsilon_1)(1-\epsilon_2)(1-\epsilon_3)$, the $\mathsf{SearchKC+}$ algorithm can find a solution that achieves $(1-\epsilon){\mathrm{OPT}}_k^c$ with probability of at least $1-\delta$, using at most $\left\lceil \ln\frac{n}{\epsilon_1}\right\rceil k$ centers. This algorithm has no more than $\lceil \log_2 \frac{1}{\epsilon_2\cdot {\mathrm{OPT}}_k^c} \rceil$ iterations.
\end{theorem}

Similar to the $\mathsf{SearchKM+}$ algorithm, $\mathsf{SearchKC+}$ also leverages the CELF framework to reduce the number of evaluating $\wht{L}_{\mathcal{R}}(q,\cdot)$. However, it uses a different procedure (i.e., the $\mathsf{GetFirstNode\_1}$ algorithm) to address the ``cold start'' problem.

Finally, we ask the question whether the $\mathsf{SearchKC+}$ could generate ``too many'' random samples, compared with the upper bound proposed in Theorem~\ref{thm:samplingubforkcenter}. To answer this question, we prove the following theorem:

\begin{theorem}
The expected number of random samples generated in the $\mathsf{SearchKC+}$ algorithm is at most $\mathcal{O}\left(\frac{1}{\epsilon^2 \mathrm{OPT}_k^c}\left(\ln \frac{n}{\delta}+\ln\ln \frac{1}{\epsilon\mathrm{OPT}_k^c}\right)\right)$
\label{thm:expectednumberofsamples}
\end{theorem}

Note that the bound shown in Theorem~\ref{thm:expectednumberofsamples} is very close to that shown in Theorem~\ref{thm:samplingubforkcenter}, and it has only introduced an additional $\ln\ln \frac{1}{\epsilon\mathrm{OPT}_k^c}$ factor. This demonstrates that the $\mathsf{SearchKC+}$ algorithm would not generate a lot of unnecessary random samples.

\section{Conclusion}

We have studied the $k$-median and $k$-center problems in uncertain graphs. We have analyzed the complexity of these problems and proposed efficient algorithms with improved approximation ratios compared with the prior art.

\section{Missing Lemmas} \label{sec:append}

\begin{lemma}
Given any set $A\subseteq V\times V$, any set $\mathcal{R}$ of weakly-dependant random samples of $G$ and any positive number $\varepsilon$, we have
    \begin{eqnarray}
    &&\mathrm{Pr}\left[\wht{\Upsilon}(A)-\Upsilon(A)\geq\varepsilon\right]\leq\exp\left\{-\frac{3\varepsilon^2|\mathcal{R}|}{2(\varepsilon+\Upsilon(A))}\right\} \nonumber
    \end{eqnarray}
where $\Upsilon(A)={\sum_{(u,v)\in A}{\Pr}[u\sim v]}/{|A|}$ and $\wht{\Upsilon}(A)=\sum_{(u,v)\in A}$ $\wht{\Pr}[\mathcal{R},u\sim v]/{|A|}$
\label{lma:concentrationbound}
\end{lemma}

\section{Missing Proofs}

\subsection{Proof of Theorem~\ref{thm:submodularitythm}}
\begin{proof}
For any $X\subseteq Y\subseteq V$ and any $x\in V\backslash Y$, we have
\begin{eqnarray}
&&f_v(X)=\max\{\mathrm{Pr}[u\sim v]\mid u\in X\}\nonumber\\
&\leq& \max\{\mathrm{Pr}[u\sim v]\mid u\in Y\}=f_v(Y)
\end{eqnarray}
So $f_v(\cdot)$ is monotone. Note that $$f_v(X\cup \{x\})=\max\{\mathrm{Pr}[x\sim v], f_v(X)\}$$ So we have:

1) if $\mathrm{Pr}[x\sim v]\geq f_v(Y)=\max\{\mathrm{Pr}[u\sim v]\mid u\in Y\}$, then we also have $\mathrm{Pr}[x\sim v]\geq f_v(X)$, so
\begin{eqnarray}
&&f_v(X\cup \{x\})-f_v(X)\nonumber\\
&=& \mathrm{Pr}[x\sim v]-f_v(X) \nonumber\\
&\geq& \mathrm{Pr}[x\sim v]-f_v(Y) \nonumber\\
&=& f_v(Y\cup \{x\})-f_v(Y)
\end{eqnarray}

2) if $\mathrm{Pr}[x\sim v]< f_v(Y)=\max\{\mathrm{Pr}[u\sim v]\mid u\in Y\}$, then we have $f_v(Y\cup \{x\})=f_v(Y)$, so we also have
\begin{eqnarray}
f_v(X\cup \{x\})-f_v(X)\geq 0= f_v(Y\cup \{x\})-f_v(Y)
\end{eqnarray}
\end{proof}

\subsection{Proof of Theorem~\ref{thm:samplingubforkmedian}}
\begin{proof}

Let $\mathcal{S}_{\mathcal{R}}=\{{D}(\mathcal{R},C)||C|=k\wedge C\subseteq V\}$. Then we must have $|\mathcal{S}_\mathcal{R}|\leq {n\choose k}$. Let $\wht{A}^o$ denote the signature in $\mathcal{S}_{\mathcal{R}}$ such that $\wht{KM}(\mathcal{R},\wht{A}^o)$ is maximized. Let  $A^o$ denote the signature of an optimal clustering of the k-median problem. Note that $A^o$ is not necessarily in $\mathcal{S}_{\mathcal{R}}$, but there must exist certain $A'\in \mathcal{S}_{\mathcal{R}}$ such that $\wht{\mathit{KM}}(\mathcal{R},A')\geq \wht{\mathit{KM}}(\mathcal{R},A^o)$. Therefore, we must have:
\begin{eqnarray}
\wht{KM}(\mathcal{R},A^*)\geq (1-1/e)\wht{KM}(\mathcal{R},\wht{A}^o)\geq (1-1/e)\wht{\mathit{KM}}(\mathcal{R},A^o) \nonumber
\end{eqnarray}

With the above equation, we can ensure that $A^*$ has a $1-1/e-\epsilon$ approximation ratio by adopting the following sampling method: we generate sufficient random samples in $\mathcal{R}$ such that $\wht{\mathit{KM}}(\mathcal{R},A)$ is an estimation of $\mathit{KM}(A)$ within an absolute error of $\beta=\frac{e}{2e-1}\cdot \epsilon\mathrm{OPT}_{km}$ for any $A\in \mathcal{S}_{\mathcal{R}}\cup\{A^o\}$. More specifically, when $|\mathcal{R}|\geq \frac{2(2e-1)(e\epsilon+2e-1)}{3e^2\epsilon^2\mathrm{OPT}_{km}}\ln\frac{{n\choose k}+1}{\delta}$, we must have
\begin{eqnarray}
&&\mathrm{Pr} \left[ \exists A\in \mathcal{S}_{\mathcal{R}}: \mathit{KM}(A)< \wht{KM}(\mathcal{R},A)-\beta\right] \nonumber\\
&\leq& \sum_{A\in \mathcal{A}_{\mathcal{R}}} \mathrm{Pr}[\mathit{KM}(A)< \wht{KM}(\mathcal{R},A)-\beta]\nonumber\\
&\leq& \frac{{n\choose k}\delta}{{n\choose k}+1}
\end{eqnarray}
and
\begin{eqnarray}
\mathrm{Pr} \left[ \wht{\mathit{KM}}(\mathcal{R},A^o)<\mathit{KM}(A^o)-\beta \right]\leq \frac{\delta}{{n\choose k}+1}
\end{eqnarray}
Moreover, as $A^*\in \mathcal{A}_{\mathcal{R}}$, we can use the union bound to get that, with probability of at least $1-\delta$, we have:
\begin{eqnarray}
\mathit{KM}(A^*)&\geq& \wht{KM}(\mathcal{R},A^*)-\beta\nonumber\\
&\geq& (1-1/e)\wht{\mathit{KM}}(\mathcal{R},A^o)-\beta\nonumber\\
&\geq& (1-1/e)\left({{KM}}(A^o)-\beta\right)-\beta\nonumber\\
&=& (1-1/e-\epsilon)\mathrm{OPT}_{k}^m\nonumber
\end{eqnarray}
Hence, the lemma follows.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:inapprofkcenter}}
\begin{proof}
Again, we prove the theorem by a reduction from the NP-hard dominating set problem. Given an instance $G=(V,E)$ of the dominating set problem where $|V|=n$, we can construct an uncertain graph by setting $p(e)=q=\frac{\alpha}{2(1+\alpha)n}$ for all $e\in E$. Suppose that there exists a polynomial-time algorithm that can find $B\in \mathcal{S}_k^G$ such that $\mathit{KC}(B)\geq \alpha \mathit{KC}(\tilde{B})$, where $\tilde{B}$ is an optimal solution to the $k$-center problem in the uncertain $G$ constructed above. We will prove that: there exists a dominating set $S$ in $G$ with $|S|=k$ if and only if $\mathit{KC}(B)\geq \alpha q$. Indeed, if such a dominating set $S$ exists, then we must have $\mathit{KC}(\tilde{B})\geq q$ and hence $\mathit{KC}(B)\geq \alpha q$. Conversely, if there does not exist such a dominating set $S$, then there must exist a cluster link $(u,v)$ in $B$ such that $u\neq v$ and $u$ is not adjacent to $v$. Thus, we can use similar reasoning as that in Theorem~\ref{thm:hardnesskmedian} to prove that
\begin{eqnarray}
\mathit{KC}(B)\leq \mathrm{\mathrm{Pr}}[u\sim v]\leq \frac{nq^2}{1-nq}<\alpha q
\end{eqnarray}
The above reasoning implies that, if there exists a polynomial-time algorithm to the $k$-center problem with any approximation ratio $\alpha$, then the dominating set can also be optimally solved in polynomial time. Hence, the theorem follows.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:kcboundedbylnn}}
\begin{proof}
Given any graph $G=(V,E)$ with $|V|=n$, we can construct an uncertain graph by setting $p(e)=q=\frac{1}{3n}$. Under this setting, we can use similar reasoning with that in Theorem~\ref{thm:inapprofkcenter} to prove that: for any clustering $B$ of $G$, the set of center nodes in $B$ is a dominating set of $G$ if and only if $\mathit{KC}(B)\geq q$.

Suppose that the cardinality of the minimum dominating set in $G$ is $k^*$ ($k^*$ is unknown), and suppose by contradiction that there exists a bi-criteria approximation algorithm $\mathcal{A}$ that achieves the properties described by the theorem. Then we can find a dominating set of $G$ as follows. We run $\mathcal{A}$ for all $k\in [n]$. Let $C_k$ denote the set of center nodes returned by $\mathcal{A}$ for any $k\in [n]$. We then return the set $C\in \{C_1,\cdots, C_n\}$ such that $C$ is a dominating set of $G$ and $|C|$ is minimized.

Note that $\mathrm{OPT}_{k^*}^c\geq q$ in such a case. So $C_{k^*}$ must be a dominating set of $G$ according to the above reasoning. Moreover, we have $|C_{k^*}|< k^*\ln n$ and hence $|C|< k^*\ln n$. This implies that we have built a polynomial-time dominating set algorithm with an approximation ratio less than $\ln n$. However, it is proved in~\cite{feige1998threshold} that such a dominating set algorithm should not exist unless P=NP. Therefore, we got a contradiction, which proves the theorem.
\end{proof}

\subsection{Proof of Lemma~\ref{lma:judgegreedy}}
\begin{proof}
Consider the following optimization problem:
    \begin{eqnarray}
        \mathbf{Minimize}&&~~|C| \qquad\qquad\qquad\qquad \mathbf{[KCT\_COVER]}\nonumber\\
        \mathbf{s.t.}&&~~L(q,C)\geq nq;~~C\subseteq V \label{eqn:robustIEOconstraint}
    \end{eqnarray}
Note that $L(q,\cdot)$ is a monotone and submodular function and $L(q,V)=nq$. So this problem is actually a ``submodular set cover'' problem. Suppose that an optimal solution to [KCT\_COVER] is $C^o_{cover}$. We can use a greedy algorithm~\cite{Goyal2013} to find $C'$ such that
\begin{eqnarray}
&&|C'|\leq \left\lceil \ln\frac{n}{\epsilon_1}\right\rceil |{C}^o_{cover}|;~~L(q,C')\geq nq-\epsilon_1 q
\end{eqnarray}
Now suppose by contradiction that $\mathrm{OPT}_k^c> q$, then we must have
\begin{eqnarray}
\min\nolimits_{v\in V} f_v(C^o_{kc})=\mathrm{OPT}_k^c >q,
\end{eqnarray}
where $C^o_{kc}$ denote the set of centering nodes in $A^o$. So we have
\begin{eqnarray}
L(q,C^o_{kc})= \sum\nolimits_{v\in V}\min\{q,f_v(C^o_{kc})\}=qn
\end{eqnarray}
This implies that $C^o_{kc}$ is a feasible solution to [KCT\_COVER]. Therefore, we must have
\begin{eqnarray}
|C'|\leq \left\lceil \ln\frac{n}{\epsilon_1}\right\rceil |{C}^o_{cover}|\leq \left\lceil \ln\frac{n}{\epsilon_1}\right\rceil |{C}^o_{kc}|\leq \left\lceil \ln\frac{n}{\epsilon_1}\right\rceil k \nonumber
\end{eqnarray}
and hence $C'\subseteq C$. This implies $L(q,C)\geq nq-\epsilon_1q$, a contradiction. Hence, the lemma follows.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:samplenum1}}
\begin{proof}
Let $Z=\{(u,v)|u,v\in V\wedge u\neq v\}$. Define the sets $Q_{\mathcal{R}},Q'_{\mathcal{R}}$ and the events $\mathcal{E}_1,\mathcal{E}_2$ as
\begin{eqnarray}
&&Q_{\mathcal{R}}=\{(u,v)|(u,v)\in Z\wedge \Pr[u\sim v]\geq (\mathrm{OPT}_k^c)^2\}\nonumber\\
&&\mathcal{E}_1=\{\forall (u,v)\in Q_{\mathcal{R}}:\wht{\Pr}[\mathcal{R}, u\sim v]\geq (1-\epsilon_1)(\mathrm{OPT}_k^c)^2\}\nonumber\\
&&Q'_{\mathcal{R}}=\{(u,v)|(u,v)\in Z\wedge \Pr[u\sim v]< (1-\epsilon)(\mathrm{OPT}_k^c)^2\}\nonumber\\
&&\mathcal{E}_2=\{\forall (u,v)\in Q'_{\mathcal{R}}:\wht{\Pr}[\mathcal{R}, u\sim v]< (1-\epsilon_1)(\mathrm{OPT}_k^c)^2\}\nonumber
\end{eqnarray}
In the sequel, we will prove that: when $\mathcal{E}_1$ and $\mathcal{E}_2$ both happen, then we must have $\mathit{KC}(B^*)\geq (1-\epsilon)(\mathrm{OPT}_k^c)^2$.

Suppose that the nodes sequentially selected by $\mathsf{SearchKC\_1}$ are $v_1,v_2,\cdots,v_k$. Let $C^*_i=\{v_1,\cdots,v_i\}$. Let $v_{k+1}$ be a node in $V\backslash C^*_k$ such that $\wht{d}(\mathcal{R},v_{k+1},C^*_k)$ is maximized. Let $l_i=\wht{d}(\mathcal{R},v_{i+1},C^*_{i})$. We first prove that $l_k\leq -2\ln \mathit{KC}(B^o)-\ln(1-\epsilon)$. It can be seen that $l_1,l_2,\cdots, l_{k}$ are non-increasing. Suppose by contradiction that $l_k>-2\ln \mathit{KC}(B^o)-\ln(1-\epsilon)$, then there must exist two nodes $v_i$ and $v_j$ in one cluster of $B^o$ such that $\wht{d}({\mathcal{R}},v_i,v_j)\geq -2\ln \mathit{KC}(B^o)-\ln(1-\epsilon)$, which implies that
\begin{eqnarray}
\wht{\Pr}[\mathcal{R},v_i\sim v_j] <(1-\epsilon) (\mathrm{OPT}_k^c)^2
\end{eqnarray}
However, as $v_i$ and $v_j$ is in the same cluster of $B^o$, we must have $\Pr[v_i\sim v_j]\geq (\mathrm{OPT}_k^c)^2$, which contradicts the assumption that the event $\mathcal{E}_1$ happens.

As $l_k\leq -2\ln \mathit{KC}(B^o)-\ln(1-\epsilon)$, we must have
\begin{eqnarray}
\forall (u,v)\in B^*: \wht{\Pr}[\mathcal{R},u\sim v] \geq (1-\epsilon_1) (\mathrm{OPT}_k^c)^2
\end{eqnarray}
As $\mathcal{E}_2$ happens, we must have
\begin{eqnarray}
\mathit{KC}(B^*) \geq (1-\epsilon) (\mathrm{OPT}_k^c)^2
\end{eqnarray}
Now the problem left is to prove that
\begin{eqnarray}
\Pr[\neg \mathcal{E}_1\vee \neg\mathcal{E}_2]\leq \delta
\end{eqnarray}
This can be proved by using the union bound and Lemma~\ref{lma:concentrationbound}. Hence the theorem follows.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:samplingubforkcenter}}
\begin{proof}
Let $(u^*,v^*)$ be the cluster-link in $B^*$ such that ${\mathrm{Pr}}[u\sim v]$ is minimized. Let $(\wht{u},\wht{v})$ be the cluster-link in $B^*$ such that $\wht{\mathrm{Pr}}[\mathcal{R},\wht{u}\sim \wht{v}]$ is minimized. Let $B^o$ be the signature of an optimal $k$-clustering in $G$ such that $\mathit{KC}(B^o)$ is maximized. Let $(\wht{u}',\wht{v}')$ be the cluster-link in $B^o$ such that $\wht{\mathrm{Pr}}[\mathcal{R},\wht{u}'\sim \wht{v}']$ is minimized.  Let $({u}^o,{v}^o)$ be the cluster-link in $B^o$ such that ${\mathrm{Pr}}[{u}^o\sim {v}^o]$ is minimized.  Let $\mathcal{E}_1$ denote the following event:
\begin{eqnarray}
&&\mathcal{E}_1=\{\wht{\mathrm{Pr}}[\mathcal{R},\wht{u}'\sim \wht{v}']\geq (1-\epsilon_3){\mathrm{Pr}}[\wht{u}'\sim \wht{v}']\}~~\label{eqn:uhatisgood}
\end{eqnarray}
If $\mathcal{E}_1$ hold, then we must have
\begin{eqnarray}
&& \wht{\mathrm{Pr}}[\mathcal{R},u^*\sim v^*]\geq \wht{\mathrm{Pr}}[\mathcal{R},\wht{u}\sim \wht{v}] \nonumber\\
&\geq& (1-\epsilon_1)(1-\epsilon_2)\wht{KC}(\mathcal{R},\wht{B}^o) \label{eqn:duetothekcugalg}\\
&\geq& (1-\epsilon_1)(1-\epsilon_2)\wht{KC}(\mathcal{R},{B}^o)\nonumber\\
&=& (1-\epsilon_1)(1-\epsilon_2)\wht{\mathrm{Pr}}[\mathcal{R},\wht{u}'\sim \wht{v}']\nonumber\\
&\geq& (1-\epsilon_1)(1-\epsilon_2)(1-\epsilon_3){\mathrm{Pr}}[\wht{u}'\sim \wht{v}'] \nonumber\\
&\geq& (1-\epsilon_1)(1-\epsilon_2)(1-\epsilon_3){\mathrm{Pr}}[{u}^o\sim {v}^o]   \nonumber\\
&=& (1-\epsilon)(1+\epsilon_3)\mathrm{OPT}_k^c  \nonumber
\end{eqnarray}
where \eqref{eqn:duetothekcugalg} is due to the performance guarantee of $\mathsf{SearchKC}$.

Note that there are at most $n-k$ possible choices for $(\wht{u}',\wht{v}')$. Therefore, when $|\mathcal{R}|\geq \frac{2(1+\epsilon_3)}{3\epsilon_3^2 \mathrm{OPT}_k^c}\ln\frac{n-k}{\delta_1}$, we can get
\begin{eqnarray}
&&\Pr[\neg \mathcal{E}_1]\leq (n-k)\exp\left(-\frac{3\epsilon_3^2\Pr[\wht{u}'\sim \wht{v}']}{2(1+\epsilon_3)}|\mathcal{R}|\right) \nonumber\\
&\leq& \frac{2(n-k)}{n^2+n-2k}\delta,
\end{eqnarray}
where we have used the the union bound and Lemma~\ref{lma:concentrationbound}.

Let $\mathcal{K}=\{(u,v)|u,v\in V\wedge \Pr[u\sim v]<(1-\epsilon)\mathrm{OPT}_k^c\}$. So we have $|\mathcal{K}|\leq {n\choose 2}$. When $|\mathcal{R}|\geq \frac{2(1+\epsilon_3)}{3\epsilon_3^2 (1-\epsilon) \mathrm{OPT}_k^c}\ln\frac{{n\choose 2}}{\delta_2}$, we can use the the union bound and Lemma~\ref{lma:concentrationbound} to get
\begin{eqnarray}
&&\Pr[(u^*,v^*)\in \mathcal{K}\wedge \mathcal{E}_1]\nonumber\\
&\leq& \Pr[\exists (u,v)\in \mathcal{K}: \wht{\mathrm{Pr}}[\mathcal{R},u\sim v]\geq (1-\epsilon)(1+\epsilon_3)\mathrm{OPT}_k^c] \nonumber\\
&\leq& \sum\limits_{(u,v)\in \mathcal{K}} \Pr[\wht{\mathrm{Pr}}[\mathcal{R},u\sim v]\geq \mathrm{Pr}[u\sim v] +\epsilon_3(1-\epsilon)\mathrm{OPT}_k^c]\nonumber\\
&\leq& {n\choose 2}\exp\left(-\frac{3\epsilon_3^2(1-\epsilon)\mathrm{OPT}_k^c}{2(1+\epsilon_3)}|\mathcal{R}|\right)\leq \frac{n(n-1)}{n^2+n-2k}\delta\nonumber
\end{eqnarray}

Combining the above results, we get
\begin{eqnarray}
&&\Pr[\Pr[u^*\sim v^*]<(1-\epsilon)\mathrm{OPT}_k^c] \leq\Pr[(u^*,v^*)\in \mathcal{K}]\nonumber\\
&\leq& \Pr[(u^*,v^*)\in \mathcal{K}\wedge \mathcal{E}_1]+\Pr[\neg\mathcal{E}_1]\nonumber\\
&\leq& \delta_1+\delta_2\leq \delta
\end{eqnarray}
Hence, the theorem follows.
\end{proof}

\subsection{Proof of Lemma~\ref{lma:judgegreedyinrandomworld1}}
\begin{proof}
Let $\wht{B}^o$ denote the $k$-clustering in $G$ such that $\wht{KC}(\mathcal{R},\wht{B}^o)$ is maximized. If $\wht{KC}(\mathcal{R},\wht{B}^o)>(1-\epsilon_3)q$, then we can get $\wht{L}_{\mathcal{R}}(q,C)\geq (n-\epsilon_1)(1-\epsilon_3)q$ by similar reasoning with that in Lemma~\ref{lma:judgegreedy}. Therefore, we ge
\begin{eqnarray}
&&\Pr[\wht{L}_{\mathcal{R}}(q,C)< (n-\epsilon_1)(1-\epsilon_3)q]\nonumber\\
&\leq& \Pr[\wht{KC}(\mathcal{R},\wht{B}^o)\leq (1-\epsilon_3)q] \nonumber\\
&\leq& \Pr[\wht{KC}(\mathcal{R},B^o)\leq (1-\epsilon_3)q] \nonumber\\
&\leq& \Pr[\exists (u,v)\in B^o: \wht{\Pr}[\mathcal{R},u\sim v]\leq (1-\epsilon_3)q] \nonumber\\
&\leq& \sum\nolimits_{(u,v)\in B^o\wedge u\neq v}\Pr[\wht{\Pr}[\mathcal{R},u\sim v]\leq (1-\epsilon_3)q] \nonumber\\
&\leq& (n-k)\exp\left(-\frac{3\epsilon_3^2 \mathrm{OPT}_k^c}{2(1+\epsilon_3)}|\mathcal{R}|\right)\leq \delta \nonumber
\end{eqnarray}
Hence, the lemma follows.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:expectednumberofsamples}}
\begin{proof}
Suppose that $q_{min}$ is the smallest $q$ that is tested by $\mathsf{SearchKC+}$. Then we must have $q_{min}\in \{2^{-j}|j\geq 1\}$. Suppose that $q_{min}=2^{-i_{min}}$. Then the $\mathsf{SearchKC+}$ algorithm takes $i_{min}$ iterations to reduce $q$ from $\frac{1}{2}$ to $q_{min}$, and then takes at most another $i_{min}+\lceil \log_2\frac{1}{\epsilon_2}\rceil$ iterations to end. Note that $i_{min}$ is a random number. When $i_{min}=i$, the total number of generated random samples is no more than
\begin{eqnarray}
\ell(i)= \left\lceil\frac{2^{i+1}(1+\epsilon_3)}{3\epsilon_3^2 (1-\epsilon)}\ln\frac{\pi^2(n^2+n-2k)(2i+\lceil \log_2\frac{1}{\epsilon_2}\rceil)^2}{12\delta}\right\rceil\nonumber
\end{eqnarray}
It can be verified that $\forall i\geq 1: \ell_{i+1}\leq 3\ell_i$. Suppose that $i_0\geq 1$ is the smallest number such that $2^{-i_0}\leq \mathrm{OPT}_k^c$. So we must have $2^{-i_0+1}\geq  \mathrm{OPT}_k^c$. For any $i>i_0$, we have
\begin{eqnarray}
&&\Pr[i_{min}=i]\leq \Pr[|C^*_{i-1}|>\lceil\ln({n}/{\epsilon_1 })\rceil k]\nonumber\\
&\leq& \Pr[\wht{\mathit{KC}}(\mathcal{R}_{i-1},B^o)< (1-\epsilon_3)\mathrm{OPT}_k^c ]\nonumber\\
&\leq& \exp\left(-\frac{3\epsilon_3^2\mathrm{OPT}_k^c}{2(1+\epsilon_3)}|\mathcal{R}_{i-1}|\right)\leq \delta^{\mathrm{OPT}_k^c\cdot 2^{i-1}}
\end{eqnarray}
where $\mathcal{R}_{i-1}$ and $C^*_{i-1}$ denote the set of generated random samples and the set of centering nodes found by $\mathsf{SearchKC+}$ when $q=2^{-i+1}$, respectively.
Let $a=\mathrm{OPT}_k^c\cdot 2^{i_0}$. When $\delta\leq 1/3$,  the total expected number of generated random samples is no more than
\begin{eqnarray}
&&\ell(i_0)+\sum_{i>i_0} \ell(i)\Pr[i_{min}=i]\nonumber\\
&\leq&\ell(i_0)+\sum_{j=0}^\infty 3^{j+1}\ell(i_0)\delta^{2^j a}\leq 2\ell(i_0)+ 3\ell(i_0)\sum_{j=1}^\infty 3^{j-2^j}\nonumber\\
&\leq&2\ell(i_0)+3\ell(i_0)\sum_{j=1}^\infty 3^{-j}\leq 7\ell(i_0)/2 \nonumber
\end{eqnarray}
Note that $i_0=\lceil \log_2\frac{1}{\mathrm{OPT}_k^c}\rceil$, so we have
\begin{eqnarray}
\ell(i_0)=\mathcal{O}\left(\frac{1}{\epsilon^2 \mathrm{OPT}_k^c}\left(\ln \frac{n}{\delta}+\ln\ln \frac{1}{\epsilon\mathrm{OPT}_k^c}\right)\right)
\end{eqnarray}
Hence the theorem follows.
\end{proof}

redpajama_set_name: RedPajamaArXiv


text:
Q: How to evaluate the derivative$\frac{d}{dx}\left(\ln\sqrt{\frac{4+x²}{4-x²}}\right)$? How can I evaluate this derivative?:
$$\frac{d}{dx}\left(\ln\sqrt{\frac{4+x^2}{4-x^2}}\right)$$
Thank you.

A: We'll exploit the properties of logarithms, recalling that $$\ln\left(\frac{a}{b}\right)^b =  b \ln\left(\frac ab\right) = b (\ln a - \ln b)$$

$$\begin{align} {\bf f(x)} & = \ln\sqrt{\frac{4+x^2}{4-x^2}} \\ \\
&= \ln\left(\frac{4+x^2}{4-x^2}\right)^{1/2}\\ \\
& = \frac 12\ln\left(\frac{4 + x^2}{4 - x^2}\right)\tag{$\ln\left(\frac ab\right)^c = c\ln\left(\frac ab\right)$}\\ \\
& = \frac12 \left(\ln(4+x^2) -  \ln(4-x^2)\right)\tag{$\ln\left(\frac ab\right) = \ln a - \ln b$}\\ \\
{\bf f'(x)} & = \frac 12\left( \frac{2x}{4 + x^2} + \frac{2x}{4 - x^2}\right)\tag{chain rule} \\ \\ & = \frac 12\left(\frac{2x[4-x^2 + 4 + x^2]}{16-x^4}\right) \\ \\ & =
\frac{8x}{16 - x^4}\end{align}$$

redpajama_set_name: RedPajamaStackExchange


Sidley United have the chance to lift a first trophy since the club left the County league when they take on Wadhurst United in the final of the Sussex FA Junior Cup at Culver Road, Lancing on Wednesday evening.
The Blues have won both league matches against Wadhurst United this season by a 2 - 1 scoreline and with our opponents showing recent improved league form, Sidley will need to be fully concentrated for the 90 minutes if they are to lift the cup.
First Round: A bye as opponents Stedham United could not raise a side.
Second Round: A 3 - 2 win away at ESFL Division Two side Catsfield.
Third Round: A 5 - 3 victory at home to East Dean I.
Quarter Final: A 4 - 3 away win after extra time to Montpelier Villa II.
Semi Final: An impressive 2 - 1 win over ESFL Division One rivals Crowhurst.
First Round: A comfortable 3 - 0 win away to Partridge Green.
Second Round: A bye as AFC Hastings could not raise a side.
Third Round: A 4 - 0 win over league rivals Ticehurst in a game switched to Sidley's home pitch.
Quarter Final: A come from behind 3 - 1 win at Midway 1948 FC of the Brighton and District League Division One East.
Semi Final: A convincing 4 - 1 win over a youthful Woodingdean Wanderers from the same league as Midway although Sidley finished with 9 men.
Sidley will be without striker Lee Roberts who is away and long term injury victim James Godden. Captain Mark Funnell returns from suspension and the Blues are otherwise at full strength. The Blues will hope to reap the benefits of having had a rest at the weekend.
Wadhurst had a tough game against The J.C. Tackleway and although they led 2 - 1 in the end they had to settle for a 3 - 3 draw. Their top scorer is Ryan Bateman with 4 league goals to his name.
The game kicks off at 7.15pm to allow for the possibility of extra time / penalties. Sidley United are running a coach to the game, leaving at 4.30pm and anyone interested in booking a place should contact Dickie Day on 07487694888.
Sidley United FC will be grateful for all the support of fans who can attend the match.


I am stopping the timeline because I am going to crest wolf lodge. We just got in the car and I am going to write this post in updates. Sorry I didn't tell you. I am watching Star Wars VI. I feel sick so I am going to end this part here.
I am so bored. I have had nothing to do and I have ANOTHER stuffy nose. FUN FACT: 1/8th of my ENTIRE LIFE I have had a stuffy nose. I honestly am going to grow up and spend my whole life finding a cure to stuffy noses. I am surrounded by chips because my siblings treat me like a trash can.
I think that stuffy noses are the reason of WWI and WWII. We are only half way there and the terrain looks exactly the same as it did at 4:13. I swear, all I can do right now is eat or sleep. I want to teleport strait to the room and cut off my nose and glue on a better one. Then I will go down every water slide, and do every magic quest instead of sitting in a sickening car. See you at around 6 o'clock.
I saw Great Wolf Lodge out my window and we still have half an hour! Why couldn't they just build a road over there to save half an hour! At least the terrain changed. And I just saw it again! I guess I will see you… wait we're here? Already? Oh whell, I'm here, and there is no downside to video games!


What an end to the year! And what a yera it's been! The DOR are all set for 2015 to begin with a HUGE bang! But, today, the final day of 2014, summons a wrap up from Vice's Kaleidoscope Radio Show, which has featured interviews with the like of TY, The Mouse Outfit, Dr Syntax, Ewan Hoozami and of course Donnie Numeric! ….
"Kaleidoscope Radio is now a monthly online show (formerly on Passion Radio Bristol from 4-6pm each Saturday). It features an eclectic mix of Hip Hop, Soul, Funk and lots of other good stuff! Tune in and get involved!!!
Stresses & Definitions (Mr Kwazi Remix) f. Seraphym & Joe Bird played on Bread & Butta (New Zealand)!
Big shouts to Bread & Butta in New Zealand on Base FM for playing the Mr Kwazi Remix of Stresses & Definitions! Always great stumbling on amazing shows like this!
Bread & Butta is part of the incredible Fry Bread Radio, a serious force to be reckoned with. Be sure to check out the show featurng Stresses & Definitions and explore their vast collection of support and international repuation. It's humbling to be part of such an established show.
Tonight from 10pm, Vice will be on the Bobby Tempo Show, offering a 30 minute guest mix, with a range of Hip Hop, Soul, Jazz and more, including a station exclusive of The Delegates Of Rhyme forthcoming single entitled "Stresses And Definitions".
Be sure to tune in to XL FM tonight to check out one of the most eclectic shows on the radio.
MAAAAAANNNN!!! We are seriously excited to announce that the king of UK Hip Hop, The Head Honcho Of Suspect Packages, and all round Mr.Nice guy the man like DIsorda played "Shadows" on Suspect Packages Show, The Boombap Festival Special!!! Mad love to Disorda, and look out for more Delegates joints featured soon.
CHECK THE SUSPECT PACKAGES SHOW HERE!!!


I just love self- guided discoveries. I love to see the joy in the kids faces as they figure something out and hearing them excitedly tell me all about it. Sure, sometimes their discoveries are not really of any interest to me or sometimes their discoveries seem very basic and simple TO ME, but to them it's amazing. They're so proud and so excited that I can't help but share in the joy with them , even if I have to fake it sometimes. This happened over the weekend with Evan. We had gotten in a whole box of gifts and Halloween costumes on Friday. In that box we had bought a light up toy machine gun for Ian as part of his Army guy Halloween costume. In order for it to light up and shake and make noise we had to add batteries. Evan helped me figure out where the batteries go because there were no instructions, so we examined every screw we saw and tried to determine if it would open a small compartment for the batteries. He read the word "shake" off the box (he even read the word while it was upside down) and excitedly told me "This says shake!" (a slight pause) and then.. "shake has a silent E on the end!" He then started playing with the gun and came to show me where all the light bulbs were and how they made each area light up, he showed me the various parts that move and tried to figure out why. To me it was just a toy gun, to him it was a 30 minute dissection of HOW the gun worked and what all the various pieces were made of. I'm not sure what I'd characterize his learning under be it science or problem solving or what not but he was definitely learning and making discoveries.
Over the weekend my boys also all picked their topic for our annual homeschool science fair. I made the conscious decision not to push them to enter this year since they are usually reluctant to do the actual work and a lot of it falls to me. When asked if/ what they wanted to study they all had an answer ready and so I guess we'll be participating in this event again this year. We spent part of our day on Saturday on our library's website requesting books about otters (both river and sea), sea turtles, and density. We then spent some time on Pinterest and talking and brainstorming to come up with some fun themed snack ideas and possible hands on projects/ activities. The boys all decided on a snack idea already and we're still working on some hands- on crafts/ activity ideas but I like knowing we have a lot of time still to work with. Knowing they get to learn about learn something that interests them is always a great motivator.
We try to rely on self- guided discoveries or self- guided learning as much as possible. I know that learning is most memorable when it's of particular interest and is relevant to the person learning. I feel that there's no point in teaching something they aren't going to remember later anyway. I try as much as possible to let them lead. I like to sit back, observe and tie what they are doing into learning & school work. It's not always possible since I do fear that there are some subjects that are just to important to ignore but I do try to let them lead. Other days, like today I put them fully in charge. I told them to grab something school-like to work on in the car as we ran errands and went to Karate. Ian chose to bring his extreme dot to dot books and work on some math/ problem solving while Alec and Evan devised a way for them to play Hangman on the Kindle (I say devised since Evan still can't really spell yet). They brought a Pokémon book in the car and Evan was allowed to look up names and spelling when inputting a puzzle for Alec to guess and he used the book to help him try and guess the words Alec made up for him.
Karate went really well today and I saw both Alec and Evan just beaming with pride when they were complimented on their kicks and rolls. Several times I heard their teacher say "Yes! That's it! You've got it." It's just the kind of positive reinforcement they needed to hear. After only a month or so of classes I have seen a huge turnaround in the kids' attitude toward this new karate class. They are really enjoying the class, the kids, and even their teachers. They've picking up new skills and had so much fun giggling and laughing while trying to learn their forward rolls today. No one is threatening to quit anymore and I'm so happy that they're happy!
For reading we listened to both our book on CD in the car and to Harry Potter during lunch. Alec started reading to us all while I made their lunches and then I took over as we settled in to eat. I used to force the boys to read during the day too but I found they often set the timer and watched that more than they read. Left on their own they tend to read when the mood strikes. The boys have really taken to reading at night in their beds. I have found Evan looking at books after we say goodnight too and last week he tried really hard to read a new book to himself. He told me the next morning that he hadn't been able to read it on his own but I was proud of him for trying. He will re-read books we've read together in school and look through the pictures of other books and I know this love of books and reading is more important at this stage than the actual reading. Over time his skills will grow and develop and he'll never learn to hate reading since he's not being pushed or feeling frustrated with it all. Ian, who still says he doesn't like to read, actually read three books on his own in bed last night after I had sat with him and we had read a story together. He picked out a HUGE stack of books at the library yesterday and I was really impressed to see him branching out reading different books-- good thing too since he's read every single truck, fishing, and equipment book we could find (even through interlibrary loan!). Hopefully, he'll discover something else that he likes to read in trying a variety of new books. Alec often falls asleep with a book open on his chest and his light on. He is my biggest bookworm and reminds me so much of myself. I love to read and often have multiple books going at once. I too will fall asleep with my book open and pick up reading where I left off as soon as I wake up in the morning.
It was a nice, albeit, windy day and the boys just wanted to play outside. As soon as we got home from karate they changed and headed outside. I felt a bit guilty letting our schoolwork slide but I know the weather will be changing soon and it's nice for them to soak up the fresh air and sunshine. They only came in long enough to eat lunch and then they were right back outside playing. They were all working together to build in the sand and then I heard my younger two playing Percy Jackson. They went up into the woods and took a pen (Percy's sword), a protein bar (ambrosia) and Evan's sword with them on their quest. I just love that they enjoy acting out books through their play just as much as they enjoy acting out movies and TV shows. That's when I know that they love what we're reading.
Ian spent a part of his day watching his new Mighty Machine videos. He was so excited that they finally came in and reminded me that it's a documentary on machines and trucks so it was educational. I certainly couldn't argue with that logic! While he was busy watching TV, Evan and I played Jenga together. As the other boys heard our fun they came into the room and wanted to play too. We spent our afternoon playing games. We played Jenga until Evan lost interest and both him and Ian wanted to use the blocks to build. Alec and I then played a good 3 rounds or so of Zeus on the Loose. He just loves this game to much and I love all the math involved in playing! We ended our afternoon with Alec, Ian and myself playing 8 or so rounds of pitch. They're still learning the ins and outs of the game but they're catching on fast. Ian won our game and they both can count for game already too. It was lots of fun!


Decor is only as complex while you allow it get. In case you are willing to find out and take time to permit new concepts sink in, you may easily view your achievement. The tips within the write-up over have been all well tested by many people prior to, and may effortlessly function in your favour also.
Article with Tag best window treatments for sliding glass doors from Window Covering Ideas For Glass Front Doors , Bring it along when buying drapes or any other decorating components looks via from: revistaalmazara.com.
Curtains For Front Door Windows Curtains For Small Windows Beside from Window Covering Ideas For Glass Front Doors , Take it along with you when looking for curtains or another decorating materials impression sourced from: tushargupta.me.
» Try to use functional furnishings when beautifying a smaller measured area. An ottoman is an excellent option. You can use it for sitting or even a kitchen table, and you may even store things inside of, if this opens up. Items that have multiple uses are effective room savers for the smaller space.
Front Door Side Window Curtains Curtain Front Door Side Window Side from Window Covering Ideas For Glass Front Doors , Take it with you when looking for curtains or some other redecorating resources looks sourced from: casualshoes.club.
Front Door Side Window Curtains Curtain Front Door Side Window Side from Window Covering Ideas For Glass Front Doors , Bring it along when buying curtains or other beautifying supplies impression sourced from: casualshoes.club.
Front Door Side Window Curtains Curtain Front Door Side Window Side from Window Covering Ideas For Glass Front Doors , Take it together with you when looking for drapes or any other redecorating supplies screenshot received from: casualshoes.club.
Need a little privacy for your front door sidelight windows We can from Window Covering Ideas For Glass Front Doors , Take it along when shopping for drapes or any other decorating materials picture via from: pinterest.com.
» Lighting fixtures are an excellent addition to any property as these might be contained in the living room or correct with you in the bedroom. Furthermore these devices offer you additional gentle to learn and publish, but they will give your home a conventional look and match a number of variations.
Trim for Front Doors More Eye Catching Illustrative Type from Window Covering Ideas For Glass Front Doors , Take it with you when buying window curtains or another decorating supplies screenshot received from: illustrativetype.com.
What colour should you paint your front door Good Housekeeping from Window Covering Ideas For Glass Front Doors , Bring it along with you when shopping for window curtains or other redecorating supplies screenshot via from: goodhousekeeping.co.uk.
Modern Home Design Ideas PapihillsTour from Window Covering Ideas For Glass Front Doors , Bring it together with you when shopping for window curtains or other decorating resources impression downloaded from: papihillstour.com.
Swinging French Patio Doors Reviews Illustrative Type from Window Covering Ideas For Glass Front Doors , Take it together with you when buying drapes or another decorating components image downloaded from: illustrativetype.com.
Furniture Black Wooden Door With Glass Panel Using Silver from Window Covering Ideas For Glass Front Doors , Bring it along with you when looking for window curtains or some other decorating supplies screenshot downloaded from: mirzaint.com.
25 Wonderful Cheap Ideas for Furniture Decoration and Revamps from Window Covering Ideas For Glass Front Doors , Bring it along when buying window curtains or another beautifying components picture received from: pinterest.com.
Front Door Side Window Curtains Curtain Front Door Side Window Side from Window Covering Ideas For Glass Front Doors , Bring it along with you when looking for drapes or other beautifying resources impression received from: casualshoes.club.


Including New PDF - Bob Bryla, 0072231459 Expert Oracle 9I Oracle 10G DBA . Get the right Oracle goldengate dba job with company ratings & salaries. Oct 1, 2012 - 3 min - Uploaded by oraclegoldengateAn introductory lab on how to configure Oracle GoldenGate for data replication. 61 Oracle Golden Gate Jobs available in Bangalore, Karnataka on Pipeline " Oracle DBA" referral requisition – Bangalore Expert in database performance analysis and tuning Expert in oracle upgrades and migrations. Oracle GoldenGate in Bangalore - Find reviews, addresses, contact details, phone number for Oracle Oracle GoldenGate, Oracle 10g DBA and more. Oracle GoldenGate: A Real-time Data integration & Heterogeneous replication tool. Find your next Charlotte, NC oracle goldengate dba job and jump-start your career E*pro. Oracle GoldenGate 11g Handbook - Kindle edition by Robert Freeman. This post concludes a short series on how a hard-core Oracle guy In Part 1 and Part 2, I covered the industry changes I've witnessed as an Oracle DBA and how and worked with the guys at GoldenGate before Oracle bought them. Oct 22, 2013 - 31 min - Uploaded by Wysheid WysheidThis video explains about the steps for Installing GoldenGate for Oracle Database. Concerned except for, perhaps, finding an experienced pro to sign on. To working here as long as one is diligent, fully focused, pro-active and sincere.". Each Oracle GoldenGate instance has a dedicated manager process. The Oracle GoldenGate manager process on MS-SQL Server runs as a reference for use by our DBA performance tuning consulting professionals. Oracle database administrator with over 12 years expirience; management of Oracle RAC, Oracle Dataguard AIX and Oracle Goldengate; ORACLE PRO.


We had this incredibly cute, gentle and funny maternity session last spring! It was quite rainy and we hid in one of the tropical houses in Geneva Botanical Garden. This was such a perfect atmosphere – rain outside, almost no visitors and us surrounded by exotic plants from far away.
For me taking pictures of couples awaiting their first child is very special. I get a chance capture the last moments of the couple's relationship which is about to turn into something new. The love which is about to became MORE and different, VERY different! I am incredibly thankful that you let me see this, capture this, that you share your love and your hope with me.
And thank you so much for these kind words!
Would You Like To Have a Session in Botanical Garden?


Also called FSW Funding, Factors Southwest specialized in providing alternative small business financing to startups that would otherwise have a difficult time obtaining funding from traditional banking sources. More than business loans, Factors Southwest offers invoice factoring and accounts receivables financing to small businesses in wholesaling and distribution, manufacturing, aerospace and defense, staffing and other services. With no financing amount being too small, Factors Southwest even offers microfinancing to those companies in the nascent startup stage.


A man was wounded and a woman was injured in a shooting in the West Pullman neighborhood on the Far South Side Friday afternoon.
Both were in a vehicle at 4:34 p.m. in the 12200 block of South Wallace when someone began shooting at them, according to Chicago Police.
The man, 35, was shot in the forehead and the woman, 37, was injured by shattered glass, police said. They took themselves to MetroSouth Medical Center in Blue Island, where the woman was treated for her injuries.
The man was transferred to Stroger Hospital where his condition was stabilized, police said.


The 5 People You'll Meet at a Frat Party | Let's win college.
Oh, freshmen year. That glorious time when going out every weekend (every night of every weekend, sometimes!) is still a novelty, and fraternities are still these mystical places of friends, fun, and free booze. Speaking as a highly experienced sophomore, I can tell you that while the novelty does wear off for everyone, for some people the allure is still there even as upperclassmen. So what is a frat party, exactly? And, more importantly, what kind of people go to such events? Someone once said (Shakespeare? Alexander the Great? Tywin Lannister?) that knowledge is power, and so it is. Armed with the knowledge of what to expect and who to avoid, you'll be that much more successful in your quest to have a great time out with friends.
Now, we all know generalizations are horrible, inaccurate things, and that stereotyping is of course very much frowned upon, but sometimes they're just plain useful! And this is one of those times, so I now present to you a highly oversimplified (and therefore very useful) list of the 5 people you'll meet at a frat party.
1. The Freshman. Now, dear frosh, you and I both know that this is your first year at college, but you don't need to telegraph that to the whole room. Freshmen generally identify themselves by either standing awkwardly in large groups, or consuming way too much alcohol and puking in the corner. From the hammered girl dancing on top of the beer pong table to the boy doing keg stand after keg stand on an empty stomach, you don't want to be this person. Blend in at frat parties by watching your alcohol consumption (or put water in your cup and don't drink at all!), hanging out with one or two friends, and mingling with strangers.
2. The Bored Upperclassmen. Refer back to the first paragraph and note for yourselves the cynical tone that I adopted in my introduction. This, friends, is because I am a sophomore in college, and am therefore infinitely older and wiser than you. Kidding. This is because I've been to my fair share of frat parties, and they're no longer quite as exciting. The bored upperclassmen at a party can usually be found congregating in the foyer, the kitchen, or anywhere away from the dance floor, and they divide their time between loudly discussing how bored they are and throwing dirty looks at the people having fun dancing.
3. The Frat Star. This is the brother whose fraternity is having the party, and he's having the time of his life. He can get you a drink, show you a safe place to leave your stuff, or even let you into the quieter rooms for a little peace and (relative) quiet. Usually pretty drunk, the frat star is fun to be around, and can be a useful asset if you know him well.
4. The Drunk Jerk. This is the guy who wasn't invited to the party- he's the one who just walked in and no one really knows how he got there. He's belligerently drunk and just looking to cause a scene for no reason at all. Usually clearly identifiable by his colorful vocabulary and swinging fists, this is definitely one party-goer you should steer clear of.
5. The Creepy Predator. This is the guy who's lurking in the shadows, just waiting to find an underclassmen girl who needs help getting a drink. This guy gives off majorly shady vibes, and if you come across one of these, stick with your friends and avoid his lecherous stares.
Do other people attend these sorts of parties, you ask? Of course. But these are the ones to watch out for, because these are the ones who will safeguard your coat, try and abduct you in a dark alley, or vastly entertain you with their drunken rendition of "We Can't Stop." One thing's for sure, dear freshmen–your frat party experience will never, ever, be boring.