4 papers
A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensors
Wei Liang, Shaojie Tang, Zhao Zhang
In this paper, we present the first constant-approximation algorithm for {\em budgeted sweep coverage problem} (BSC). The BSC involves designing routes for a number of mobile senso…
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…