The warehouse-retailer network design game
Gaidi Li Jiating Shao Dachuan Xu Wen-Qing Xu
Journal of Industrial & Management Optimization 2015, 11(1): 291-305 doi: 10.3934/jimo.2015.11.291
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
Journal of Industrial & Management Optimization 2018, 13(5): 1-12 doi: 10.3934/jimo.2018057

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
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
An approximation algorithm for the $k$-level facility location problem with submodular penalties
Gaidi Li Zhen Wang Dachuan Xu
Journal of Industrial & Management Optimization 2012, 8(3): 521-529 doi: 10.3934/jimo.2012.8.521
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
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
Approximate algorithms for unrelated machine scheduling to minimize makespan
Xianzhao Zhang Dachuan Xu Donglei Du Cuixia Miao
Journal of Industrial & Management Optimization 2016, 12(2): 771-779 doi: 10.3934/jimo.2016.12.771
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]