Table of Content

15 September 2022, Volume 26 Issue 3

Previous Issue    Next Issue

A survey of differential privacy algorithms for the $k$-means problem

Fan YUAN, Dachuan XU, Dongmei ZHANG

2022, 26(3):  1-16.  doi:10.15960/j.cnki.issn.1007-6093.2022.03.001

Asbtract ( 7581 )   HTML ( 826)   PDF (993KB) ( 1124 )  

Figures and Tables | References | Related Articles | Metrics

The $k$-means problem is a very important problem in the field of machine learning and combinatorial optimization. It is a classic NP-hard problem, which is widely used in data mining, business production decision-making, image processing, biomedical technology, and more. As people in these fields pay more and more attention to personal privacy protection, which raises a question: In the case that decisions are usually made by artificial intelligence algorithms, how to ensure that as much information as possible is extracted from the data without revealing personal privacy? In the past ten years, experts and scholars have continuously studied and explored the $k$-means problem with privacy protection, and has also obtained many results with theoretical guiding significance and practical application value. In this paper we mainly introduce these differential privacy algorithms of the $k$-means problem for readers.

Optimization model and algorithm for Online to Offline dynamic take-out delivery routing problem centered on business districts

Chenghao ZHOU, Boxuan LYU, Hanyu ZHOU, Haiyan LU

2022, 26(3):  17-30.  doi:10.15960/j.cnki.issn.1007-6093.2022.03.002

Asbtract ( 7586 )   HTML ( 526)   PDF (1042KB) ( 950 )  

Figures and Tables | References | Related Articles | Metrics

In the take-out food industry, improper path planning by couriers often leads to low delivery efficiency. Most of the existing VRP research focuses on the optimization of express delivery and other industries, and there is a lack of optimization algorithm research for the food delivery with real-time characteristics. Aiming at the Online to Offline (O2O) take-out delivery routing optimization problem, this paper takes a comprehensive consideration of its dynamic delivery requirements, cargo differentiation and other characteristics as well as constraints such as time windows and cargo capacities, and establishes an O2O dynamic route optimization model of the take-out delivery personnel, in which the business districts are regarded as a delivery centre, and the number of delivery personnel and the total travel time by the delivery personnel are taken as the minimization targets. Using the method of periodically processing new orders, the resultant dynamic adjustment problem of the delivery personnel's route is converted into a series of static TSP sub-problems and thereby a phased heuristic real-time delivery routing optimization algorithm framework is designed, and a concrete algorithm and a numerical example are given. A set of test cases centered on business districts is generated on the basis of a number of widely used VRP instances, the algorithm is tested through simulation experiment and compared with other algorithms. The results show that the algorithm proposed in this paper can make full use of the delivery personnel near the location of the new orders to conduct the delivery, optimize the corresponding delivery route, and effectively reduce the number of delivery personnel for delivery and the total travel time by the delivery personnel.

A tensor completion method based on tensor train decomposition and its application in image restoration

Wenhui XIE, Chen LING, Chenjian PAN

2022, 26(3):  31-43.  doi:10.15960/j.cnki.issn.1007-6093.2022.03.003

Asbtract ( 7332 )   HTML ( 65)   PDF (3899KB) ( 704 )  

Figures and Tables | References | Related Articles | Metrics

Low-rank tensor completion is widely used in data recovery, and the tensor completion model based on tensor train (TT) decomposition works well in color image, video and internet data recovery. This paper proposes a tensor completion model based on the third-order tensor TT decomposition. In this model, the sparse regularization and the spatio-temporal regularization are introduced to characterize the sparsity of the kernel tensor and the inherent block similarity of the data, respectively. According to the structural characteristics of the problem, some auxiliary variables are introduced to convert the original model into a separable form equivalently, and the method of combining proximal alternating minimization (PAM) and alternating direction multiplier method (ADMM) is used to solve the model. Numerical experiments show that the introduction of two regular terms is beneficial to improve the stability and practical effect of data recovery, and the proposed method is superior to other methods. When the sampling rate is low or the image is structurally missing, the presented method is more effective.

The bounded inverse optimal value problem on minimum spanning tree under unit infinity norm

Binwu ZHANG, Xiucui GUAN

2022, 26(3):  44-56.  doi:10.15960/j.cnki.issn.1007-6093.2022.03.004

Asbtract ( 7129 )   HTML ( 45)   PDF (888KB) ( 512 )  

References | Related Articles | Metrics

We consider the bounded inverse optimal value problem on minimum spanning tree under unit $l_{\infty}$ norm. Given an edge weighted connected undirected network $G=(V, E, w)$, a spanning tree $T^0$, a lower bound vector $\bm{l}$, an upper bound vector $\bm{u}$ and a value $K$, we aim to obtain a new weight vector $\bm{\bar{w}}$ satisfying the lower and upper bounds such that $T^0$ is a minimum spanning tree under the vector $\bm{\bar{w}}$ with weight $K$. The objective is to minimize the modification cost under unit $l_{\infty}$ norm. We present a mathematical model of the problem. After analyzing optimality conditions of the problem, we develop an $O(|V||E|)$ strongly polynomial time algorithm.

Maximum matching based approximation algorithms for precedence constrained scheduling problems

An ZHANG, Yong CHEN, Guangting CHEN, Zhanwen CHEN, Qiaojun SHU, Guohui LIN

2022, 26(3):  57-74.  doi:10.15960/j.cnki.issn.1007-6093.2022.03.005

Asbtract ( 2156 )   HTML ( 296)   PDF (902KB) ( 181 )  

Figures and Tables | References | Related Articles | Metrics

We investigate the problem to schedule a set of precedence constrained jobs of unit size on an open-shop or on a flow-shop to minimize the makespan. The precedence constraints among the jobs are presented as a directed acyclic graph called the precedence graph. When the number of machines in the shop is part of the input, both problems are strongly NP-hard on general precedence graphs, but were proven polynomial-time solvable for some special precedence graphs such as intrees. In this paper, we characterize improved lower bounds on the minimum makespan in terms of the number of agreeable pairings among certain jobs and propose approximation algorithms based on a maximum matching among these jobs, so that every agreeable pair of jobs can be processed on different machines simultaneously. For open-shop with an arbitrary precedence graph and for flow-shop with a spine precedence graph, both achieved approximation ratios are $2 - \frac 2m$, where $m$ is the number of machines in the shop.

Sharing bicycle relocating with minimum carbon emission

Bing SU, Wyatt CARLSON, Jiabin FAN, Arthur GAO, Yanjun SHAO, Guohui LIN

2022, 26(3):  75-91.  doi:10.15960/j.cnki.issn.1007-6093.2022.03.006

Asbtract ( 2194 )   HTML ( 47)   PDF (1155KB) ( 303 )  

Figures and Tables | References | Related Articles | Metrics

We formulate the sharing bicycle relocating practice as a novel optimization problem, which can be regarded as a variant of the classic TSP problem while its objective function is no longer the length of the Hamiltonian tour but the carbon emission. A well-adopted carbon emission formula that is the product of the load of the vehicle and the travel distance is employed and we propose two heuristic algorithms Greedy and TSP-based, inside both of which we set the priority to reduce the load of the vehicle for minimizing carbon emission. The feasibility of both algorithms is proven and numerical experiments are conducted to validate their performance empirically. The promise of Greedy over TSP-based algorithm is shown to the sharing bicycle companies for their daily dispatching practice.

On the worst-case ratio of algorithm SPT for two uniform machines scheduling with minisum criteria

Mingyang GONG, Zhiyi TAN, Yujie YAN

2022, 26(3):  92-108.  doi:10.15960/j.cnki.issn.1007-6093.2022.03.007

Asbtract ( 2107 )   HTML ( 13)   PDF (821KB) ( 179 )  

Figures and Tables | References | Related Articles | Metrics

This paper studies the scheduling problem on two uniform machines with objective of minimizing the total completion time. The parametric worst-case ratio of the algorithm SPT is investigated. The gap between the overall upper bound and lower bound decreases from 0.430 5 to 0.014 7.

Tight Price of Anarchy for selfish task scheduling on two selfish machines

Xiayan CHENG, Yin HE, Congcong ZHAO, Rongheng LI

2022, 26(3):  109-119.  doi:10.15960/j.cnki.issn.1007-6093.2022.03.008

Asbtract ( 2009 )   HTML ( 13)   PDF (783KB) ( 99 )  

Figures and Tables | References | Related Articles | Metrics

In this paper, we study selfish task scheduling on two selfish machines with respect to Dual Equilibrium, called Dual Equilibrium Schedule. For any job list $L$, we show that the Price of Anarchy of Dual Equilibrium Schedule is $\frac{8}{7}$. If the job sizes are constrained in $[1, r](r\ge1)$, this research states that the tight PoA(Price of Anarchy) of Dual Equilibrium Schedule is a piecewise linear function of $r$.

Manufacturer channel rebate strategies with customer experience under new product supply chain

Chunming XU, Chenchen WU, Baiyun YUAN

2022, 26(3):  120-132.  doi:10.15960/j.cnki.issn.1007-6093.2022.03.009

Asbtract ( 2172 )   HTML ( 22)   PDF (2172KB) ( 235 )  

Figures and Tables | References | Related Articles | Metrics

With the advent of experience economy and the competition of new product, it is important for manufacturers to build channel distribution and brand promotion based on the customer experience. In this paper, considering the customer experience factor and the retailer's investment in the experience, offline and online demand models are firstly developed in the new product supply chain, respectively. The manufacturer-led supply chain with the contracts of the wholesale price and the channel rebate are discussed. Furthermore, the characteristics of the equilibrium solution of each decision-maker in the supply chain are analyzed, and the comparisons of the optimality based on the above models are made. Finally, the effects of the manufacturer's rebate point, the retailer's experience investment level, the customer's experience factor, the travel cost and the willingness-to-pay on the optimal performance of supply chain are explored in the numerical examples.

Approximation algorithm for mixed batch scheduling on identical machines for jobs with arbitrary sizes

Dong WANG, Ganggang LI, Wenchang LUO

2022, 26(3):  133-142.  doi:10.15960/j.cnki.issn.1007-6093.2022.03.010

Asbtract ( 2066 )   HTML ( 18)   PDF (840KB) ( 225 )  

References | Related Articles | Metrics

In this paper, we consider the mixed batch scheduling problem in which a set of jobs with arbitrary sizes should be processed on identical batch machines with identical capacities. Each job has its processing time and size. Each machine can process a group of jobs as a batch simultaneously, as long as the total size of the jobs in this batch does not exceed the capacity of the machine. For a given batch, its processing time is equal to the weighted sum of the maximum processing time and the total processing time of jobs in the batch. The objective function is to minimize the makespan. The problem includes the one-dimension bin packing problem as its special case, which is strongly NP-hard. For the studied problem, we provide an approximation algorithm with performance ratio of $\left( {2 +2\alpha+\alpha^{2}} \right)$, where $\alpha$ is a given parameter for weight with $0\leq\alpha\leq 1$.

Randomized approximation algorithms for a class of one-dimensional online unit clustering problem

Yubo DAI, Yihong DUAN, Longcheng LIU, Zihao WANG

2022, 26(3):  143-150.  doi:10.15960/j.cnki.issn.1007-6093.2022.03.011

Asbtract ( 2040 )   HTML ( 10)   PDF (766KB) ( 114 )  

References | Related Articles | Metrics

In a given metric space, the unit clustering problem is to find a minimum number of unit balls to cover all the given points. It is a well known combinatorial optimization problem and the online version is: Given a set of n points in a given metric space, which arrive one by one at any locations, the point should be assigned to a unit cluster at the time of its arrival without any future information, the goal is to minimize the number of used clusters. In this paper, we consider a class of online unit clustering problem in one dimension with the assumption that the distance between any two adjacent clusters in the offline optimal solution is greater than 0.5. We first present two online algorithms with some lemmas, and then present a combined randomized algorithm which run the two online algorithms with a probability 0.5. We show that the expected competitive ratio of the combined randomized algorithm is at most 1.5.

LPT heuristic for parallel-machine scheduling of maximizing total early work

Ping ZHOU, Min JI, Yiwei JIANG

2022, 26(3):  151-156.  doi:10.15960/j.cnki.issn.1007-6093.2022.03.012

Asbtract ( 2118 )   HTML ( 14)   PDF (744KB) ( 184 )  

Figures and Tables | References | Related Articles | Metrics

This paper considers the problem of scheduling on three identical machines with a common due date. The preemption is not allowed. The goal is to maximize the total early work of all the jobs, i.e., the total processing time of all the jobs (or part) completed before the common due date. Since the problem is NP-hard, we apply the classical heuristic, namely longest processing time (LPT), to tackle the problem. We show that the worst-case ratio of LPT is at most $\frac{15}{13}$ and the lower bound of the worst-case ratio is at least $\frac{27}{25}$ by providing an instance.