Efficient algorithms for the conditional covering problem

We consider the conditional covering problem in an undirected network, in which each vertex represents a demand point that must be covered by a facility as well as a potential facility site. Each facility can cover all vertices within a given coverage radius, except the vertex at which the facility is located. The objective is to locate facilities to cover all vertices such that the total facility location cost is minimized. In this paper, new upper bounds are proposed for the conditional covering problem on paths, cycles, extended stars, and trees. In particular, we provide an O ( n log n ) -time algorithm for paths, an O ( n 2 log n ) -time algorithm for cycles, an O ( n 1. 5 log n ) -time algorithm for extended stars, and an O ( n 3 ) -time algorithm for trees. Our algorithms for paths, extended stars, and trees improve the previous upper bounds from O ( n 2 ), O ( n 2 ), and O ( n 4 ), respectively.

Authors

• Robert Benkoczi
• Binay Bhattacharya
• Yuzhuang Hu
• Chien-Hsin Lin
• Qiaosheng Shi
• Biing-Feng Wang

Keywords

• Algorithms
• Graphs
• Covering location problems
• Conditional covering
• Dynamic programming