In this paper,an Unmanned Aerial Vehicle(UAV)-assisted relay communication system is studied,where a UAV is served as a flying relay to maintain a communication link between a mobile source node and a remote destinati...In this paper,an Unmanned Aerial Vehicle(UAV)-assisted relay communication system is studied,where a UAV is served as a flying relay to maintain a communication link between a mobile source node and a remote destination node.Specifically,an average outage probability minimization problem is formulated firstly,with the constraints on the transmission power of the source node,the maximum energy consumption budget,the transmission power,the speed and acceleration of the flying UAV relay.Next,the closed-form of outage probability is derived,under the hybrid line-of-sight and non-line-of-sight probability channel model.To deal with the formulated nonconvex optimization,a long-term proactive optimization mechanism is developed.In particular,firstly,an approximation for line-of-sight probability and a reformulation of the primal problem are given,respectively.Then,the reformulated problem is transformed into two subproblems:one is the transmission power optimization with given UAV’s trajectory and the other is the trajectory optimization with given transmission power allocation.Next,two subproblems are tackled via tailoring primal–dual subgradient method and successive convex approximation,respectively.Furthermore,a proactive optimization algorithm is proposed to jointly optimize the transmission power allocation and the three-dimensional trajectory.Finally,simulation results demonstrate the performance of the proposed algorithm under various parameter configurations.展开更多
Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields ...Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods.展开更多
In the present paper we present a class of polynomial primal-dual interior-point algorithms for semidefmite optimization based on a kernel function. This kernel function is not a so-called self-regular function due to...In the present paper we present a class of polynomial primal-dual interior-point algorithms for semidefmite optimization based on a kernel function. This kernel function is not a so-called self-regular function due to its growth term increasing linearly. Some new analysis tools were developed which can be used to deal with complexity ＂analysis of the algorithms which use analogous strategy in [5] to design the search directions for the Newton system. The complexity bounds for the algorithms with large- and small-update methodswere obtained, namely,O（qn^（p＋q/q（P＋1）log n/ε and O（q^2√n）log n/ε,respectlvely.展开更多
In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neig...In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neighborhood degenerates into the central path, our algorithms also degenerate into path-following algorithms. We prove that our algorithms maintain the O9√nL) -iteration complexity still, while the classical wide neighborhood primal-dual interior point algorithms have only the O(nL-iteration complexity. We also proved that the algorithms are quadratic convergence if the optimal vertex is nondegenerate. Finally, we show some computational results of our algorithms.展开更多
The distributed nonconvex optimization problem of minimizing a global cost function formed by a sum of n local cost functions by using local information exchange is considered.This problem is an important component of...The distributed nonconvex optimization problem of minimizing a global cost function formed by a sum of n local cost functions by using local information exchange is considered.This problem is an important component of many machine learning techniques with data parallelism,such as deep learning and federated learning.We propose a distributed primal-dual stochastic gradient descent(SGD)algorithm,suitable for arbitrarily connected communication networks and any smooth(possibly nonconvex)cost functions.We show that the proposed algorithm achieves the linear speedup convergence rate O(1/(√nT))for general nonconvex cost functions and the linear speedup convergence rate O(1/(nT)) when the global cost function satisfies the Polyak-Lojasiewicz(P-L)condition,where T is the total number of iterations.We also show that the output of the proposed algorithm with constant parameters linearly converges to a neighborhood of a global optimum.We demonstrate through numerical experiments the efficiency of our algorithm in comparison with the baseline centralized SGD and recently proposed distributed SGD algorithms.展开更多
Neutron computed tomography(NCT)is widely used as a noninvasive measurement technique in nuclear engineering,thermal hydraulics,and cultural heritage.The neutron source intensity of NCT is usually low and the scan tim...Neutron computed tomography(NCT)is widely used as a noninvasive measurement technique in nuclear engineering,thermal hydraulics,and cultural heritage.The neutron source intensity of NCT is usually low and the scan time is long,resulting in a projection image containing severe noise.To reduce the scanning time and increase the image reconstruction quality,an effective reconstruction algorithm must be selected.In CT image reconstruction,the reconstruction algorithms can be divided into three categories:analytical algorithms,iterative algorithms,and deep learning.Because the analytical algorithm requires complete projection data,it is not suitable for reconstruction in harsh environments,such as strong radia-tion,high temperature,and high pressure.Deep learning requires large amounts of data and complex models,which cannot be easily deployed,as well as has a high computational complexity and poor interpretability.Therefore,this paper proposes the OS-SART-PDTV iterative algorithm,which uses the ordered subset simultaneous algebraic reconstruction technique(OS-SART)algorithm to reconstruct the image and the first-order primal–dual algorithm to solve the total variation(PDTV),for sparse-view NCT three-dimensional reconstruction.The novel algorithm was compared with other algorithms(FBP,OS-SART-TV,OS-SART-AwTV,and OS-SART-FGPTV)by simulating the experimental data and actual neutron projection experiments.The reconstruction results demonstrate that the proposed algorithm outperforms the FBP,OS-SART-TV,OS-SART-AwTV,and OS-SART-FGPTV algorithms in terms of preserving edge structure,denoising,and suppressing artifacts.展开更多
We consider the problem of restoring images corrupted by Poisson noise. Under the framework of maximum a posteriori estimator, the problem can be converted into a minimization problem where the objective function is c...We consider the problem of restoring images corrupted by Poisson noise. Under the framework of maximum a posteriori estimator, the problem can be converted into a minimization problem where the objective function is composed of a Kullback-Leibler(KL)-divergence term for the Poisson noise and a total variation(TV) regularization term. Due to the logarithm function in the KL-divergence term, the non-differentiability of TV term and the positivity constraint on the images, it is not easy to design stable and efficiency algorithm for the problem. Recently, many researchers proposed to solve the problem by alternating direction method of multipliers(ADMM). Since the approach introduces some auxiliary variables and requires the solution of some linear systems, the iterative procedure can be complicated. Here we formulate the problem as two new constrained minimax problems and solve them by Chambolle-Pock's first order primal-dual approach. The convergence of our approach is guaranteed by their theory. Comparing with ADMM approaches, our approach requires about half of the auxiliary variables and is matrix-inversion free. Numerical results show that our proposed algorithms are efficient and outperform the ADMM approach.展开更多
Interior-point methods （IPMs） for linear optimization （LO） and semidefinite optimization （SDO） have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with si...Interior-point methods （IPMs） for linear optimization （LO） and semidefinite optimization （SDO） have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with simple algebraic expression is proposed. Based on this kernel function, a primal-dual interior-point methods （IPMs） for semidefinite optimization （SDO） is designed. And the iteration complexity of the algorithm as O（n^3/4 log n/ε） with large-updates is established. The resulting bound is better than the classical kernel function, with its iteration complexity O（n log n/ε） in large-updates case.展开更多
In this paper,we consider the-prize-collecting minimum vertex cover problem with submodular penalties,which generalizes the well-known minimum vertex cover problem,minimum partial vertex cover problem and minimum vert...In this paper,we consider the-prize-collecting minimum vertex cover problem with submodular penalties,which generalizes the well-known minimum vertex cover problem,minimum partial vertex cover problem and minimum vertex cover problem with submodular penalties.We are given a cost graph and an integer.This problem determines a vertex set such that covers at least edges.The objective is to minimize the total cost of the vertices in plus the penalty of the uncovered edge set,where the penalty is determined by a submodular function.We design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the problem.When the submodular penalty cost function is normalized and nondecreasing,the proposed algorithm has an approximation factor of.When the submodular penalty cost function is linear,the approximation factor of the proposed algorithm is reduced to,which is the best factor if the unique game conjecture holds.展开更多
This paper investigates two distributed accelerated primal-dual neurodynamic approaches over undirected connected graphs for resource allocation problems(RAP)where the objective functions are generally convex.With the...This paper investigates two distributed accelerated primal-dual neurodynamic approaches over undirected connected graphs for resource allocation problems(RAP)where the objective functions are generally convex.With the help of projection operators,a primal-dual framework,and Nesterov's accelerated method,we first design a distributed accelerated primal-dual projection neurodynamic approach(DAPDP),and its convergence rate of the primal-dual gap is O(1/(t^(2)))by selecting appropriate parameters and initial values.Then,when the local closed convex sets are convex inequalities which have no closed-form solutions of their projection operators,we further propose a distributed accelerated penalty primal-dual neurodynamic approach(DAPPD)on the strength of the penalty method,primal-dual framework,and Nesterov's accelerated method.Based on the above analysis,we prove that DAPPD also has a convergence rate O(1/(t^(2)))of the primal-dual gap.Compared with the distributed dynamical approaches based on the classical primal-dual framework,our proposed distributed accelerated neurodynamic approaches have faster convergence rates.Numerical simulations demonstrate that our proposed neurodynamic approaches are feasible and effective.展开更多
Color image segmentation is crucial in image processing and computer vision.Most traditional segmentation methods simply regard an RGB color image as the direct combination of the three monochrome images and ignore th...Color image segmentation is crucial in image processing and computer vision.Most traditional segmentation methods simply regard an RGB color image as the direct combination of the three monochrome images and ignore the inherent color structures within channels,which contain some key feature information of the image.To better describe the relationship of color channels,we introduce a quaternion-based regularization that can reflect the image characteristics more intuitively.Our model combines the idea of the Mumford-Shah model-based two-stage segmentation method and the Saturation-Value Total Variation regularization for color image segmentation.The new strategy first extracts features from the color image and then subdivides the image in a new color feature space which achieves better performance than methods in RGB color space.Moreover,to accelerate the optimization process,we use a new primal-dual algorithm to solve our novel model.Numerical results demonstrate clearly that the performance of our proposed method is excellent.展开更多
This paper studies the distributed optimization problem when the objective functions might be nondifferentiable and subject to heterogeneous set constraints.Unlike existing subgradient methods,the authors focus on the...This paper studies the distributed optimization problem when the objective functions might be nondifferentiable and subject to heterogeneous set constraints.Unlike existing subgradient methods,the authors focus on the case when the exact subgradients of the local objective functions can not be accessed by the agents.To solve this problem,the authors propose a projected primaldual dynamics using only the objective function’s approximate subgradients.The authors first prove that the formulated optimization problem can generally be solved with an error depending upon the accuracy of the available subgradients.Then,the authors show the exact solvability of this distributed optimization problem when the accumulated approximation error of inexact subgradients is not too large.After that,the authors also give a novel componentwise normalized variant to improve the transient behavior of the convergent sequence.The effectiveness of the proposed algorithms is verified by a numerical example.展开更多
In this paper,we consider the P-prize-collecting set cover(P-PCSC)problem,which is a generalization of the set cover problem.In this problem,we are given a set system(U,S),where U is a ground set and S⊆2U is a collect...In this paper,we consider the P-prize-collecting set cover(P-PCSC)problem,which is a generalization of the set cover problem.In this problem,we are given a set system(U,S),where U is a ground set and S⊆2U is a collection of subsets satisfying∪S∈SS=U.Every subset in S has a nonnegative cost,and every element in U has a nonnegative penalty cost and a nonnegative profit.Our goal is to find a subcollection C⊆S such that the total cost,consisting of the cost of subsets in C and the penalty cost of the elements not covered by C,is minimized and at the same time the combined profit of the elements covered by C is at least P,a specified profit bound.Our main work is to obtain a 2f+ε-approximation algorithm for the P-PCSC problem by using the primal-dual and Lagrangian relaxation methods,where f is the maximum frequency of an element in the given set system(U,S)andεis a fixed positive number.展开更多
基金co-supported by the Natural Science Foundation for Distinguished Young Scholars of Jiangsu Province(No.BK20190030)the National Natural Science Foundation of China(Nos.61871398 and 61931011)the National Key R&D Program of China(No.2018YFB1801103)。
文摘In this paper,an Unmanned Aerial Vehicle(UAV)-assisted relay communication system is studied,where a UAV is served as a flying relay to maintain a communication link between a mobile source node and a remote destination node.Specifically,an average outage probability minimization problem is formulated firstly,with the constraints on the transmission power of the source node,the maximum energy consumption budget,the transmission power,the speed and acceleration of the flying UAV relay.Next,the closed-form of outage probability is derived,under the hybrid line-of-sight and non-line-of-sight probability channel model.To deal with the formulated nonconvex optimization,a long-term proactive optimization mechanism is developed.In particular,firstly,an approximation for line-of-sight probability and a reformulation of the primal problem are given,respectively.Then,the reformulated problem is transformed into two subproblems:one is the transmission power optimization with given UAV’s trajectory and the other is the trajectory optimization with given transmission power allocation.Next,two subproblems are tackled via tailoring primal–dual subgradient method and successive convex approximation,respectively.Furthermore,a proactive optimization algorithm is proposed to jointly optimize the transmission power allocation and the three-dimensional trajectory.Finally,simulation results demonstrate the performance of the proposed algorithm under various parameter configurations.
基金Supported by National Natural Science Foundation of China (Grant Nos.10771133 and 70871082)Shanghai Leading Academic Discipline Project (Grant No.S30104)
文摘Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods.
文摘In the present paper we present a class of polynomial primal-dual interior-point algorithms for semidefmite optimization based on a kernel function. This kernel function is not a so-called self-regular function due to its growth term increasing linearly. Some new analysis tools were developed which can be used to deal with complexity ＂analysis of the algorithms which use analogous strategy in [5] to design the search directions for the Newton system. The complexity bounds for the algorithms with large- and small-update methodswere obtained, namely,O（qn^（p＋q/q（P＋1）log n/ε and O（q^2√n）log n/ε,respectlvely.
基金This work is partially supported by the National Natural Science Foundation of China(Grant No.19731010)the Knowledge Innovation Program of the Chinese Academy of Sciences.
文摘In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neighborhood degenerates into the central path, our algorithms also degenerate into path-following algorithms. We prove that our algorithms maintain the O9√nL) -iteration complexity still, while the classical wide neighborhood primal-dual interior point algorithms have only the O(nL-iteration complexity. We also proved that the algorithms are quadratic convergence if the optimal vertex is nondegenerate. Finally, we show some computational results of our algorithms.
基金supported by the Knut and Alice Wallenberg Foundationthe Swedish Foundation for Strategic Research+1 种基金the Swedish Research Councilthe National Natural Science Foundation of China(62133003,61991403,61991404,61991400)。
文摘The distributed nonconvex optimization problem of minimizing a global cost function formed by a sum of n local cost functions by using local information exchange is considered.This problem is an important component of many machine learning techniques with data parallelism,such as deep learning and federated learning.We propose a distributed primal-dual stochastic gradient descent(SGD)algorithm,suitable for arbitrarily connected communication networks and any smooth(possibly nonconvex)cost functions.We show that the proposed algorithm achieves the linear speedup convergence rate O(1/(√nT))for general nonconvex cost functions and the linear speedup convergence rate O(1/(nT)) when the global cost function satisfies the Polyak-Lojasiewicz(P-L)condition,where T is the total number of iterations.We also show that the output of the proposed algorithm with constant parameters linearly converges to a neighborhood of a global optimum.We demonstrate through numerical experiments the efficiency of our algorithm in comparison with the baseline centralized SGD and recently proposed distributed SGD algorithms.
基金supported by the National Key Research and Development Program of China(No.2022YFB1902700)the Joint Fund of Ministry of Education for Equipment Pre-research(No.8091B042203)+5 种基金the National Natural Science Foundation of China(No.11875129)the Fund of the State Key Laboratory of Intense Pulsed Radiation Simulation and Effect(No.SKLIPR1810)the Fund of Innovation Center of Radiation Application(No.KFZC2020020402)the Fund of the State Key Laboratory of Nuclear Physics and Technology,Peking University(No.NPT2023KFY06)the Joint Innovation Fund of China National Uranium Co.,Ltd.,State Key Laboratory of Nuclear Resources and Environment,East China University of Technology(No.2022NRE-LH-02)the Fundamental Research Funds for the Central Universities(No.2023JG001).
文摘Neutron computed tomography(NCT)is widely used as a noninvasive measurement technique in nuclear engineering,thermal hydraulics,and cultural heritage.The neutron source intensity of NCT is usually low and the scan time is long,resulting in a projection image containing severe noise.To reduce the scanning time and increase the image reconstruction quality,an effective reconstruction algorithm must be selected.In CT image reconstruction,the reconstruction algorithms can be divided into three categories:analytical algorithms,iterative algorithms,and deep learning.Because the analytical algorithm requires complete projection data,it is not suitable for reconstruction in harsh environments,such as strong radia-tion,high temperature,and high pressure.Deep learning requires large amounts of data and complex models,which cannot be easily deployed,as well as has a high computational complexity and poor interpretability.Therefore,this paper proposes the OS-SART-PDTV iterative algorithm,which uses the ordered subset simultaneous algebraic reconstruction technique(OS-SART)algorithm to reconstruct the image and the first-order primal–dual algorithm to solve the total variation(PDTV),for sparse-view NCT three-dimensional reconstruction.The novel algorithm was compared with other algorithms(FBP,OS-SART-TV,OS-SART-AwTV,and OS-SART-FGPTV)by simulating the experimental data and actual neutron projection experiments.The reconstruction results demonstrate that the proposed algorithm outperforms the FBP,OS-SART-TV,OS-SART-AwTV,and OS-SART-FGPTV algorithms in terms of preserving edge structure,denoising,and suppressing artifacts.
基金supported by National Natural Science Foundation of China(Grant Nos.1136103011271049 and 11271049)+5 种基金the Project Sponsored by the Scientific Research Foundation for the Returned Overseas Chinese ScholarsState Education Ministry(Grant Nos.CUHK400412HKBU502814211911and 12302714)Hong Kong Research Grants Council(Grant No.Ao E/M-05/12)FRGs of Hong Kong Baptist University
文摘We consider the problem of restoring images corrupted by Poisson noise. Under the framework of maximum a posteriori estimator, the problem can be converted into a minimization problem where the objective function is composed of a Kullback-Leibler(KL)-divergence term for the Poisson noise and a total variation(TV) regularization term. Due to the logarithm function in the KL-divergence term, the non-differentiability of TV term and the positivity constraint on the images, it is not easy to design stable and efficiency algorithm for the problem. Recently, many researchers proposed to solve the problem by alternating direction method of multipliers(ADMM). Since the approach introduces some auxiliary variables and requires the solution of some linear systems, the iterative procedure can be complicated. Here we formulate the problem as two new constrained minimax problems and solve them by Chambolle-Pock's first order primal-dual approach. The convergence of our approach is guaranteed by their theory. Comparing with ADMM approaches, our approach requires about half of the auxiliary variables and is matrix-inversion free. Numerical results show that our proposed algorithms are efficient and outperform the ADMM approach.
基金Project supported by the National Natural Science Foundation of China （Grant No. 10117733）, the Shanghai Leading Academic Discipline Project （Grant No.J50101）, and the Foundation of Scientific Research for Selecting and Cultivating Young Excellent University Teachers in Shanghai （Grant No.06XPYQ52）
文摘Interior-point methods （IPMs） for linear optimization （LO） and semidefinite optimization （SDO） have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with simple algebraic expression is proposed. Based on this kernel function, a primal-dual interior-point methods （IPMs） for semidefinite optimization （SDO） is designed. And the iteration complexity of the algorithm as O（n^3/4 log n/ε） with large-updates is established. The resulting bound is better than the classical kernel function, with its iteration complexity O（n log n/ε） in large-updates case.
基金The work was supported in part by the National Natural Science Foundation of China(Grant No.12071417)。
文摘In this paper,we consider the-prize-collecting minimum vertex cover problem with submodular penalties,which generalizes the well-known minimum vertex cover problem,minimum partial vertex cover problem and minimum vertex cover problem with submodular penalties.We are given a cost graph and an integer.This problem determines a vertex set such that covers at least edges.The objective is to minimize the total cost of the vertices in plus the penalty of the uncovered edge set,where the penalty is determined by a submodular function.We design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the problem.When the submodular penalty cost function is normalized and nondecreasing,the proposed algorithm has an approximation factor of.When the submodular penalty cost function is linear,the approximation factor of the proposed algorithm is reduced to,which is the best factor if the unique game conjecture holds.
基金supported by the National Natural Science Foundation of China (Grant No.62176218)the Fundamental Research Funds for the Central Universities (Grant No.XDJK2020TY003)。
文摘This paper investigates two distributed accelerated primal-dual neurodynamic approaches over undirected connected graphs for resource allocation problems(RAP)where the objective functions are generally convex.With the help of projection operators,a primal-dual framework,and Nesterov's accelerated method,we first design a distributed accelerated primal-dual projection neurodynamic approach(DAPDP),and its convergence rate of the primal-dual gap is O(1/(t^(2)))by selecting appropriate parameters and initial values.Then,when the local closed convex sets are convex inequalities which have no closed-form solutions of their projection operators,we further propose a distributed accelerated penalty primal-dual neurodynamic approach(DAPPD)on the strength of the penalty method,primal-dual framework,and Nesterov's accelerated method.Based on the above analysis,we prove that DAPPD also has a convergence rate O(1/(t^(2)))of the primal-dual gap.Compared with the distributed dynamical approaches based on the classical primal-dual framework,our proposed distributed accelerated neurodynamic approaches have faster convergence rates.Numerical simulations demonstrate that our proposed neurodynamic approaches are feasible and effective.
文摘Color image segmentation is crucial in image processing and computer vision.Most traditional segmentation methods simply regard an RGB color image as the direct combination of the three monochrome images and ignore the inherent color structures within channels,which contain some key feature information of the image.To better describe the relationship of color channels,we introduce a quaternion-based regularization that can reflect the image characteristics more intuitively.Our model combines the idea of the Mumford-Shah model-based two-stage segmentation method and the Saturation-Value Total Variation regularization for color image segmentation.The new strategy first extracts features from the color image and then subdivides the image in a new color feature space which achieves better performance than methods in RGB color space.Moreover,to accelerate the optimization process,we use a new primal-dual algorithm to solve our novel model.Numerical results demonstrate clearly that the performance of our proposed method is excellent.
基金supported by the National Natural Science Foundation of China under Grant No.61973043。
文摘This paper studies the distributed optimization problem when the objective functions might be nondifferentiable and subject to heterogeneous set constraints.Unlike existing subgradient methods,the authors focus on the case when the exact subgradients of the local objective functions can not be accessed by the agents.To solve this problem,the authors propose a projected primaldual dynamics using only the objective function’s approximate subgradients.The authors first prove that the formulated optimization problem can generally be solved with an error depending upon the accuracy of the available subgradients.Then,the authors show the exact solvability of this distributed optimization problem when the accumulated approximation error of inexact subgradients is not too large.After that,the authors also give a novel componentwise normalized variant to improve the transient behavior of the convergent sequence.The effectiveness of the proposed algorithms is verified by a numerical example.
基金This work was supported by the National Natural Science Foundation of China(No.11971146)the Natural Science Foundation of Hebei Province of China(Nos.A2019205089 and A2019205092)+1 种基金Hebei Province Foundation for Returnees(No.CL201714)Overseas Expertise Introduction Program of Hebei Auspices(No.25305008).
文摘In this paper,we consider the P-prize-collecting set cover(P-PCSC)problem,which is a generalization of the set cover problem.In this problem,we are given a set system(U,S),where U is a ground set and S⊆2U is a collection of subsets satisfying∪S∈SS=U.Every subset in S has a nonnegative cost,and every element in U has a nonnegative penalty cost and a nonnegative profit.Our goal is to find a subcollection C⊆S such that the total cost,consisting of the cost of subsets in C and the penalty cost of the elements not covered by C,is minimized and at the same time the combined profit of the elements covered by C is at least P,a specified profit bound.Our main work is to obtain a 2f+ε-approximation algorithm for the P-PCSC problem by using the primal-dual and Lagrangian relaxation methods,where f is the maximum frequency of an element in the given set system(U,S)andεis a fixed positive number.
