Abstract
We obtain a number of results regarding the distribution of values of a quadratic function f on the set of n x n permutation matrices (identified with the symmetric group Sn S n ) around its optimum (minimum or maximum). We estimate the fraction of permutations σ such that f(σ) lies within a given neighborhood of the optimal value of f and relate the optimal value with the average value of f over a neighborhood of the optimal permutation. We describe a natural class of functions (which includes, for example, the objective function in the Traveling Salesman Problem) with a relative abundance of near-optimal permutations. Also, we identify a large class of functions f with the property that permutations close to the optimal permutation in the Hamming metric of S n tend to produce near optimal values of f, and show that for general f just the opposite behavior may take place
This research was partially supported by NSF grant DMS 9734138
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anstreicher, K., Brixius, N., Goux, J.-P., Linderoth, J.: Solving large quadratic assignment problems on computational grids. Math Programming B (to appear)
Arkin, E., Hassin, R., Sviridenko, M.: Approximating the maximum quadratic assignment problem. Inform. Process. Lett. 77 (2000) no. 1. 13–16
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and approximation. Combinatorial optimization problems and their approximability properties. Springer-Verlag, Berlin (1999)
Brüngger, A., Marzetta, A., Clausen, J., Perregaard M.: Solving large scale quadratic assignment problems in parallel with the search library ZRAM. Journal of Parallel and Distributed Computing 50 (1998) 157–66
Burkard, R., çCela, E., Pardalos, P., Pitsoulis, L.: The quadratic assignment problem. In: Du, D.-Z., and Pardalos, P. M. (eds.): Handbook of Combinatorial Optimization. Kluwer Academic Publishers (1999) 75–149
Fulton, W., Harris, J.: Representation theory. Springer-Verlag, New York (1991)
Goulden, I. P., Jackson, D. M.: Combinatorial enumeration. John Wiley & Sons, Inc., New York (1983)
Graves, G. W., Whinston, A. B.: An algorithm for the quadratic assignment problem. Management Science 17 (1970) no. 7. 452–71
Stephen, T.: The distribution of values in combinatorial optimization problems. Ph.D. Dissertation, University of Michigan (in preparation)
Ye, Y.: Approximating quadratic programming with bound and quadratic constraints. Math. Programming 84 (1999) no. 2. 219–226
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Barvinok, A., Stephen, T. (2002). The Distribution of Values in the Quadratic Assignment Problem. In: Cook, W.J., Schulz, A.S. (eds) Integer Programming and Combinatorial Optimization. IPCO 2002. Lecture Notes in Computer Science, vol 2337. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47867-1_26
Download citation
DOI: https://doi.org/10.1007/3-540-47867-1_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43676-8
Online ISBN: 978-3-540-47867-6
eBook Packages: Springer Book Archive