On random quadratic bottleneck assignment problems

The relative error between best and worst solution of quadratic bottleneck assignment problems with cost coefficientsd _ijpq =a _ip b _jq is considered, wherea _ip is either arbitrarily given or corresponds to a distance in the plane. It is shown that the relative error is bounded by a function(m), tending to zero, with probability tending to one asm , provided the data are uniformly distributed. This implies that any algorithm for the above mentioned problems yields asymptotically an arbitrarily small relative error with probability tending to one.     

Quadratic assignment problems on series-parallel digraphs

Christofides has shown that the quadratic assignment problem (QAP) on isomorphic trees is solvable in polynomial time by dynamic programming. We generalize the approach to minimal series-parallel digraphs and show that this problem is equivalent to the general QAP, thus NP-hard. However the restriction to the subclass of series-parallel digraphs not containing bipartite subgraphs again is solvable in polynomial time. An algorithm for this class is given.This work was financially supported by the Austrian Fonds zur Förderung der wissenschaftlichen Forschung, Projekt S32/01.     

A contribution to quadratic assignment problems

We discuss special eases of the quadratic assignment problem (QAP) being polynomially solvable. In particular we give an algebraic condition for the cost; Matrices of a QAP which guarantees that it is equivalent with a linear assignment problem. Based on these results we develop an approximation algorithm for QAPs with non-negative symmetric cost matrices.     

A generalized bottleneck assignment problem

A solution procedure is presented for a generalization of the standard bottleneck assignment problem in which a secondary criterion is automatically provided. A partitioning problem is modeled by this bottleneck problem to provide an example of its application.     

Autocorrelation measures for the quadratic assignment problem

In this article we provide an exact expression for computing the autocorrelation coefficient ξ and the autocorrelation length ? of any arbitrary instance of the Quadratic Assignment Problem (QAP) in polynomial time using its elementary landscape decomposition. We also provide empirical evidence of the autocorrelation length conjecture in QAP and compute the parameters ξ and ? for the 137 instances of the QAPLIB. Our goal is to better characterize the difficulty of this important class of problems to ease the future definition of new optimization methods. Also, the advance that this represents helps to consolidate QAP as an interesting and now better understood problem.     

Towards auction algorithms for large dense assignment problems

In this paper, we focus on the problem of solving large-scale instances of the linear sum assignment problem by auction algorithms. We introduce a modified auction algorithm, called look-back auction algorithm, which extends the forward auction algorithm by the ability of reusing information from previous bids. We show that it is able to reuse information from the previous bids with high efficiency for all tested types of input instances. We discuss then the design and implementation of a suite of sequential and distributed memory auction algorithms on a Linux cluster with the evaluation on several types of input instances of the linear sum assignment problem. Our results show that the look-back auction algorithm solves sequentially nearly all types of dense instances faster than other evaluated algorithms and it is more stable than the forward-reverse auction algorithm for sparse instances. Our distributed memory auction algorithms are fully memory scalable. This research has been supported by IGA CTU under grant CTU0308013 and under research program MSMT 6840770014.     

A note on the asymptotic behaviour of bottleneck problems

We generalize and sharpen results of Burkard and Fincke concerning the asymptotic behaviour of a certain class of combinatorial optimization problems with bottleneck objective function. In this way several open questions are answered.     

The alternating basis algorithm for assignment problems

The purpose of this paper is to present a new primal extreme point algorithm for solving assignment problems which both circumvents and exploits degeneracy. The algorithm is based on the observation that the degeneracy difficulties of the simplex method result from the unnecessary inspection of alternative basis representations of the extreme points. This paper characterizes a subsetQ of all bases that are capable of leading to an optimal solution to the problem if one exists. Using this characterization, an extreme point algorithm is developed which considers only those bases inQ. Computational results disclose that the new algorithm is substantially more efficient than previously developed primal and primal-dual extreme point (simplex) methods for assignment problems.     

A note on a polynomial time solvable case of the quadratic assignment problem

We identify a class of instances of the Koopmans–Beckmann form of the Quadratic Assignment Problem that are solvable in polynomial time. This class is characterized by a path structure in the flow data and a grid structure in the distance data. Chr18b, one of the test problems in the QAPLIB, is in this class even though this feature of it has not been noticed until now.     

Lower bounds for the quadratic assignment problem via triangle decompositions

We consider transformations of the (metric) Quadratic Assignment Problem (QAP) that exploit the metric structure of a given instance. We show in particular how the structural properties of rectangular grids can be used to improve a given lower bound. Our work is motivated by previous research of Palubetskes (1988), and it extends a bounding approach proposed by Chakrapani and Skorin-Kapov (1993). Our computational results indicate that the present approach is practical; it has been applied to problems of dimension up ton = 150. Moreover, the new approach yields by far the best lower bounds on most of the instances of metric QAPs that we considered.The authors gratefully acknowledge financial support by the Christian Doppler Laboratorium für Diskrete Optimierung.     

The generalized assignment problem with flexible jobs

The Generalized Assignment Problem (GAP) seeks an allocation of jobs to capacitated resources at minimum total assignment cost, assuming a job cannot be split among multiple resources. We consider a generalization of this broadly applicable problem in which each job must not only be assigned to a resource, but its resource consumption must also be determined within job-specific limits. In this profit-maximizing version of the GAP, a higher degree of resource consumption increases the revenue associated with a job. Our model permits a job’s revenue per unit resource consumption to decrease as a function of total resource consumption, which allows modeling quantity discounts. The objective is then to determine job assignments and resource consumption levels that maximize total profit. We develop a class of heuristic solution methods, and demonstrate the asymptotic optimality of this class of heuristics in a probabilistic sense.     

An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors

Given a complete k-partite graph G=(V₁,V₂,…,V_k;E) satisfying |V₁|=|V₂|=?=|V_k|=n and weights of all  k-cliques of G, the  k-dimensional assignment problem finds a partition of vertices of G into a set of (pairwise disjoint) n k-cliques that minimizes the sum total of weights of the chosen cliques. In this paper, we consider a case in which the weight of a clique is defined by the sum of given weights of edges induced by the clique. Additionally, we assume that vertices of G are embedded in the d-dimensional space Q^d and a weight of an edge is defined by the square of the Euclidean distance between its two endpoints. We describe that these problem instances arise from a multidimensional Gaussian model of a data-association problem.We propose a second-order cone programming relaxation of the problem and a polynomial time randomized rounding procedure. We show that the expected objective value obtained by our algorithm is bounded by (5/2−3/k) times the optimal value. Our result improves the previously known bound (4−6/k) of the approximation ratio.     

Probabilistic analysis of the generalised assignment problem

We analyse thegeneralised assignment problem under the assumption that all coefficients are drawn uniformly and independently from [0, 1]. We show that such problems can be solved exactly with high probability, in a well-defined sense. The results are closely related to earlier work of Lueker, Goldberg and Marchetti-Spaccamela and ourselves.Supported by NATO grant RG0088/89.Supported by NSF grant CCR-8900112 and NATO grant RG0088/89.     

Asymptotic Properties of Random Multidimensional Assignment Problems

The multidimensional assignment problem (MAP) is a NP-hard combinatorial optimization problem, occurring in many applications, such as data association. In this paper, we prove two conjectures made in Ref. 1 and based on data from computational experiments on MAPs. We show that the mean optimal objective function cost of random instances of the MAP goes to zero as the problem size increases, when assignment costs are independent exponentially or uniformly distributed random variables. We prove also that the mean optimal solution goes to negative infinity when assignment costs are independent normally distributed random variables.     

Strong Asymptotics of Laguerre-Type Orthogonal Polynomials and Applications in Random Matrix Theory

We consider polynomials orthogonal on [0,∞) with respect to Laguerre-type weights w(x) = x^α e^-Q(x), where α > -1 and where Q denotes a polynomial with positive leading coefficient. The main purpose of this paper is to determine Plancherel-Rotach-type asymptotics in the entire complex plane for the orthonormal polynomials with respect to w, as well as asymptotics of the corresponding recurrence coefficients and of the leading coefficients of the orthonormal polynomials. As an application we will use these asymptotics to prove universality results in random matrix theory. We will prove our results by using the characterization of orthogonal polynomials via a 2 × 2 matrix valued Riemann--Hilbert problem, due to Fokas, Its, and Kitaev, together with an application of the Deift-Zhou steepest descent method to analyze the Riemann-Hilbert problem asymptotically.     

Lower bounds for the quadratic assignment problem

We investigate the classical Gilmore-Lawler lower bound for the quadratic assignment problem. We provide evidence of the difficulty of improving the Gilmore-Lawler bound and develop new bounds by means of optimal reduction schemes. Computational results are reported indicating that the new lower bounds have advantages over previous bounds and can be used in a branch-and-bound type algorithm for the quadratic assignment problem.     

Ranking scalar products to improve bounds for the quadratic assignment problem

The eigenvalue bound for the quadratic assignment problem (QAP) is successively improved by considering a set of k-best scalar products, related to the QAP. An efficient procedure is proposedto find such a set of k-best scalar products. A class of QAPs is described for which this procedure in general improves existing lower bounds and at the same time generates good suboptimal solutions. The method leaves the user with a large flexibility in controlling the quality of the bound. However, since the method is sensitive to input data it should only be used in combination with other bounding rules.     

Comparison of Lagrangian bounds for one class of generalized assignment problems

Classical and modified Lagrangian bounds for the optimal value of optimization problems with a double decomposable structure are examined. For the class of generalized assignment problems, this property of constraints is used to design a Benders algorithm for solving the modified dual problem. Numerical results are presented that compare the quality of classical and modified bounds.     

Asymptotic analysis for multi-objective sequential stochastic assignment problems

ABSTRACT

We provide an asymptotic analysis of multi-objective sequential stochastic assignment problems (MOSSAP). In MOSSAP, a fixed number of tasks arrive sequentially, with an n-dimensional value vector revealed upon arrival. Each task is assigned to one of a group of known workers immediately upon arrival, with the reward given by an n-dimensional product-form vector. The objective is to maximize each component of the expected reward vector. We provide expressions for the asymptotic expected reward per task for each component of the reward vector and compare the convergence rates for three classes of Pareto optimal policies.