Speaker : Dr. Shi Yishuo (Institute of Information Science)
Title : Design of Algorithm for Fault-Tolerant Virtual Backbone in Wireless Networks and Influence Propagation in Social Networks
Time : 2019-01-15 (Tue) 15:00 -
Place : Seminar Room 617, Institute of Mathematics (NTU Campus)
Abstract: The talk focuses on combinatorial optimization problems under network background, aiming at the design of efficient algorithm with good approximation ratios. It contains two parts. The first part, studies the construction of fault tolerant virtual backbone in a wireless sensor network, which can be modeled as a $k$-connected $m$-fold dominating set ~($(k,m)$-CDS). A subset of nodes $C\subseteq V(G)$ is a $(k,m)$-CDS of $G$ if every node in $V(G)\setminus C$ is adjacent with at least $m$ nodes in $C$ and the subgraph of $G$ induced by $C$ is $k$-connected. For the minimum $(2,m)$-CDS problem with $m\geq 2$, we give an $\alpha+2(1+\ln\alpha)$ approximation algorithm, where $\alpha$ is the approximation ratio for the minimum $(1,m)$-CDS problem. This is the first approximation algorithm for $(2,m)$-CDS in general graphs with a guaranteed performance ratio and significantly improves previous approximation ratios in unit disk graphs. One step further, we present the first constant approximation algorithm for the minimum weight $(k,m)$-CDS problem in unit disk graphs with $m\geq k$, answering the following open question in wireless sensor networks: dose there exist a constant approximation algorithm for the minimum $(k,m)$-CDS problem in unit disk graphs for ~$k\geq 4$ ?

The second part is motivated by the influence propagation problem in a social network. The main problem is the minimum cost partial set multi-cover problem (PSMC), the goal of which is to find a minimum cost sub-collection of sets such that at least some percentage (say q) of all elements are fully covered. In order to solve PSMC, we first propose a new NP-hard problem: the minimum density subcollection (MDSC), and give an $O(r_{\max}(\log n)^2)$--approximation algorithm for MDSC, where $r_{\max}$ is the maximum covering requirement of an element. Based on this algorithm, we give a bicriteria ($q-\varepsilon, O(\frac{r_{\max}(\log n)^2}{\varepsilon})$--approximation algorithm for PSMC, which outputs a subcollection of sets at least $(q-\varepsilon)$-percentage of all elements fully covering achieving approximation ratio $O(\frac{r_{\max}(\log n)^2}{\varepsilon})$. Then, we generalized the above problem to the minimum submodular cost partial set multi-cover problem, give a first randomized algorithm which is a $(q-\varepsilon,O(b/\varepsilon))$ bicriterion algorithm with high probability where $b=O(f^{r_{max}})$ and $f$ is the maximum frequency of an element. We also study its special dual problem called the maximum profit with a submodular budget constraint problem including classical maximum densest $k$--subgraph problem as a special case and show the open problem related to it.