A note on “scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan”

In a recent paper, Chen [J.S. Chen, Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan, European Journal of Operational Research 190 (2008) 90–102] proposes a heuristic algorithm to deal with the problem Scheduling of Nonresumable Jobs and Flexible Maintenance Activities on A Single Machine to Minimize Makespan  . Chen also provides computational results to demonstrate its effectiveness. In this note, we first show that the worst-case performance bound of this heuristic algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case performance bound less than 2 unless P=NP$P=\mathit{NP}$, which implies that Chen’s heuristic algorithm is the best possible polynomial time approximation algorithm for the considered scheduling problem.     

Critical edges for the assignment problem: Complexity and exact resolution

This paper investigates two problems related to the determination of critical edges for the minimum cost assignment problem. Given a complete bipartite balanced graph with n$n$ vertices on each part and with costs on its edges, k$k$Most Vital Edges Assignment consists of determining a set of k$k$ edges whose removal results in the largest increase in the cost of a minimum cost assignment. A dual problem, Min Edge Blocker Assignment, consists of removing a subset of edges of minimum cardinality such that the cost of a minimum cost assignment in the remaining graph is larger than or equal to a specified threshold. We show that k$k$Most Vital Edges Assignment is NP$NP$-hard to approximate within a factor c<2$c<2$ and Min Edge Blocker Assignment is NP$NP$-hard to approximate within a factor 1.36$1.36$. We also provide an exact algorithm for k$k$Most Vital Edges Assignment that runs in O(n^k+2)$O\left(n^{k+2}\right)$. This algorithm can also be used to solve exactly Min Edge Blocker Assignment.     

Polar permutation graphs are polynomial-time recognisable

Polar graphs generalise bipartite graphs, cobipartite graphs, and split graphs, and they constitute a special type of matrix partitions. A graph is polar if its vertex set can be partitioned into two, such that one part induces a complete multipartite graph and the other part induces a disjoint union of complete graphs. Deciding whether a given arbitrary graph is polar, is an NP$\text{NP}$-complete problem. Here, we show that for permutation graphs this problem can be solved in polynomial time. The result is surprising, as related problems like achromatic number and cochromatic number are NP$\text{NP}$-complete on permutation graphs. We give a polynomial-time algorithm for recognising graphs that are both permutation and polar. Prior to our result, polarity has been resolved only for chordal graphs and cographs.     

A distance-based point-reassignment heuristic for the k-hyperplane clustering problem

We consider the k-Hyperplane Clustering problem where, given a set of m   points in Rⁿ${\mathbb{R}}^n$, we have to partition the set into k subsets (clusters) and determine a hyperplane for each of them, so as to minimize the sum of the squares of the Euclidean distances between the points and the hyperplane of the corresponding clusters. We give a nonconvex mixed-integer quadratically constrained quadratic programming formulation for the problem. Since even very small-size instances are challenging for state-of-the-art spatial branch-and-bound solvers like Couenne, we propose a heuristic in which many “critical” points are reassigned at each iteration. Such points, which are likely to be ill-assigned in the current solution, are identified using a distance-based criterion and their number is progressively decreased to zero. Our algorithm outperforms the best available one proposed by Bradley and Mangasarian on a set of real-world and structured randomly generated instances. For the largest instances, we obtain an average improvement in the solution quality of 54%.     

Branch-and-reduce algorithm for convex programs with additional multiplicative constraints

This article presents a branch-and-reduce algorithm for globally solving for the first time a convex minimization problem (P) with p?1$p?1$ additional multiplicative constraints. In each of these p   additional constraints, the product of two convex functions is constrained to be less than or equal to a positive number. The algorithm works by globally solving a 2p$2p$-dimensional master problem (MP) equivalent to problem (P). During a typical stage k of the algorithm, a point is found that minimizes the objective function of problem (MP) over a nonconvex set F^k$F^k$ that contains the portion of the boundary of the feasible region of the problem where a global optimal solution lies. If this point is feasible in problem (MP), the algorithm terminates. Otherwise, the algorithm continues by branching and creating a new, reduced nonconvex set F^k+1$F^{k+1}$ that is a strict subset of F^k$F^k$. To implement the algorithm, all that is required is the ability to solve standard convex programming problems and to implement simple algebraic steps. Convergence properties of the algorithm are given, and results of some computational experiments are reported.