Search · four archives
Search · four archives
15 papers · ranked by Valyu relevance
Joshua T. Vogelstein, John M. Conroy, Vince Lyzinski, Louis J. Podrazik + 6 more
'Louis J. Podrazik' 'Steven G. Kratzer' 'Eric T. Harley' 'Donniell E. Fishkind' 'R. Jacob Vogelstein' 'Carey E. Priebe' 'Mark R. Muldoon'] Quadratic assignment problems arise in a wide variety of domains, spanning operations research, graph theory, computer vision, and neuroscience, to name a few. The graph matching…
Jeffrey Christiansen, Kate Smith‐Miles
For any optimisation problem where diverse algorithmic approaches are available, the task of predicting algorithm performance and selecting the algorithm most likely to perform well on a given instance holds great practical interest. However, if our test instances do not adequately represent the potential problem…
Alfonsas Misevičius, Dovilė Verenė
In this paper, we present a hybrid genetic-hierarchical algorithm for the solution of the quadratic assignment problem. The main distinguishing aspect of the proposed algorithm is that this is an innovative hybrid genetic algorithm with the original, hierarchical architecture. In particular, the genetic algorithm is…
Wojciech Chmiel, Joanna Kwiecień
The paper focuses on the opportunity of the application of the quantum-inspired evolutionary algorithm for determining minimal costs of the assignment in the quadratic assignment problem. The idea behind the paper is to present how the algorithm has to be adapted to this problem, including crossover and mutation…
Wee Loon Lim, Antoni Wibowo, Mohammad Ishak Desa, Habibollah Haron
The quadratic assignment problem (QAP) is an NP-hard combinatorial optimization problem with a wide variety of applications. Biogeography-based optimization (BBO), a relatively new optimization technique based on the biogeography concept, uses the idea of migration strategy of species to derive algorithm for solving…
Christine Huber, Wolfgang Riedl
The quadratic assignment problem is a well-known optimization problem with numerous applications. A common strategy to solve it is to use one of its linearizations and then apply the toolbox of mixed integer linear programming methods. One measure of quality of a mixed integer formulation is the quality of its linear…
Taku Mikuriya, Kein Yukiyoshi, S. Fujiwara, Giuseppe Abreu + 1 more
'Naoki Ishikawa'] Abstract—We demonstrate that the search space of the quadratic assignment problem (QAP), known as an NP-hard combinatorial optimization problem, can be reduced using Grover adaptive search (GAS) with Dicke state operators. To that end, we first revise the traditional quadratic formulation of the QAP…
Hao Hu, Renata Sotirov, Henry Wolkowicz
We consider both facial reduction, FR, and symmetry reduction, SR, techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. In fact, this approach allows for simply adding on nonnegativity constraints, and…
Alexandre Domingues Gonçalves, Artur Alves Pessoa, Lúcia M. A. Drummond, Cristiana Bentes + 1 more
'Lúcia M. A. Drummond' 'Cristiana Bentes' 'Ricardo Farias'] The Quadratic Assignment Problem, QAP, is a classic combinatorial optimization problem, classified as NP-hard and widely studied. This problem consists in assigning N facilities to N locations obeying the relation of 1 to 1, aiming to minimize costs of the…
Yam Kushinsky, Haggai Maron, Nadav Dym, Yaron Lipman
Recently, Sinkhorn's algorithm was applied for approximately solving linear programs emerging from optimal transport very efficiently [1]. This was accomplished by formulating a regularized version of the linear program as Bregman projection problem onto the polytope of doubly-stochastic matrices, and then computing…
Ante Ćustić, Vladyslav Sokol, Abraham P. Punnen, Binay Bhattacharya
In this paper we study the bilinear assignment problem (BAP) with size parameters m and n, m ≤ n. BAP is a generalization of the well known quadratic assignment problem and the three dimensional assignment problem and hence NP-hard. We show that BAP cannot be approximated within a constant factor unless P=NP even if…
S. H. Sathish Indika, Douglas R. Shier
This work is motivated by a particular scheduling problem that is faced by logistics centers that perform aircraft maintenance and modification. Here we concentrate on a single facility (hangar) which is equipped with several work stations (bays). Specifically, a number of jobs have already been scheduled for…
Pooja Pandey, Abraham P. Punnen
In this paper we identify various inaccuracies in the paper by R. R. Saxena and S. R. Arora, A Linearization technique for solving the Quadratic Set Covering Problem, Optimization, 39 (1997) 33-42. In particular, we observe that their algorithm does not guarantee optimality, contrary to what is claimed. Experimental…
Amnon Rosenmann
The k-cardinality assignment (k-assignment, for short) problem asks for finding a minimal (maximal) weight of a matching of cardinality k in a weighted bipartite graph $K_{n,n}$, $k \le n$. Here we are interested in computing the sequence of all k-assignments, $k=1,\ldots ,n$. By applying the algorithm of Gassner and…
Daniel Lokshtanov
In the Integer Quadratic Programming problem input is an n × n integer matrix Q, an m × n integer matrix A and an m-dimensional integer vector b. The task is to find a vector x ∈ Z n minimizing x TQx, subject to Ax ≤ b. We give a fixed parameter tractable algorithm for Integer Quadratic Programming parameterized by n +…