Vassilis Zissimopoulos

Ioannis Sigalas, Nikolaos Lazaropoulos, Ioannis Lamprou et al.

In various domination and coverage problems, certain vertices or edges should not be dominated/covered and are designated as vulnerable. Motivated by this, we define the $k$-Vertex Maximum Domination Ratio with Vulnerable Vertices $(k\textit{-}Max \ \mathit{DRVV})$ problem, which extends the budgeted dominating set problem to include vulnerability constraints. We propose an approximation algorithm based on an unbudgeted variant of $k\textit{-}Max \ \mathit{DRVV}$, termed the Maximum Domination Ratio with Vulnerable Vertices $(\mathit{DRVV})$ problem. For bounded-degree graphs of order $n$, our algorithm provides an $O(k/n)$-approximation for the $k\textit{-}Max \ \mathit{DRVV}$ problem. We introduce the Dominating Set with Vulnerable Vertices $(\mathit{DSV})$ problem, reduce it to the Red-Blue Set Cover problem, and derive a $2\sqrt{|V|\cdot(H(Δ_{N})-\frac{1}{2}})$-approximation algorithm, where $|V|$ is the order of the graph, $Δ_N$ is the maximum degree among non-vulnerable vertices and $H$ is the harmonic function. Finally, we examine the Vertex Cover with Vulnerable Edges $(\mathit{VCVE})$ problem, which can be naturally expressed as a special case of the Red-Blue Set Cover problem. We present a polynomial-time $2$-approximation algorithm for the $VCVE$ problem, achieving the best possible ratio.

Yicheng Xu, Vincent Chau, Chenchen Wu et al.

Clustering is one of the most fundamental tools in the artificial intelligence area, particularly in the pattern recognition and learning theory. In this paper, we propose a simple, but novel approach for variance-based k-clustering tasks, included in which is the widely known k-means clustering. The proposed approach picks a sampling subset from the given dataset and makes decisions based on the data information in the subset only. With certain assumptions, the resulting clustering is provably good to estimate the optimum of the variance-based objective with high probability. Extensive experiments on synthetic datasets and real-world datasets show that to obtain competitive results compared with k-means method (Llyod 1982) and k-means++ method (Arthur and Vassilvitskii 2007), we only need 7% information of the dataset. If we have up to 15% information of the dataset, then our algorithm outperforms both the k-means method and k-means++ method in at least 80% of the clustering tasks, in terms of the quality of clustering. Also, an extended algorithm based on the same idea guarantees a balanced k-clustering result.