40 citations · 97 across the 16 of their papers we have counts for
6 papers · 1 filter
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…
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…
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…
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…