Solution methods and computational investigations for the Linear Bottleneck Assignment Problem
Tóm tắt
The Linear Bottleneck Assignment ProblemLBAP is analyzed from a computational point of view. Beside a brief review of known algorithms new methods are developed using only sparse subgraphs for their computation. The practical behaviour of both types of algorithms is investigated. The most promising algorithm consists of computing a maximum cardinality matching with all edge costs smaller than a previously determined bound and augmenting this matching to an assignment. The methods on sparse subgraphs are useful in the case of memory restrictions and are superior if the subgraph selection can be improved by some previously generated structure. Other treated questions are how to select a suitable subgraph for the new methods, how to deal with non regular data and what connections to asymptotic results for theLBAP can be detected.
Tài liệu tham khảo
Alt, H., Blum, N., Mehlhorn, K., Paul, M.: Computing a maximum cardinality matching in a bipartite graph in timeO(n 1.5√m/logn). Inf. Proc. Lett.37, 237–240 (1991).
Bollobás, B., Thomason, A.: Random graphs of small order. Random Graphs, ’83. Ann. Disc. Math.28, 47–97 (1985).
Burkard, R. E., Derigs, U.: Assignment and matching problems: solution methods with Fortran-programs. Springer Lecture Notes Econ. Math. Sys.184 (1980).
Carpaneto, G., Toth, P.: Algorithm for the solution of the bottleneck assignment problem. Computing27, 179–187 (1981).
Carpaneto, G., Toth, P.: Algorithm for the solution of the assignment problem for sparse matrices. Computing31, 83–94 (1983).
Derigs, U.: Alternate strategies for solving bottleneck assignment problems — analysis and computational results. Computing33, 95–106 (1984).
Derigs, U.: The shortest augmenting path method for solving assignment problems. Ann. Oper. Res.4, 57–102 (1985).
Derigs, U., Metz, A.: An efficient labeling technique for solving sparse assignment problems. Computing36, 301–311 (1986).
Derigs, U., Metz, A.: An in-core/out-of-core method for solving large scale assignment problems. Z. Oper. Res.30, 181–195 (1986).
Derigs, U., Zimmermann, U.: An augmenting path method for solving linear bottleneck assignment problems. Computing19, 285–295 (1978).
Gabow, H. N., Tarjan, R. E.: Algorithms for two bottleneck optimization problems. J. Algorithms9, 411–417 (1988).
Hopcroft, J. E., Karp, R. M.: Ann 5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput2, 225–231 (1973).
Palmer, E.M.: Graphical Evolution. New York: J. Wiley 1985.
Pferschy, U.: The random linear bottleneck assignment problem. In: Proc. of the 4. IPCO Conference, (Balas, E., Clausen, J., eds.). Springer Lecture Notes in Computer Science920, 145–156 (1995) and RAIRO30, 127–142 (1996).
Pferschy, U.: On three topics in combinatorial optimization, Chapter 4. PhD-thesis, Report 300, Institute of Mathematics, University of Technology Graz 1995.
Punnen, A. P., Nair, K. P. K.: Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem. Discr. Appl. Math.55, 91–93 (1994).
Taillard, E. D.: Comparison of iterative searches for the quadratic assignment problem. Centre de recherche sur les transports, CRT-989, Université de Montréal, 1994.