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
An adaptive probabilistic algorithm for online k-center clustering
Ruiqi Yang Dachuan Xu Yicheng Xu Dongmei Zhang

The $k$-center clustering is one of the well-studied clustering problems in computer science. We are given a set of data points $P\subseteq R^d$, where $R^d$ is $d$ dimensional Euclidean space. We need to select $k≤ |P|$ points as centers and partition the set $P$ into $k$ clusters with each point connecting to its nearest center. The goal is to minimize the maximum radius. We consider the so-called online $k$-center clustering model where the data points in $R^d$ arrive over time. We present the bi-criteria $(\frac{n}{k}, (\log\frac{U^*}{L^*})^2)$-competitive algorithm and $(\frac{n}{k}, \logγ\log\frac{nγ}{k})$-competitive algorithm for semi-online and fully-online $k$-center clustering respectively, where $U^*$ is the maximum cluster radius of optimal solution, $L^*$ is the minimum distance of two distinct points of $P$, $γ$ is the ratio of the maximum distance of two distinct points and the minimum distance of two distinct points of $P$ and $n$ is the number of points that will arrive in total.

keywords: k-center online clustering probabilistic 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
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
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
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]