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.
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.
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.
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.
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.
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.
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.
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$.
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.
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$.
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.
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.
Multi-instance learning is a special kind of machine learning problem, has received extensive attention and been researched on in recent years. Many different types of multi-instance learning algorithms have been proposed to deal with practical problems in various fields. This paper reviews the algorithm research and application of multi-instance learning in detail, introduces various background assumptions， and introduces multi-instance learning from three aspects: instance level, bag level, and embedded space. Finally we provide the algorithm extensions and major applications in several areas.
This paper considers the monotone variational inequality problems with two separable blocks subject to linear coupling constraints. Problems of this type arise in many contemporary applications including traffic assignment and economics. Based on its favorable separable structure, splitting type methods have been studied. In this paper, we introduce a new inexact parallel alternating direction method with a substitution to solve this family of problems. At each iteration, one can get a predictor by using projection in parallel fashion, then corrects the predictor to generate the new iterate. For the proposed algorithm, we prove its convergence under mild conditions via the analytic framework of contractive type methods. Some numerical results are reported to support the efficiency of the new method. Moreover, the proposed method can be extended to solve the variational inequality problems with multi-blocks.
The k-means problem which is one of the classical NP-hard problems keeps attracting wide attention in combinatorial optimization and computer science area since been proposed. Given a set of observations consisting of N d-dimensional real vectors, the objective is to partition the N observations into k(\leqslant N) sets, so as to minimize the within-cluster sum of squares, where the center of a cluster is defined as the mean of all the observations in it. As one of the heuristic algorithms for solving k-means problem, k-means algorithm is quite popular in practice because of its excellent perform of convergence. The k-means algorithm can be described as: given initial solution for k-means problem, repeat assignment (assign observations to its nearest center) and update (compute the new centers in the new clusters) step until convergence to a solution. Although the algorithm is usually considered as linearly convergency, its shortcomings are obvious. The k-means algorithm is unable to ensure the global optimality and the output is rely badly on the choice of initial solutions. Therefore, variants of initialization methods are proposed to improve the performance of the k-means algorithm. In this paper we mainly filter and list some of them for readers.
In this paper, two factorizations for fourth-order tensors based on different multiplications of the fourth-order tensors are investigated. One is, called as F-TD, based on the fourth-order tensor multiplication (F-product). Another is, the fourth-order tensor multiplication and decomposition are defined, called as B-product and FT-SVD, based on the t-product of the third-order tensor multiplication. Meanwhile, two tensor approximation theorems are present using two decomposition methods. Finally, three numerical examples are given to demonstrate the accuracy and the feasibility of our proposed methods.
Nonparallel support vector machine (NSVM) is the extension of support vector machine (SVM), and it has been widely studied in recent years. The NSVM constructs nonparallel support hyperplanes for each class, which can describe the distribution of different classes, thus applicable to wider problems. However, the study of the relationship between NSVM and SVM is rarely. And to now, there is no NSVM could be degenerate or equivalent to the standard SVM. We start from this view of point, and construct a new NSVM model. Our model not only can be reduced to the standard SVM, preserves the sparsity and kernel scalability, but also can describe the distribution of the different classes. At last, we compare our model with start-of-art SVMs and NSVMs on benchmark datasets, and confirm the superiority of proposed NSVM.
In this paper, we consider a class of semi-supervised metric learning problems. Due to the explosion in size and complexity of datasets, it is increasingly important to consider the sparse of metric learning. We add the constraint of sparse for the model of semi-supervised metric learning. To be easy to deal with the sparse constraint, we apply the Frobenius norm to define the sparse and transform it into the objective function of model by using the penalty parameter. Next we present an accelerated projection gradient algorithm, which is originally designed for convex smooth optimization in Euclidean space, over a positive definite matrix group. We analyze the convergence of our algorithm. Finally, we show the numerical test to demonstrate the effectiveness of the proposed algorithm.
Based on the alternating direction method of multipliers (ADMM) and the sequential quadratic programming (SQP) method, this paper proposes a new efficient algorithm for two blocks nonconvex optimization with linear constrained. Firstly, taking SQP thought as the main line, the quadratic programming (QP) is decomposed into two independent small scale QP according to ADMM idea. Secondly, the new iteration point of the prime variable is generated by Armijo line search for the augmented Lagrange function. Finally, the dual variables are updated by an explicit expression. Thus, a new ADMM-SQP algorithm is constructed. Under the weaker conditions, the global convergence of the algorithm is analyzed. Some preliminary numerical results are reported to support the efficiency of the new algorithm.
Facility location game is one of important research areas in the forefront of algorithmic game theory. Different with the traditional facility problem, there are $n$ selfish agents in game and the addresses where they are located are private information. The game designer tries to design a mechanism, which outputs the locations of facilities according to the reported addresses of agents. One of the most important objectives in the study of facility location game is to design approximation strategy-proof or group strategy-proof mechanisms without money in order to enforce all agents to choose strategies faithfully and to achieve the overall equlibria. Mechanism design without money for the facility location game is an interdisciplinary project with topics in the common part of combinatorial optimization and theoretical computer science, which has important applications in a few practical areas such as management science, information science, social economics, etc. This survey aims at listing the recent results on the approximation mechanism design without money for facility location games from different perspectives of agent preferences, facility types, metric spaces and social objectives, and summarizes some problems which have not been solved for readers.
