In this paper, we study the quadratic assignment problem with a rank-one cost matrix (QAP-R1). Four integer-programming formulations are introduced of which three are assumed to have partial integer data. Unlike the standard quadratic assignment problem, some of our formulations can solve reasonably large instances of QAP-R1 with impressive running times and are faster than some metaheuristics. Pairwise relative strength of the LP relaxations of these formulations are also analyzed from theoretical and experimental points of view. Finally, we present a new metaheuristic algorithm to solve QAP-R1 along with its computational analysis. Our study offers the first systematic experimental analysis of integer-programming models and heuristics for QAP-R1. The benchmark instances with various characteristics generated for our study are made available to the public for future research work. Some new polynomially solvable special cases are also introduced. Summary of Contribution: This paper aims to advance our knowledge and ability in solving an important special case of the quadratic assignment problem. It shows how to exploit inherent properties of an optimization problem to achieve computational advantages, a strategy that was followed by researchers in model building and algorithm developments for decades. Our computational results attest to this time-tested general philosophy. The paper presents the first systematic computational study of the rank one quadratic assignment problem, along with new mathematical programming models and complexity analysis. We believe the theoretical and computational results of this paper will inspire further research on the topic and will be of significant value to practitioners using rank one quadratic assignment models.

The bilinear assignment problem (BAP) is a generalization of the well-known quadratic assignment problem. In this paper, we study the problem from the computational analysis point of view. Several classes of neighborhood structures are introduced for the problem along with some theoretical analysis. These neighborhoods are then explored within a local search and variable neighborhood search frameworks with multistart to generate robust heuristic algorithms. In addition, we present several very fast construction heuristics. Our systematic experimental analysis disclosed some interesting properties of the BAP, different from those of comparable models. We have also introduced benchmark test instances that can be used for future experiments on exact and heuristic algorithms for the problem.

In this paper, we provide a complete characterization of undirected SC-Hamiltonian graphs that are not strongly Hamiltonian. This conclusively settles a conjecture by Kryński [Discrete Appl. Math., 55 (1994), pp. 87–89], which was later disproved by Kabadi and Punnen [Discrete Math., 271 (2003), pp. 129–139] with a counterexample. We show that the Kabadi–Punnen counterexample is the only class of graphs where Kryński's conjecture is false, thereby proving the conjecture for all other graphs.

Abstract The prize‐collecting Steiner tree problem is well known to be NP‐hard. We consider seven variations of this problem generalizing several well‐studied bottleneck and minsum problems with feasible solutions as trees of a graph. Four of these problems are shown to be solvable in O(m+n log n) time and the remaining are shown to be NP‐hard where n is the number of nodes and m is the number of edges in the underlying graph. For one of these polynomially solvable cases, we also provide an O(m) algorithm generalizing and unifying known linear time algorithms for the bottleneck spanning tree problem, bottleneck s−t path problem, and bottleneck Steiner tree problem. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(4), 199–205 2006

A polynomial time testable characterization of cost matrices associated with a complete digraph on n nodes such that all the Hamiltonian cycles (tours) have the same cost is well known. Tarasov [U.S.S.R. Comput. Maths. Math. Phys., 21 (1981), pp. 167–174.] obtained a characterization of cost matrices where tour costs take two distinct values. We provide a simple alternative characterization of such cost matrices, which can be tested in $O(n^2)$ time. We also provide analogous results where tours are replaced by Hamiltonian paths. When the cost matrix is skew‐symmetric, we provide polynomial time testable characterizations such that the tour costs take three distinct values. Corresponding results for the case of Hamiltonian paths are also given. Using these results, special instances of the asymmetric traveling salesman problem (ATSP) are identified that are solvable in polynomial time and that have improved constant factor approximation schemes. In particular, we observe that the 3/2 performance guarantee of the Christofides algorithm extends to all metric Hamiltonian symmetric matrices. Further, we identify special classes of ATSP for which polynomial $\epsilon$‐approximation algorithms are available for $\epsilon \in \{3/2, 4/3, 4\tau, \frac{3\tau^2}{2}, \frac{4+\delta}{3}\}$, where $\tau > 1/2$ and $\delta \geq 0$ are constants.

Local search algorithms for combinatorial optimization problems are generally of pseudopolynomial running time, and polynomial-time algorithms are not often known for finding locally optimal solutions for NP-hard optimization problems. We introduce the concept of $\varepsilon$-local optimality and show that, for every $\varepsilon > 0$, an $\varepsilon$-local optimum can be identified in time polynomial in the problem size and $1/\varepsilon$ whenever the corresponding neighborhood can be searched in polynomial time. If the neighborhood can be searched in polynomial time for a $\delta$-local optimum, a variation of our main algorithm produces a $(\delta + \varepsilon)$-local optimum in time polynomial in the problem size and $1/\varepsilon$. As a consequence, a combinatorial optimization problem has a fully polynomial-time approximation scheme if and only if the problem of determining a better neighbor in an exact neighborhood has a fully polynomial-time approximation scheme.

We propose an algorithm to solve the bottleneck spanning tree problem with an additional linear constraint. Our algorithm has an improved worst case performance over the best known algorithm for this problem. In a graph with n nodes and m edges such that m ≥ O(n log n log log*n), where log* n is the iterative logarithm of n, our algorithm runs in O(m) time and hence is the best possible in that case. For a large class of graphs, the proposed algorithm has almost the same complexity as that of computing just one minimum spanning tree.