Assignment Problem Complexity

  • 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)Google Scholar

  • 2.

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

  • 3.

    Altman, M.: Bilinear programming. Bull. de l’ Académie Pol. des Sci. 16, 741–746 (1968)MathSciNetMATHGoogle Scholar

  • 4.

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

  • 5.

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

  • 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)MathSciNetMATHGoogle Scholar

  • 7.

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

  • 8.

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

  • 9.

    Çela, E., Deĭneko, V.G., Woeginger, G.J.: Linearizable special cases of the QAP. J. Comb. Optim. 31, 1269–1279 (2016)MathSciNetCrossRefMATHGoogle Scholar

  • 10.

    Ćustić, A., Klinz, B.: The constant objective value property for multidimensional assignment problems. Discrete Optim. 19, 23–35 (2016)MathSciNetCrossRefGoogle Scholar

  • 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)MathSciNetCrossRefMATHGoogle Scholar

  • 14.

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

  • 15.

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

  • 16.

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

  • 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)CrossRefMATHGoogle Scholar

  • 18.

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

  • 19.

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

  • 20.

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

  • 21.

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

  • 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)MathSciNetCrossRefMATHGoogle Scholar

  • 23.

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

  • 24.

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

  • 25.

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

  • 26.

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

  • 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)MathSciNetCrossRefMATHGoogle Scholar

  • 28.

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

  • 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)MathSciNetCrossRefMATHGoogle Scholar

  • 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)MathSciNetCrossRefMATHGoogle Scholar

  • 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)MathSciNetCrossRefMATHGoogle Scholar

  • 32.

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

  • 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)MathSciNetCrossRefGoogle Scholar

  • 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)MathSciNetCrossRefMATHGoogle Scholar

  • 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)MathSciNetGoogle Scholar

  • 36.

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

  • 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)Google Scholar

  • 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)Google Scholar

  • 39.

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

  • 40.

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

  • 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)CrossRefMATHGoogle Scholar

  • 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)CrossRefMATHGoogle Scholar

  • 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)CrossRefGoogle Scholar

  • 44.

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

  • 45.

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

  • 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)MathSciNetGoogle Scholar

  • 47.

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

  • 48.

    Zikan, K.: Track Initialization in the Multiple-Object Tracking Problem, Technical Report SOL-88-18, Systems Optimization Laboratory. Stanford University, California. (1988)

  • Title: The Bilinear Assignment Problem: Complexity and polynomially solvable special cases

    Authors:Ante Ćustić, Vladyslav Sokol, Abraham P. Punnen, Binay Bhattacharya

    (Submitted on 23 May 2016)

    Abstract: In this paper we study the {\it bilinear assignment problem} (BAP) with size parameters $m$ and $n$, $m\leq 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(\sqrt[r]{n})$, for some fixed $r$, but is solvable in polynomial time if $m = O(\sqrt{\log n})$. 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)!$ 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 !$ solutions is NP-hard for any fixed rational number $\beta>1$.

    Submission history

    From: Ante Ćustić [view email]
    [v1] Mon, 23 May 2016 22:53:42 GMT (18kb)

    Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)

    0 thoughts on “Assignment Problem Complexity”


    Leave a Comment

    Your email address will not be published. Required fields are marked *