Approximation Algorithms For Partially Prize-Collecting Laminar Cover Problems

Covering problem is one of classical problems in combinatorial optimization,and is widely studied.Laminar cover problem is a special case of covering problem.In this thesis,we consider two variants of laminar cover problem:k-prize-collecting laminar cover problem and P-prize-collecting laminar cover problem.In the k-prize-collecting laminar cover problem,we are given a graph G=(V,E).Every edge e∈E has a non-negative cost c(e).F={V1,V2,...,Vm} is a laminar family of vertex subsets,that is Vi∩Vj∈{Vi,Vj,(?)} for any vertex subsets Vi,Vj∈F.Each vertex subset Vi∈F has a non-negative penalty cost πi.For a given edge e∈E,vertex subset Vi∈F is said to be covered by e if e has exactly one node in Vi.Given a positive integer k(≤m).The objective is to find an edge subset E’ covering at least k vertex subsets in F such that the sum of the total costs of the edges in E’ and the total penalty costs of the vertex subsets not covered by the edges in E’ is minimized.In the P-prize-collecting laminar cover problem,we are given a graph G=(V,E).Every edge e∈E has a non-negative cost c(e).F={V1,V2,...,Vm} is a laminar family of vertex subsets.Each vertex subset Vi∈F has a non-negative penalty cost πi and a non-negative profit pi.Given a non-negative constant P(less than or equal to the sum of the profits of the vertex subsets in F).The objective is to find an edge subset E’ covering vertex subsets in F whose total profits are at least P such that the sum of the total costs of the edges in E’ and the total penalty costs of the vertex subsets not covered by the edges in E’ is minimized.In this thesis,the approximation algorithms for solving the above two problems are respectively designed by using the Lagrange relaxation technique.The approximation ratios of both algorithms are 4+ε,where ε is any fixed positive number.