1 Introduction
In the network design problems, we have been studying many combinatorial problems such as minimum Steiner tree problems and minimum spanning tree problems[12]. This paper studies a prize collecting Steiner tree problems (PCST) which is proposed by Han et.al.[11]. This problem generalizes both minimum spanning tree problems and prize collecting Steiner tree problems.
We are given an undirected connected graph , a root vertex , and an integer . Let be a nonnegative cost function on and be a nonnegative penalty cost function on . Suppose that a tuple is an instance of PCST. The goal is to find an rooted subtree that spans at least vertices with minimum total cost that is described by . Han et.al.[11] proposed a 5approximation algorithm based on primaldual method for this problem. Suppose OPT and are the optimal value and an optimal solution for the PCST instance.
Han et. al. [11] assume the following four general conditions to establish 5approximation algorithm for PCST.

is a complete graph.

The cost function satisfies a triangular inequality.

For each , a distance from is smaller than the optimal value of PCST obtained from the PCST instance.

The minimum nonnegative value of cost function is smaller than the optimal value of PCST.
Our paper employs same conditions when we discuss PCST.
In this paper, we propose a 4approximation algorithm for PCST based on two primaldual methods for minimum spanning tree problems and prize collecting Steiner tree problems. Also we propose 4approximation algorithm, that is the same framework, for prize collecting traveling salesman problems under the triangular inequality.
2 Preliminaries
The prize collecting Steiner tree problem is a generalization problem of both minimum spanning tree problems (MST) and prize collecting Steiner tree problems (PCST)[11].
MST is one of well studied network design problems. Given an undirected connected graph , a vertex , and an integer . Let be a nonnegative cost function on . Suppose that a tuple is an instance of rooted MST. The goal of this problem is to find a subtree of such that includes the vertex , , and minimum total cost which is . Unrooted MST was proposed by [13] who proved its NPhardness and gave a approximation algorithm. After that, many approximation algorithms have been proposed (see [7], [8], [6] and [2]). The best approximation ratio for this problem is 2 by Garg[9] who treats rooted MST.
For the PCST instance , we can get a rooted MST instance by for each . Suppose that OPT and are the optimal value and an optimal solution for the MST instance induced by the PCST instance. We hold the following lemma.
Lemma 1.
An optimal solution for MST satisfies
Proof.
Since the cost function and the penalty function are nonnegative, and ,
∎
From the lemma 1, a set of feasible solutions of MST includes any feasible solutions of PCST.
Other problem is prize collecting Steiner tree problems (PCST). In the PCST, given an undirected connected graph , an root vertex . Let be a nonnegative cost function on and be a nonnegative penalty cost function on . The goal is to find an rooted subtree with minimum total cost that is . Goemans and Williamson derive a 2approximation algorithm for this problem[10]. They show the following theorem.
Theorem 1 ([10]).
Consider an arbitrary PCST instance where . Suppose that and is an output of the algorithm. It holds that
is the objective function of dual problem of the LP relaxed PCST. This theorem shows that as the number of vertices increases, the approximation ratio becomes asymptotically 2. The best possible approximation algorithm is 1.9672 approximation derived by Archer et. al.[1]. When we set , PCST is a special case of PSCT. Since every feasible solution of PCST is also a feasible solution of PCST, we are able to show the following lemma.
Lemma 2.
An optimal solution for PCST satisfies
3 Proposed algorithm
We propose a primal dual method based 4approximation algorithm for PCST. Our algorithm combines two procedures, one is 2approximation algorithm for PCST proposed by Goemans and Williamson[10], the other is 2approximation algorithm for MST proposed by Garg[9]. We call each approximation algorithm procedure 1 and procedure 2, respectively. [l]4approximation algorithm for PCST
 Input:

An undirected connected graph , an root vertex , an integer , a cost function , and a penalty function .
 Output:

rooted prize collecting Steiner tree of .
 Step 1:

For a PCST instance , apply Procedure 1. Let be an output of this procedure. If , return , otherwise goto Step 2.
 Step 2:

For a MST instance , apply Procedure 2. Let be an output of this procedure.
 Step 3:

Construct an undirected connected graph , , and find a minimum spanning tree of . Return .
It is easy to check the output of proposed algorithm is a feasible solution for PCST and the algorithm is an polynomial time algorithm. The analysis of the time complexity will be described later. To analyze an approximation ratio of our algorithm, we introduce some terms. Given a PCST instance , let be an optimal solution and OPT be its optimal value. Also let be an optimal solution of PCST and OPT be its optimal value, be an optimal solution of MST and OPT be its optimal value.
Lemma 3.
If proposed algorithm terminated at Step 1, then holds
Proof.
From the assumption, the output is obtainable from Procedure 1. Since contains a vertex and , is a feasible solution of PCST. Suppose is an optimal value of PCST instance . From lemma 2, we get
∎
Theorem 2.
If proposed algorithm terminated at Step 4, then holds
Proof.
From above discussion, we get 4approximation algorithm for PCST. Our algorithm has a following property.
Proposition 1.
If there exists an optimal solution for PCST such that , then holds
Proof.
Consider the case that our algorithm terminated in Step 4. From the theorem 2, is a feasible solution of PCST. We get
∎
Next, we describe the time complexity of the proposed algorithm for the PCST problem. If the number of vertices is and the number of edges is for the input graph, the time complexity of GWalgorithm is O(), the time complexity of Garg’s algorithm is O(). In the proposed algorithm, we call the algorithm of GWalgorithm and Garg’s algorithm once. The minimum spanning tree is obtained for the subgraph obtained last, but by using the Kruskal algorithm O(). Therefore, the time complexity of the proposed algorithm is O().
4 Prize collecting traveling salesman problems
In order to simplify the explanation, a tour of the graph is represented as a sequence of vertices, denoted by . Denote that is a edge set and is a vertex set induced by . In other words, we define and .
We are given a complete graph , a root vertex , and an integer . Let be a nonnegative cost function on and be a nonnegative penalty function. The prize collecting traveling salesman problem (PCTSP) is a problem of finding a tour that minimizes in the tour of G with the number of vertices equal to or larger than and including the vertex . This problem is a generalization of both traveling salesman problems(TSP) and penalty traveling salesman problems(PTSP)[11]. TSP and PTSP is described in [3]. Under the triangular inequality for the edge cost function, Han et al. show that there is a 5approximation algorithm for the PCTSP in [11], which is the best approximation ratio among the approximation algorithms for the existing PCTSP.
It is known that PCTSP is a special case of prize collecting traveling salesman problems(PCTSP) proposed by Balas[5]. Given a complete graph , a vertex , a nonnegative integer , a cost function , a penalty function , and a reward function . This problem finds a tour such that contains and minimizes under a cover constraint . PCTSP can be reduced to PCTSP by setting for every and .
An approximation algorithm combining two approximation algorithms for quota traveling salesman problems (QTSP) and for PTSP is shown in [4] and [3] for the PCTSP assuming that the cost function satisfies the triangular inequality. From the fact that QTSP is a generalization of TSP, we can show a 4approximation algorithm for PCTSP when the cost function satisfies the triangular inequality by using a similar technique.
Our algorithm framework can be applied to the PCTSP. We employ two 2approximation algorithms, one is for PTSP[10] and the other is for TSP[9].
[l]4approximation algorithm for PCTSP
 Input:

A complete graph , a vertex , an integer , a cost function , and a penalty function .
 Output:

A tour of including , denoted by .
 Step 1:

For a TSP instance , we apply Garg’s algorithm. Let be an output of this procedure.
 Step2:

For a PCTSP instance , we apply GW algorithm. Let be an output of this procedure.
 Step3:

Return a short cut of a tour that merged and .
From each procedure is 2approximation algorithm for TSP and PTSP, we can get the following by using [4]’s technique.
Theorem 3.
Proposed algorithm is 4approximation algorithm for PCTSP under the triangular inequality.
Proof.
Suppose that , , and are costs of , , and , respectively. We denote the optimal value for each problem to OPT , OPT, and OPT.
∎
5 Conclusion
This paper proposed 4approximation algorithm for both prize collecting Steiner tree problems and prize collecting traveling salesman problems. The time complexity of the proposed approximation algorithm is O (). A bottleneck is Garg’s approximation algorithm for MST, TSP. As a future task, in order to reduce the calculation amount, reduction of the time complexity of the approximation algorithm for MST and TSP can be mentioned. Improvement of the approximation rate for PCST and PCTSP is also a future task.
Acknowledgement
This research was partially supported by the Ministry of Education, Science, Sports and Culture through GrantsinAid for Scientific Research (C) 26330025, (B) 15H02972, and through GrantsinAid for Young Scientists (B) 26870200.
References
 [1] A. Archer, B. Mohammadhossein, M. Hajiaghayi, and H. Karloff, Improved approximation algorithms for prizecollecting Steiner tree and TSP, SIAM Journal of Computing, 40, 309–332, (2011).
 [2] S. Arora and G. Karakostas, A approximation algorithm for the MST problem, Mathematical Programming Series A, 107, 491–504 (2006).
 [3] G. Ausiello, V. Bonifaci, S. Leonardi, and A.M. Spaccamela, Prize Collecting Traveling Salesman problem and Related Problems, in Handbook of Approximation Algorithms and Metaheuristics, Chapter 40, Chapman & Hall/CRC (2007).
 [4] B. Awerbuch, Y. Azar, A. Blum, and S. Vempala. New Approximation Guarantees for MinimumWeight Trees and PrizeCollecting Salesmen, SIAM Journal on Computing, 28(1), 254–262 (1998)
 [5] E. Balas, The prize collecting traveling salesman problem, Networks, 19, 621–636(1989)
 [6] A. Blum, R. Ravi, and S. Vempala, A constant factor approximation for the MST problem, Journal of Computer and System Sciences, 58(1), 101–108 (1999).
 [7] M. Fischetti, H.W. Hamacher, K. Jörnsten, and F. Maffioli, Weighted cardinality trees: complexity and polyhedral structure, Networks, 24, 11–21 (1994).
 [8] N. Garg, A 3approximation for the minimum tree spanning vertices, In Proceedings of 37th IEEE Symp. on Foundations of Computer Science (FOCS), 302–309 (1996).

[9]
N. Garg, Saving an epsilon: a 2approximation for the MST problem in graphs,
In Proceedings of the 37th Annual ACM Symposium on Theory of Computing
, 396–402, (2005).  [10] M. X. Goemans and D. P. Williamson, A general approximation technique for constrained forest problems, SIAM Journal of Computation, 24, 296–317, (1995).
 [11] L. Han, D. Xu, D. Du, and C. Wu, A 5approximation algorithm for the kprizecollecting Steiner tree problem, Optimization Letters, (2017).
 [12] B. H. Korte, and J. Vygen, Combinatorial Optimization: Theory and Algorithms, SpringerVerlag (2004).
 [13] R. Ravi, R. Sundaram, M. Marathe, D. Rosenkrantz, and S. Ravi, Spanning trees short and small, Journal of Discrete Mathematics, 9(2), 178–200 (1993).
Comments
There are no comments yet.