A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem
- PDF / 964,655 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 85 Downloads / 196 Views
A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem Lu Han1 · Da-Chuan Xu1 · Dong-Lei Du2 · Chen-Chen Wu3
Received: 10 August 2016 / Revised: 22 January 2017 / Accepted: 5 April 2017 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg 2017
Abstract In this paper, we consider the generalized prize-collecting Steiner forest problem, extending the prize-collecting Steiner forest problem. In this problem, we are given a connected graph G = (V, E) and a set of vertex sets V = {V1 , V2 , · · · , Vl }. Every edge in E has a nonnegative cost, and every vertex set in V has a nonnegative penalty cost. For a given edge set F ⊆ E, vertex set Vi ∈ V is said to be connected by edge set F if Vi is in a connected component of the F-spanned subgraph. The objective is to find such an edge set F such that the total edge cost in F and the penalty cost of
This paper is dedicated to Professor Lian-Sheng Zhang in celebration of his 80th birthday. D.-C. Xu is supported by the National Natural Science Foundation of China (No. 11371001) and Collaborative Innovation Center on Beijing Society-Building and Social Governance. D.-L. Du is supported by the Natural Sciences and Engineering Research Council of Canada (No. 06446). C.-C. Wu is supported by the National Natural Science Foundation of China (No. 11501412).
B
Da-Chuan Xu [email protected] Lu Han [email protected] Dong-Lei Du [email protected] Chen-Chen Wu [email protected]
1
Department of Information and Operations Research, Beijing University of Technology, Beijing 100124, China
2
Faculty of Business Administration, University of New Brunswick, Fredericton, NB E3B 5A3, Canada
3
College of Science, Tianjin University of Technology, Tianjin 300384, China
123
L. Han et al.
the vertex sets not connected by F is minimized. Our main contribution is to give a 3-approximation algorithm for this problem via the primal-dual method. Keywords Prize-collecting · Steiner forest · Approximation algorithm · Primal-dual Mathematics Subject Classification 90C27 · 68W25
1 Introduction The prize-collecting Steiner forest (PCSF) problem has several practical applications (see [1,2]). In the PCSF problem, we are given a connected graph G = (V, E) and a set of vertex pairs P = {(s1 , t1 ), (s2 , t2 ), · · · , (sl , tl )}. Every edge e ∈ E has a nonnegative cost ce . Every vertex pair (si , ti ) ∈ P has a nonnegative penalty cost π((si , ti )). Our goal is to find an edge set F such that the total cost, including the edge cost of the edges in F and the penalty cost of the vertex pairs not connected by F, is minimized. The PCSF problem is a well-known NP-hard problem, for which many approximation algorithms exist. It is easy to obtain an linear programming (LP)-rounding 3-approximation algorithm for the PCSF problem by adopting the idea in Bienstock et al. [3]. Hajiaghayi and Jain [4] improved the approximation ratio to 2.54 by using a randomized LP-rounding method.
Data Loading...
