Algorithm Research On Minimum Power Partial Cover Problem

The coverage problem is a classic NP-hard problem.In recent years,due to the rapid progress of wireless sensor networks,the problem of disk cover has attracted more and more attention.Considering fault tolerance,a lot of work has been done to study the multicov-er problem.In practice,the cost of full coverage is often too high,so the partial coverage problem arises.This paper mainly studies the algorithm design and analysis of the mini-mum power partial cover problem on Euclid plane and minimum power partial multicover problem on a line.For the minimum power partial cover problem on the Euclidean plane,suppose X is a set of n points,and S is a set of m servers.Any server s can adjust its power p(s),and the covering range of server s with power p(s)is a circular area of radius r(s),where p(s)=c·r(s)?(??1).A point x is covered by a server s if x falls into the covering range of s.Given positive integer k ?|X|,the goal of the minimum power partial cover problem is to determine the power of servers so that at least k points are covered and the total power is minimized.We design a local ratio algorithm and a primal dual algorithm.Through a strict theoretical analysis their approximate ratios are proved to be 3a.There is only paper studying the partial version of the minimum power problem,and the study is only carrried out on the special case of ?=2,achieving approximation ratio(12+?).Our algorithm is valid for any ?,greater than or equal to 1,and our approximate ratio is 9 for ?=2,which improves the previous ratioThe minimum power partial cover problem on a line is a special case of the minimum power partial cover problem on the plane,where points and sensors are all confined on a line.This thesis studies a more general problem:the minimum power partial multi-cover problem on a line.Every point has a covering requirement cr(x).We say that x is fully covered only when x is covered by at least cr(x)servers.The goal of the problem is to determine the power of servers so that at least k points in X are fully covered and the total power is as small as possible.For the minimum power partial multi-cover on a line,under the assumption that crmax=max{cr(x):x??} is upper bounded by a constant,we design a dynamic programming algorithm which finds an optimal solution in polynomial time.