Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
Fengmin Wang Dachuan Xu Donglei Du Chenchen Wu
Numerical Algebra, Control & Optimization 2015, 5(2): 91-100 doi: 10.3934/naco.2015.5.91
We introduce two set cover problems with submodular costs and linear/submodular penalties and offer two approximation algorithms of ratios $\eta$ and $2\eta$ respectively via the primal-dual technique, where $\eta$ is the largest number of sets that each element belongs to.
keywords: primal-dual. penalties submodular cost Set cover approximation algorithm
An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation
Chenchen Wu Dachuan Xu Xin-Yuan Zhao
Journal of Industrial & Management Optimization 2012, 8(1): 117-126 doi: 10.3934/jimo.2012.8.117
In this paper, we consider the $2$-catalog segmentation problem. For the disjoint version, we propose an approximation algorithm based on the non-uniform rotation technique using a semidefinite programming ($SDP$) relaxation. We give the performance curve depending on the ratio between the value of optimal SDP solution and the total weight. In this curve, the lowest point implies the approximation ratio is $0.7317$ which is the best ratio for the disjoint version until now. We also consider the performance curve of the joint version.
keywords: approximation algorithm semidefinite programming. 2-catalog segmentation problem

Year of publication

Related Authors

Related Keywords

[Back to Top]