A heuristic for the time constrained asymmetric linear sum assignment problem

The linear sum assignment problem is a fundamental combinatorial optimisation problem and can be broadly defined as: given an \(n \times m, m \ge n\) benefit matrix \(B = (b_{ij})\), matching each row to a different column so that the sum of entries at the row-column intersections is maximised. This paper describes the application of a new fast heuristic algorithm, Asymmetric Greedy Search, to the asymmetric version (\(n \ne m\)) of the linear sum assignment problem. Extensive computational experiments, using a range of model graphs demonstrate the effectiveness of the algorithm. The heuristic was also incorporated within an algorithm for the non-sequential protein structure matching problem where non-sequential alignment between two proteins, normally of different numbers of amino acids, needs to be maximised.     

Online MapReduce scheduling problem of minimizing the makespan

MapReduce system is a popular big data processing framework, and the performance of it is closely related to the efficiency of the centralized scheduler. In practice, the centralized scheduler often has little information in advance, which means each job may be known only after being released. In this paper, hence, we consider the online MapReduce scheduling problem of minimizing the makespan, where jobs are released over time. Both preemptive and non-preemptive version of the problem are considered. In addition, we assume that reduce tasks cannot be parallelized because they are often complex and hard to be decomposed. For the non-preemptive version, we prove the lower bound is \(\frac{m+m(\Psi (m)-\Psi (k))}{k+m(\Psi (m)-\Psi (k))}\), higher than the basic online machine scheduling problem, where k is the root of the equation \(k=\big \lfloor {\frac{m-k}{1+\Psi (m)-\Psi (k)}+1 }\big \rfloor \) and m is the quantity of machines. Then we devise an \((2-\frac{1}{m})\)-competitive online algorithm called MF-LPT (Map First-Longest Processing Time) based on the LPT. For the preemptive version, we present a 1-competitive algorithm for two machines.     

On nonlinear multi-covering problems

In this paper we define the exact k-coverage problem, and study it for the special cases of intervals and circular-arcs. Given a set system consisting of a ground set of n points with integer demands \(\{d_0,\dots ,d_{n-1}\}\) and integer rewards, subsets of points, and an integer k, select up to k subsets such that the sum of rewards of the covered points is maximized, where point i is covered if exactly \(d_i\) subsets containing it are selected. Here we study this problem and some related optimization problems. We prove that the exact k-coverage problem with unbounded demands is NP-hard even for intervals on the real line and unit rewards. Our NP-hardness proof uses instances where some of the natural parameters of the problem are unbounded (each of these parameters is linear in the number of points). We show that this property is essential, as if we restrict (at least) one of these parameters to be a constant, then the problem is polynomial time solvable. Our polynomial time algorithms are given for various generalizations of the problem (in the setting where one of the parameters is a constant).     

Neighbor sum distinguishing index of 2-degenerate graphs

We consider proper edge colorings of a graph G using colors in \(\{1,\ldots ,k\}\). Such a coloring is called neighbor sum distinguishing if for each pair of adjacent vertices u and v, the sum of the colors of the edges incident with u is different from the sum of the colors of the edges incident with v. The smallest value of k in such a coloring of G is denoted by \({\mathrm ndi}_{\Sigma }(G)\). In this paper we show that if G is a 2-degenerate graph without isolated edges, then \({\mathrm ndi}_{\Sigma }(G)\le \max \{\Delta (G)+2,7\}\).     

Multiple facility location on a network with linear reliability order of edges

We study the problem of locating facilities on the nodes of a network to maximize the expected demand serviced. The edges of the input graph are subject to random failure due to a disruptive event. We consider a special type of failure correlation. The edge dependency model assumes that the failure of a more reliable edge implies the failure of all less reliable ones. Under this dependency model called Linear Reliability Order (LRO) we give two polynomial time exact algorithms. When two distinct LRO’s exist, we prove the total unimodularity of a linear programming formulation. In addition, we show that minimizing the sum of facility opening costs and expected cost of unserviced demand under two orderings reduces to a matching problem. We prove NP-hardness of the three orderings case and show that the problem with an arbitrary number of orderings generalizes the deterministic maximum coverage problem. When a demand point can be covered only if a facility exists within a distance limit, we show that the problem is NP-hard even for a single ordering.     

On global integer extrema of real-valued box-constrained multivariate quadratic functions

Determining global integer extrema of an real-valued box-constrained multivariate quadratic functions is a very difficult task. In this paper, we present an analytic method, which is based on a combinatorial optimization approach in order to calculate global integer extrema of a real-valued box-constrained multivariate quadratic function, whereby this problem will be proven to be as NP-hard via solving it by a Travelling Salesman instance. Instead, we solve it using eigenvalue theory, which allows us to calculate the eigenvalues of an arbitrary symmetric matrix using Newton’s method, which converges quadratically and in addition yields a Jordan normal form with \(1 \times 1\)-blocks, from which a special representation of the multivariate quadratic function based on affine linear functions can be derived. Finally, global integer minimizers can be calculated dynamically and efficiently most often in a small amount of time using the Fourier–Motzkin- and a Branch and Bound like Dijkstra-algorithm. As an application, we consider a box-constrained bivariate and multivariate quadratic function with ten arguments.     

Hamiltonian numbers in oriented graphs

A hamiltonian walk of a digraph is a closed spanning directed walk with minimum length in the digraph. The length of a hamiltonian walk in a digraph D is called the hamiltonian number of D, denoted by h(D). In Chang and Tong (J Comb Optim 25:694–701, 2013), Chang and Tong proved that for a strongly connected digraph D of order n, \(n\le h(D)\le \lfloor \frac{(n+1)^2}{4} \rfloor \), and characterized the strongly connected digraphs of order n with hamiltonian number \(\lfloor \frac{(n+1)^2}{4} \rfloor \). In the paper, we characterized the strongly connected digraphs of order n with hamiltonian number \(\lfloor \frac{(n+1)^2}{4} \rfloor -1\) and show that for any triple of integers n, k and t with \(n\ge 5\), \(n\ge k\ge 3\) and \(t\ge 0\), there is a class of nonisomorphic digraphs with order n and hamiltonian number \(n(n-k+1)-t\).     

An optimal online algorithm for the parallel-batch scheduling with job processing time compatibilities

We consider the online (over time) scheduling on a single unbounded parallel-batch machine with job processing time compatibilities to minimize makespan. In the problem, a constant \(\alpha >0\) is given in advance. Each job \(J_{j}\) has a normal processing time \(p_j\). Two jobs \(J_i\) and \(J_j\) are compatible if \(\max \{p_i, p_j\} \le (1+\alpha )\cdot \min \{p_i, p_j\}\). In the problem, mutually compatible jobs can form a batch being processed on the machine. The processing time of a batch is equal to the maximum normal processing time of the jobs in this batch. For this problem, we provide an optimal online algorithm with a competitive ratio of \(1+\beta _\alpha \), where \(\beta _\alpha \) is the positive root of the equation \((1+\alpha )x^{2}+\alpha x=1+\alpha \).     

A lower bound for the adaptive two-echelon capacitated vehicle routing problem

Adaptive two-echelon capacitated vehicle routing problem (A2E-CVRP) proposed in this paper is a variant of the classical 2E-CVRP. Comparing to 2E-CVRP, A2E-CVRP has multiple depots and allows the vehicles to serve customers directly from the depots. Hence, it has more efficient solution and adapt to real-world environment. This paper gives a mathematical formulation for A2E-CVRP and derives a lower bound for it. The lower bound is used for deriving an upper bound subsequently, which is also an approximate solution of A2E-CVRP. Computational results on benchmark instances show that the A2E-CVRP outperforms the classical 2E-CVRP in the costs of routes.     

The no-wait job shop with regular objective: a method based on optimal job insertion

The no-wait job shop problem (NWJS-R) considered here is a version of the job shop scheduling problem where, for any two operations of a job, a fixed time lag between their starting times is prescribed. Also, sequence-dependent set-up times between consecutive operations on a machine can be present. The problem consists in finding a schedule that minimizes a general regular objective function. We study the so-called optimal job insertion problem in the NWJS-R and prove that this problem is solvable in polynomial time by a very efficient algorithm, generalizing a result we obtained in the case of a makespan objective. We then propose a large neighborhood local search method for the NWJS-R based on the optimal job insertion algorithm and present extensive numerical results that compare favorably with current benchmarks when available.