Maximum cardinality neighbourly sets in quadrilateral free graphs

Neighbourly set of a graph is a subset of edges which either share an end point or are joined by an edge of that graph. The maximum cardinality neighbourly set problem is known to be NP-complete for general graphs. Mahdian (Discret Appl Math 118:239–248, 2002) proved that it is in polynomial time for quadrilateral-free graphs and proposed an \(O(n^{11})\) algorithm for the same, here n is the number of vertices in the graph, (along with a note that by a straightforward but lengthy argument it can be proved to be solvable in \(O(n^5)\) running time). In this paper we propose an \(O(n^2)\) time algorithm for finding a maximum cardinality neighbourly set in a quadrilateral-free graph.     

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.