Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
Fengmin Wang Dachuan Xu Donglei Du Chenchen Wu
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
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]