40 citations · 97 across the 16 of their papers we have counts for
17 papers
Approximation Algorithm for Unrooted Prize-Collecting Forest with Multiple Components and Its Application on Prize-Collecting Sweep Coverage
Wei Liang, Shaojie Tang, Zhao Zhang
In this paper, we introduce a polynomial-time 2-approximation algorithm for the Unrooted Prize-Collecting Forest with Components (URPCF) problem. URPCF aims to find a f…
A New Approximation Algorithm for Minimum-Weight --Connected Dominating Set
Jiao Zhou, Yingli Ran, Panos M. Pardalos +3
Consider a graph with nonnegative node weight. A vertex subset is called a CDS (connected dominating set) if every other node has at least one neighbor in the subset and the subset…
Evolution is Still Good: Theoretical Analysis of Evolutionary Algorithms on General Cover Problems
Yaoyao Zhang, Chaojie Zhu, Shaojie Tang +3
Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ra…
Approximation Algorithm for Minimum Union Under a Geometric Setting
Yingli Ran, Zhao Zhang
In a minimum union problem (MinU), given a hypergraph and an integer , the goal is to find a set of hyperedges such that the number of verti…
A parallel algorithm for minimum weight set cover with small neighborhood property
Yingli Ran, Yaoyao Zhang, Zhao Zhang
This paper studies the minimum weight set cover (MinWSC) problem with a {\em small neighborhood cover} (SNC) property proposed by Agarwal {\it et al.} in \cite{Agarwal.}. A paralle…
Performance Guaranteed Evolutionary Algorithm for Minimum Connected Dominating Set
Chaojie Zhu, Yingli Ran, Zhao Zhang +1
A connected dominating set is a widely adopted model for the virtual backbone of a wireless sensor network. In this paper, we design an evolutionary algorithm for the minimum conne…
Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem
Yingli Ran, Zhao Zhang, Shaojie Tang
In the minimum cost submodular cover problem (MinSMC), we are given a monotone nondecreasing submodular function , a linear cost function $c:…
On Approximating Partial Set Cover and Generalizations
Chandra Chekuri, Kent Quanrud, Zhao Zhang
Partial Set Cover (PSC) is a generalization of the well-studied Set Cover problem (SC). In PSC the input consists of an integer and a set system where is a finite s…
Extremality and Sharp Bounds for the -edge-connectivity of Graphs
Yuefang Sun, Xiaoyan Zhang, Zhao Zhang
Boesch and Chen (SIAM J. Appl. Math., 1978) introduced the cut-version of the generalized edge-connectivity, named -edge-connectivity. For any integer with ,…
Approximation Algorithm for the Partial Set Multi-Cover Problem
Yishuo Shi, Yingli Ran, Zhao Zhang +3
Partial set cover problem and set multi-cover problem are two generalizations of set cover problem. In this paper, we consider the partial set multi-cover problem which is a combin…
Circumference of 3-connected cubic graphs
Qinghai Liu, Xingxing Yu, Zhao Zhang
The circumference of a graph is the length of its longest cycles. Jackson established a conjecture of Bondy by showing that the circumference of a 3-connected cubic graph of order…
Randomized Bicriteria Approximation Algorithm for Minimum Submodular Cost Partial Multi-Cover Problem
Yishuo Shi, Zhao Zhang, Ding-Zhu Du
This paper studies randomized approximation algorithm for a variant of the set cover problem called minimum submodular cost partial multi-cover (SCPMC), in which each element h…
Performance Guaranteed Approximation Algorithm for Minimum -Connected -Fold Dominating Set
Zhao Zhang, Jiao Zhou, Xiaohui Huang +1
To achieve an efficient routing in a wireless sensor network, connected dominating set (CDS) is used as virtual backbone. A fault-tolerant virtual backbone can be modeled as a $(k,…
Approximation Algorithm for Fault-Tolerant Virtual Backbone in Wireless Sensor Networks
Jiao Zhou, Zhao Zhang, Xiaohui Huang +1
To save energy and alleviate interferences in a wireless sensor network, the usage of virtual backbone was proposed. Because of accidental damages or energy depletion, it is desira…
Approximation Algorithm for Minimum Weight Connected -Fold Dominating Set
Zhao Zhang, Jiao Zhou, Ker-I Ko +1
Using connected dominating set (CDS) to serve as a virtual backbone in a wireless networks can save energy and reduce interference. Since nodes may fail due to accidental damage or…
Approximation Algorithm for Minimum Weight -CDS Problem in Unit Disk Graph
Yishuo Shi, Zhao Zhang, Ding-Zhu Du
In a wireless sensor network, the virtual backbone plays an important role. Due to accidental damage or energy depletion, it is desirable that the virtual backbone is fault-toleran…
Networked Stochastic Multi-Armed Bandits with Combinatorial Strategies
Shaojie Tang, Yaqin Zhou
In this paper, we investigate a largely extended version of classical MAB problem, called networked combinatorial bandit problems. In particular, we consider the setting of a decis…