JIMO
The warehouse-retailer network design game
Gaidi Li Jiating Shao Dachuan Xu Wen-Qing Xu
In this paper, we consider the warehouse-retailer network design game based on the warehouse-retailer network design problem (WRND) proposed by Teo and Shu (2004). By carefully defining the generalized distance function, we present a cost-sharing method for the warehouse-retailer network design game. We show that the proposed cost-sharing scheme is cross-monotonic, competitive, and $3$-approximate cost recovery.
keywords: approximate cost recovery. cost-sharing method Warehouse-retailer network design
JIMO
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
JIMO
An approximation algorithm for the $k$-level facility location problem with submodular penalties
Gaidi Li Zhen Wang Dachuan Xu
In this paper, we consider the $k$-level facility location problem with submodular penalties ($k$-FLPSP). We propose a primal-dual $6$-approximation (combinatorial) algorithm for the $k$-FLPSP.
keywords: submodular. approximation algorithm primal-dual Facility location combinatorial algorithm
NACO
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
JIMO
Approximate algorithms for unrelated machine scheduling to minimize makespan
Xianzhao Zhang Dachuan Xu Donglei Du Cuixia Miao
We study two unrelated machine scheduling problems with machine dependent release dates to minimize the makespan. For the case with fixed processing time where processing job $j$ on machine $i$ requires time $p_{ij}$ and incurs a cost of $c_{ij}$, we derive a $2$-approximation algorithm. For the problem with variable processing times where the cost increases linearly as the processing time decreases, we propose a $(2+\epsilon)$-approximation algorithm.
keywords: Scheduling linear programming rounding. unrelated parallel machine approximation algorithm

Year of publication

Related Authors

Related Keywords

[Back to Top]