More Web Proxy on the site http://driver.im/

article

The bilinear assignment problem: complexity and polynomially solvable special cases

Authors:

Ante ăźUstić,

Vladyslav Sokol,

Abraham P. Punnen,

Binay BhattacharyaAuthors Info & Claims

Mathematical Programming: Series A and B, Volume 166, Issue 1-2

Pages 185 - 205

https://doi.org/10.1007/s10107-017-1111-1

Published: 01 November 2017 Publication History

Abstract

In this paper we study the bilinear assignment problem (BAP) with size parameters m and n, $$m\le 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 the associated quadratic cost matrix Q is diagonal. Further, we show that BAP remains NP-hard if $$m = O(\root r \of {n})$$m=O(nr), for some fixed r, but is solvable in polynomial time if $$m = O\left( \frac{\log n}{\log \log n}\right) $$m=Olognloglogn. When the rank of Q is fixed, BAP is observed to admit FPTAS and when this rank is one, it is solvable in polynomial time under some additional restrictions. We then provide a necessary and sufficient condition for BAP to be equivalent to two linear assignment problems. A closed form expression to compute the average of the objective function values of all solutions is presented, whereas the median of the solution values cannot be identified in polynomial time, unless P = NP. We then provide polynomial time heuristic algorithms that find a solution with objective function value no worse than that of $$(m-1)!(n-1)!$$(m-1)!(n-1)! solutions. However, computing a solution whose objective function value is no worse than that of $$m!n!-\lceil \frac{m}{\beta }\rceil !\lceil \frac{n}{\beta }\rceil !$$m!n!-źmβź!źnβź! solutions is NP-hard for any fixed rational number $$\beta >1$$β>1.

References

[1]

Ahuja, R.K., Ergun, O., Orlin, J.B., Punnen, A.P.: Very large scale neighborhood search: theory, algorithms and applications, approximation algorithms and metaheuristics. In: Gonzalez, T.F. (ed.): Handbook of approximation algorithms and metaheuristics. CRC Press (2007)

[2]

Alon, N., Gutin, G., Krivelevich, M.: Algorithms with large domination ratio. J. Algorithms 50, 118---131 (2004)

Digital Library

[3]

Altman, M.: Bilinear programming. Bull. de l' Académie Pol. des Sci. 16, 741---746 (1968)

[4]

Angel, E., Zissimopoulos, V.: On the quality of local search for the quadratic assignment problem. Discrete Appl. Math. 82, 15---25 (1995)

Digital Library

[5]

Berenguer, X.: A characterization of linear admissible transformations for the $$m$$m-traveling salesman problem. Eur. J. Op. Res. 3, 232---238 (1979)

[6]

Burkard, R.E., Çela, E., Rote, G., Woeginger, G.J.: The quadratic assignment problem with monotone anti-Monge and symmetric Toeplitz matrix: easy and hard cases. Math. Program. 82, 125---158 (1998)

[7]

Burkard, R.E., Dell'Amico, M., Martello, S.: Assignment Problems. SIAM, Philadelphia (2009)

Digital Library

[8]

Çela, E.: The Quadratic Assignment Problem: Theory and Algorithms. Kluwer Academic Publishers, Dordrecht (1998)

[9]

Çela, E., Deă¿neko, V.G., Woeginger, G.J.: Linearizable special cases of the QAP. J. Comb. Optim. 31, 1269---1279 (2016)

Digital Library

[10]

ă¿ustić, A., Klinz, B.: The constant objective value property for multidimensional assignment problems. Discrete Optim. 19, 23---35 (2016)

Digital Library

[11]

ă¿ustić, A., Punnen, A.P.: Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis. arXiv:1512.02709 (2015)

[12]

ă¿ustić, A., Punnen, A.P.: Characterization of the linearizable instances of the quadratic minimum spanning tree problem. arXiv:1510.02197 (2015)

[13]

Deă¿neko, V.G., Woeginger, G.J.: A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem. Math. Program. 87, 519---542 (2000)

[14]

Fon-Der-Flaass, D.: Arrays of distinct representatives--a very simple NP-complete problem. Discrete Math. 171, 295---298 (1997)

Digital Library

[15]

Frieze, A.M.: Complexity of a 3-dimensional assignment problem. Eur. J. Op. Res. 13, 161---164 (1983)

[16]

Frieze, A.M.: A bilinear programming formulation of the 3-dimensional assignment problem. Math. Program. 7, 376---379 (1974)

Digital Library

[17]

Glover, F., Punnen, A.P.: The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms. J. Op. Res. Soc. 48, 502---510 (1997)

[18]

Graves, G.W., Whinston, A.B.: An algorithm for the quadratic assignment problem. Manag. Sci. 16, 453---471 (1970)

Digital Library

[19]

Grover, L.K.: Local search and the local structure of NP-complete problems. Op. Res. Lett. 12, 235---243 (1992)

Digital Library

[20]

Gutin, G., Jensen, T., Yeo, A.: Domination analysis for minimum multiprocessor scheduling. Discrete Appl. Math. 154, 2613---2619 (2006)

Digital Library

[21]

Gutin, G., Vainshtein, A., Yeo, A.: Domination analysis of combinatorial optimization problems. Discrete Appl. Math. 129, 513---520 (2003)

Digital Library

[22]

Gutin, G., Yeo, A.: Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number. Discrete Appl. Math. 119, 107---116 (2002)

Digital Library

[23]

Gutin, G., Yeo, A.: TSP tour domination and Hamilton cycle decompositions of regular graphs. Op. Res. Lett. 28, 107---111 (2001)

Digital Library

[24]

Hassin, R., Khuller, S.: z-Approximations. J. Algorithms 41, 429---442 (2001)

Digital Library

[25]

Konno, H.: Maximization of a convex quadratic function under linear constraints. Math. Program. 11, 117---127 (1976)

Digital Library

[26]

Kabadi, S.N., Punnen, A.P.: An $$O(n^4)$$O(n4) algorithm for the QAP linearization problem. Math. Op. Res. 36, 754---761 (2011)

Digital Library

[27]

Kuhn, D., Osthus, D.: Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments. Adv. Math. 237, 62---146 (2013)

[28]

Koller, A.E., Noble, S.D.: Domination analysis of greedy heuristics for the frequency assignment problem. Discrete Math. 275, 331---338 (2004)

Digital Library

[29]

Mitrović-Minić, A., Punnen, A.P.: Local search intensified: very large-scale variable neighborhood search for the multi-resource generalized assignment problem. Discrete Optim. 6, 370---377 (2009)

Digital Library

[30]

Mittal, S., Schulz, A.S.: An FPTAS for optimizing a class of low-rank functions over a polytope. Math. Program. 141, 103---120 (2012)

[31]

Punnen, A.P., Kabadi, S.N.: Domination analysis of some heuristics for the asymmetric traveling salesman problem. Discrete Appl. Math. 119, 117---128 (2002)

Digital Library

[32]

Punnen, A.P., Margot, F., Kabadi, S.N.: TSP heuristics: domination analysis and complexity. Algorithmica 35, 111---127 (2003)

[33]

Punnen, A.P., Kabadi, S.N.: A linear time algorithm for the Koopmans-Beckman QAP linearization and related problems. Discrete Optim. 10, 200---209 (2013)

[34]

Punnen, A.P., Sripratak, P., Karapetyan, D.: Average value of solutions for the bipartite boolean quadratic programs and rounding algorithms. Theor. Comput. Sci. 565, 77---89 (2015)

Digital Library

[35]

Rublineckii, V.I.: Estimates of the accuracy of procedures in the traveling salesman problem. Numer. Math. Comput. Technol. 4, 18---23 (1973). (in Russian)

[36]

Sahni, S., Gonzalez, T.F.: P-complete approximation problems. J. ACM 23, 555---565 (1976)

Digital Library

[37]

Sarvanov, V., Doroshko, N.: The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of exponential cardinality in quadratic time. Softw. Algorithms Progr. 31, 8---11 (1981). (in Russian)

[38]

Sarvanov, V., Doroshko, N.: The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of factorial cardinality in cubic time. Softw. Algorithms Progr. 31, 11---13 (1981). (in Russian)

[39]

Sarvanov, V.: The mean value of the functional in sampling problems, Vestsi Akademii Navuk BSSR. Ser. Fiz. Mat. Navuk 139, 51---54 (1978)

[40]

Spieksma, F.C.R.: Multi Index Assignment Problems: Complexity, Approximation, Applications, Nonlinear Assignment Problems, 1---12. Kluwer Academic Publishers, Dordrecht (2000)

[41]

Tarasov, S.P.: Properties of the trajectories of the appointments problem and the travelling-salesman problem. USSR Comput. Math. Math. Phys. 21, 167---174 (1981)

[42]

Torki, A., Yajima, Y., Enkawa, T.: A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem. Eur. J. Op. Res. 94, 384---391 (1996)

[43]

Tsui, L.Y., Chang, C.-H.: A microcomputer based decision support tool for assigning dock doors in freight yards. Comput. Ind. Eng. 19, 309---312 (1990)

Digital Library

[44]

Tsui, L.Y., Chang, C.-H.: An optimal solution to a dock door assignment problem. Comput. Ind. Eng. 23, 283---286 (1992)

Digital Library

[45]

Twitto, Y.: Dominance guarantees for above-average solutions. Discrete Optim. 5, 563---568 (2008)

Digital Library

[46]

Vizing, V.G.: Values of the target functional in a priority problem that are majorized by the mean value. Kibernetika 5, 76---78 (1973)

[47]

Zemel, E.: Measuring the quality of approximate solutions to zero-one programming problems. Math. Op. Res. 6, 319---332 (1981)

Digital Library

[48]

Zikan, K.: Track Initialization in the Multiple-Object Tracking Problem, Technical Report SOL-88-18, Systems Optimization Laboratory. Stanford University, California. http://www.dtic.mil/dtic/tr/fulltext/u2/a202284.pdf (1988)

Cited By

Huang TVishwakarma HSala FOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Train 'n tradeProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667359(28478-28490)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667359
Housni OFoussoul AGoyal V(2022)LP-Based Approximations for Disjoint Bilinear and Two-Stage Adjustable Robust OptimizationInteger Programming and Combinatorial Optimization10.1007/978-3-031-06901-7_17(223-236)Online publication date: 27-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-06901-7_17

The bilinear assignment problem: complexity and polynomially solvable special cases
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games

In several settings, derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are ...
The complexity of the covering radius problem

We initiate the study of the computational complexity of the covering radius problem for lattices, and approximation versions of the problem for both lattices and linear codes. We also investigate the computational complexity of the shortest linearly ...
Query Complexity in Errorless Hardness Amplification

An errorless circuit for a Boolean function is one that outputs the correct answer or "don't know" on each input (and never outputs the wrong answer). The goal of errorless hardness amplification is to show that if f has no size s errorless circuit that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematical Programming: Series A and B

Mathematical Programming: Series A and B Volume 166, Issue 1-2

November 2017

399 pages

ISSN:0025-5610

Issue’s Table of Contents

Copyright © Copyright © 2017 Springer-Verlag GmbH Germany and Mathematical Optimization Society.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 November 2017

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang TVishwakarma HSala FOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Train 'n tradeProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667359(28478-28490)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667359
Housni OFoussoul AGoyal V(2022)LP-Based Approximations for Disjoint Bilinear and Two-Stage Adjustable Robust OptimizationInteger Programming and Combinatorial Optimization10.1007/978-3-031-06901-7_17(223-236)Online publication date: 27-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-06901-7_17

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents