linear and semi assignment problems a core oriented approach

Handbook of Combinatorial Optimization pp 75–149 Cite as

Linear Assignment Problems and Extensions

• Rainer E. Burkard 4 &
• Eranda Çela 4  

1576 Accesses

154 Citations

Assignment problems deal with the question how to assign n items (e.g. jobs) to n machines (or workers) in the best possible way. They consist of two components: the assignment as underlying combinatorial structure and an objective function modeling the ”best way”.

• Bipartite Graph
• Assignment Problem
• Dual Solution
• Cost Coefficient
• Discrete Apply Mathematic

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

This research has been supported by the Spezialforschungsbereich F 003 “Optimierung und Kontrolle”, Projektbereich Diskrete Optimierung.

This is a preview of subscription content, log in via an institution .

Buying options

• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Purchases are for personal use only

Unable to display preview.  Download preview PDF.

H. Achatz, P. Kleinschmidt, and K. Paparrizos, A dual forest algorithm for the assignment problem, in Applied Geometry and Discrete Mathematics, P. Gritzmann and B. Sturmfels, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 4, AMS, Providence, RI, 1991, pp. 1–11.

Google Scholar  

R. K. Ahuja, T. L. Magnanti, J. B. Orlin, and M. R. Reddy, Applications of network optimization, in Network Models–Handbooks of Operations Research and Management Science 7), M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, eds., Elsevier, Amsterdam, 1995, pp. 1–83.

R. K. Ahuja, K. Mehlhorn, J. B. Orlin, and R. E. Tarjan, Faster algorithms for the shortest path problem, Journal of the ACM 37 , 1990, 213–223.

Article   MathSciNet   MATH   Google Scholar  

R. K. Ahuja and J. B. Orlin, The scaling network simplex algorithm, Operations Research 40 , Suppl. No. 1, 1992, S5 - S13.

MathSciNet   Google Scholar  

M. Akgül, A sequential dual simplex algorithm for the linear assignment problem, Operations Research Letters 7 , 1988, 155–158.

M. Akgül, The linear assignment problem, in Combinatorial Optimization, M. Akgül and S. Tufecki, eds., Springer Verlag, Berlin, 1992, pp. 85 –122.

Chapter   Google Scholar  

M. Akgül, A genuinely polynomial primal simplex algorithm for the assignment problem, Discrete Applied Mathematics 45 , 1993, 93–115.

M. Akgül and O. Ekin, A dual feasible forest algorithm for the assignment problem, RAIRO Operations Research 25 , 1991, 403–411.

MATH   Google Scholar  

H. Alt, N. Blum, K. Mehlhorn, and M. Paul, Computing maximum cardinality matching in time O(n1.5/m/ log e), Information Process. Letters 37 , 1991, 237–240.

MathSciNet   MATH   Google Scholar  

R. D. Armstrong and J. Zhiying, Solving linear bottleneck assignment problems via strong spanning trees, Operations Research Letters 12 , 1992, 179–180.

D. Avis and L. Devroye, An analysis of a decomposition heuristic for the assignment problem, Operations Research Letters 3, 1985, 279–283.

D. Avis and C. W. Lai, The probabilistic analysis of a heuristic for the assignment problem, SIAM Journal on Computing 17 , 1988, 732–741.

E. Balas and P. R. Landweer, Traffic assignment in communications satellites, Operations Research Letters 2, 1983, 141–147.

Article   MATH   Google Scholar  

E. Balas, D. Miller, J. Pekny, and P. Toth, A parallel shortest path algorithm for the assignment problem, Journal of the ACM 38 , 1991, 985–1004.

E. Balas and L. Qi, Linear-time separation algorithms for the three-index assignment polytope, Discrete Applied Mathematics 43, 1993, 1–12.

E. Balas and M. J. Saltzman, Facets of the three-index assignment polytope, Discrete Applied Mathematics 23 , 1989, 201–229.

E. Balas and M. J. Saltzman, An algorithm for the three-index assignment problem, Operations Research 39, 1991, 150–161.

M. L. Balinski, Signature methods for the assignment problem, Operations Research 33, 1985, 527–537.

M. L. Balinski, A competitive (dual) simplex method for the assignment problem, Mathematical Programming 34 , 1986, 125–141.

M. L. Balinski and R. E. Gomory, A primal method for the assignment and transportation problems, Management Science 10, 1964, 578–593.

Article   Google Scholar  

M. L. Balinski and J. Gonzalez, Maximum matchings in bipartite graphs via strong spanning trees, Networks 21 , 1991, 165–179.

M. L. Balinski and A. Russakoff, On the assignment polytope, SIAM Review 16, 1974, 516–525.

S. E. Bammel and J. Rothstein, The number of 9 x 9 Latin squares, Discrete Mathematics 11, 1975, 93–95.

H.-J. Bandelt, Y. Crama, and F. C. R. Spieksma, Approximation algorithms for multi-dimensional assignment problems with decomposable costs, Discrete Applied Mathematics 49 , 1994, 25–50.

V. A. Bardadym, Modifications of general lexicographic bottleneck optimization problems, Proceedings of the 5-th Twente Workshop on Graphs and Combinatorial Optimization, U. Faigle and C. Hoede, eds., 1997, University of Twente, Enschede, The Netherlands, 27–30.

R. S. Barr, F. Glover, and D. Klingman, The alternating basis algorithm for assignment problems, Mathematical Programming 13 , 1977, 1–13.

R. S. Barr and B. L. Hickman, A new parallel network simplex algorithm and implementation for large time-critical problems, Technical Report, Department of Computer Science and Engineering, Southern Methodist University, Dallas, TX, 1990.

D. P. Bertsekas, A new algorithm for the assignment problem, Mathematical Programming 21 , 1981, 152–171.

D. P. Bertsekas, The auction algorithm: A distributed relaxation method for the assignment problem, Annals of Operations Research 14 , 1988, 105–123.

D. P. Bertsekas, Linear Network Optimization: Algorithms and codes, MIT Press, Cambridge, MA, 1991.

D. P. Bertsekas and D. A. Castanon, Parallel synchronous and asynchronous implementations of the auction algorithm, Parallel Computing 17 , 1991, 707–732.

D. P. Bertsekas and D. A. Castanon, Parallel asynchronous Hungarian methods for the assignment problem, ORSA Journal on Computing 5 , 1993, 661–674.

D. P. Bertsekas and D. A. Castanon, Parallel primal-dual methods to the minimum cost network flow problem, Computational Optimization and Applications 2, 1993, 319–338.

D. P. Bertsekas, D. A. Castanon, J. Eckstein, and S. Zenios, Parallel computing in network optimization, in Network Models–Handbooks in Operations Research and Management Science, Vol. 7, M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, eds., Elsevier, Amsterdam, The Netherlands, 1995, pp. 330–399.

D. P. Bertsekas and J. Eckstein, Dual coordinate step methods for linear network flow problems, Mathematical Programming 42 , 1988, 203–243.

G. Birkhoff, Tres observaciones sobre el algebra lineal, Rev. univ. nac. Tucuman (A) 5, 1946, 147–151.

W. L. Brogan, Algorithm for ranked assignments with applications to multiobject tracking, Journal of Guidance 12, 1989, 357–364.

R. E. Burkard, Time-slot assignment for TDMA-systems, Computing 35, 1985, 99–112.

R. E. Burkard and U. Derigs, Assignment and Matching Problems: Solution Methods with FORTRAN Programs, Springer, Berlin, 1980.

Book   MATH   Google Scholar  

R. E. Burkard and K. Fröhlich, Some remarks on 3-dimensional assignment problems, Methods of Operations Research 36, 1980, 31–36.

R. E. Burkard, W. Hahn, and U. Zimmermann, An algebraic approach to assignment problems, Mathematical Programming 12 , 1977, 318327.

R. E. Burkard, B. Klinz, and R. Rudolf, Perspectives of Monge properties in optimization, Discrete Applied Mathematics 70 , 1996, 95–161.

R. E. Burkard and F. Rendl, Lexicographic bottleneck problems, Operations Research Letters 10 , 1991, 303–308.

R. E. Burkard and R. Rudolf, Computational investigations on 3dimensional axial assignment problems, Belgian J. of Operations Research 32, 1993, 85–98.

R. E. Burkard, R. Rudolf, and G. J. Woeginger, Three dimensional axial assignment problems with decomposable cost coefficients, Discrete Applied Mathematics 65 , 1996, 123–169.

R. E. Burkard and U. Zimmermann, Weakly admissible transformations for solving algebraic assignment and transportation problems, Mathematical Programming Study 12, 1980, 1–18.

R. E. Burkard and U. Zimmermann, Combinatorial optimization in linearly ordered semimodules: a survey, in Modern Applied Mathematics, B. Korte ed., North Holland, Amsterdam, 1982, pp. 392–436.

P. Camerini, L. Fratta, and F. Maffioli, On improving relaxation methods by modified gradient techniques, Mathematical Programming Study 3 , 1975, 26–34.

Article   MathSciNet   Google Scholar  

P. Carraresi and G. Gallo, Network models for vehicle and crew scheduling, European Journal of Operational Research 16 , 1984, 139–151.

P. Carraresi and G. Gallo, A multi-level bottleneck assignment approach to the bus drivers’ rostering problem, European Journal of Operational Research 16 , 1984, 163–173.

G. Carpaneto, S. Martello, and P. Toth, Algorithms and codes for the assignment problem, Annals of Operations Research 13 , 1988, 193–223.

P. Carraresi and C. Sodini, An efficient algorithm for the bipartite matching problem, European Journal of Operational Research 23, 1986, 86–93.

D. A. Castaíïon, B. Smith, and A. Wilson, Performance of parallel assignment algorithms on different multiprocessor architectures, Technical Report TP-1245, ALPHATECH, Inc., Burlington, Mass.

G. Carpaneto and P. Toth, Solution of the assignment problem, ACM Transactions on Mathematical Software 6, 1980, 104–11.

G. Carpaneto and P. Toth, Algorithm for the solution of the bottleneck assignment problem, Computing 27, 1981, 179–187.

G. Carpaneto and P. Toth, Primal-dual algorithms for the assignment problem, Discrete Applied Mathematics 18 , 1987, 137–153.

K. Cechlârovâ, The uniquely solvable bipartite matching problem, Operations Research Letters 10, 1991, 221–224.

B. V. Cherkassky and A. V. Goldberg, On implementing push-relabel methods for the maximum flow problem, Algorithmica 19, 1997, 390410.

B. V. Cherkassky, A. V. Goldberg, and T. Radzik, Shortest paths algorithms: theory and experimental evaluation, Mathematical Programming 73 , 1996, 129–174.

D. Coppersmith and S. Vinograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computing 9, 1990, 251–280.

Y. Crama and F. C. R. Spieksma, Approximation algorithms for three-dimensional assignment problems with triangle inequalities, European Journal of Operational Research 60 , 1992, 273–279.

W. H. Cunningham, A network simplex method, Mathematical Programming 11, 1976, 105–116.

W. H. Cunningham, Theoretical properties of the network simplex method, Mathematics of Operations Research 4 , 1979, 196–208.

W. H. Cunningham and A. B. Marsh, A primal algorithm for optimum matching, Mathematical Programming Study 8 , 1978, 50–72.

G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963.

V. G. Deineko and V. L. Filonenko, On the reconstruction of specially structured matrices, Aktualnyje Problemy EVM i Programmirovanije, Dnjepropetrovsk, DGU, 1979, (in Russian).

U. Derigs, Alternate strategies for solving bottleneck assignment problems–analysis and computational results, Computing 33, 1984, 95–106.

The shortest augmenting path for solving assignment problems–motivation and computational experience, in Algorithms and Software for Optimization- Part I, Annals of Operations Research 4, C. L. Monma cd., Baltzer, Basel, 1985, 57–102.

U. Derigs, O. Goecke, and R. Schrader, Monge sequences and a simple assignment algorithm, Discrete Applied Mathematics 15 , 1986, 24 1248.

U. Derigs and U. Zimmermann, An augmenting path method for solving linear bottleneck assignment problems, Computing 19, 1978, 285–295.

E. W. Dijkstra, A note on two problems in connection with graphs, Numerische Mathematik 1 , 1959, 269–271.

W. E. Donath, Algorithms and average-value bounds for assignment problems, IBM Journal on Research Development 13, 1969, 380–386.

J. Edmonds and D. R. Fulkerson, Bottleneck extrema, Journal of Combinatorial Theory 8, 1970, 299–306.

P. Erdös and A. Rényi, On random matrices, Pub. Math. Inst. Hung. Acad. of Sciences 8A , 1963, 455–461.

R. Euler, Odd cycles and a class of facets of the axial 3-index assignment polytope, Applicationes mathematicae (Zastowania Matematyki) 19, 1987, 375–386.

R. Euler, R. E. Burkard, and R. Grommes, On Latin squares and the facial structure of related polytopes, Discrete Mathematics 62 , 1986, 155–181.

R. Euler and H. Le Verge, Time-tables, polyhedra and the greedy algorithm, Discrete Applied Mathematics 65 , 1996, 207–221.

T. A. Ewashko and R. C. Dudding, Application of Kuhn’s Hungarian assignment algorithm to posting servicemen, Operations Research 19 , 1971, 991.

D. Fortin and R. Rudolf, Weak algebraic Monge arrays, to appear in Discrete Mathematics, 1998.

M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM 34, 1987, 596–615.

J. B. G. Frenk, M. van Houweninge, and A. H. G. Rinnooy Kan, Order statistics and the linear assignment problem, Computing 39 , 1987, 165174.

A. M. Frieze, Complexity of a 3-dimensional assignment problem, European Journal of Operational Research 13 , 1983, 161–164.

A. M. Frieze and L. Yadegar, An algorithm for solving 3-dimensional assignment problems with application to scheduling in a teaching practice, Journal of the Operational Research Society 32, 1981, 989–995.

R. Fulkerson, I. Glicksberg, and O. Gross, A production line assignment problem, Technical Report RM-1102, The Rand Corporation, Sta. Monica, CA, 1953.

L. R. Ford and D. R. Fulkerson, Maximal flow through a network, Canadian Journal of Mathematics 8, 1956, 399–404.

H. N. Gabow and R. E. Tarjan, A linear time algorithm for a special case of set union, Journal of Computer and System Sciences 30, 1985, 209–221.

H. N. Gabow and R. E. Tarjan, Algorithms for two bottleneck optimization problems, Journal of Algorithms 9, 1988, 411–417.

R. Garfinkel, An improved algorithm for the bottleneck assignment problem, Operations Research 19, 1971, 1747–1751.

F. Glover, Maximum matching in a convex bipartite graph, Naval Research Logistics Quarterly 14, 1967, 313–316.

F. Glover, R. Glover, and D. Klingman, Threshold assignment algorithm, Mathematical Programming Study 26, 1986, 12–37.

F. Glover, D. Karney, and D. Klingman, Implementation and computational study on start procedures and basis change criteria for a primal network code, Networks 4, 1974, 191–212.

F. Glover and D. Klingman, Improved labeling of L.P. bases in networks, Research report CS 218, Center for Cybernetic Studies, University of Texas, Austin, TX, 1974.

M. X. Goemans and M. Kodilian, A lower bound on the expected value of an optimal assignment, Mathematics of Operations Research 18, 1993, 267–274.

A. V. Goldberg and R. Kennedy, An efficient cost scaling algorithm for the assignment problem, Mathematical Programming 75, 1995, 153177.

A. V. Goldberg, S. A. Plotkin, and P. Vaidya, Sublinear-time parallel algorithms for matching and related problems, Journal of Algorithms 14, 1993, 180–213.

A. V. Goldberg and R. E. Tarjan, Finding minimum-cost circulations by successive approximation, Mathematics of Operations Research 15, 1990, 430–466.

D. Goldfarb, Efficient dual simplex methods for the assignment problem, Mathematical Programming 33, 1985, 187–203.

O. Gross, The bottleneck assignment problem, Technical Report P1630, The Rand Corporation, Sta. Monica, CA, 1959.

Ph. Hall, On representatives of subsets, Journal of the London Mathematical Society 10, 1935, 26–30.

P. Hansen and L. Kaufman, A primal-dual algorithm for the three-dimensional assignment problem, Cahiers du CERO 15, 1973, 327–336.

G. H. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, Cambridge University Press, London and New York, 1952.

A. J. Hoffman, On simple linear programming problems, in Convexity, Proceedings of Symposia in Pure Mathematics 7, V. Klee ed., AMS, Providence, RI, 1963, 317–327.

J. E. Hoperoft and R. M. Karp, An n 2 algorithm for maximum matchings in bipartite graphs, SIAM Journal on Computing 2, 1973, 225–231.

M. S. Hung, A polynomial simplex method for the assignment problem, Operations Research 31, 1983, 595–600.

M. S. Hung and W. D. Rom, Solving the assignment problem by relaxation, Operations Research 28, 1980, 969–982.

D. S. Johnson and C. C. McGeoch, eds., Network Flows and Matching - First DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 12, AMS, Providence, RI, 1993.

R. Jonker and A. Volgenant, Improving the Hungarian assignment algorithm, Operations Research Letters 5, 1986, 171–175.

R. Jonker and A. Volgenant, A shortest augmenting path algorithm for dense and sparse linear assignment problems, Computing 38, 1987, 325–340.

R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York, 1972, 85–103.

R. M. Karp, An algorithm to solve the m x n assignment problem in expected time O(mn log n), Networks 10, 1980, 143–152.

R. M. Karp, An upper bound on the expected cost of an optimal assignment, in Discrete Algorithms and Complexity, Academic Press, Boston, 1987, 1–4.

R. M. Karp, A. H. G. Rinnooy Kan, and R. V. Vohra, Average case analysis of a heuristic for the assignment problem, Mathematics of Operations Research 19, 1994, 513–522.

J. Kennington and Z. Wang, Solving dense assignment problems on a shared memory multiprocessor, Report 88-OR-16, Department of Operations Research and Applied Science, Souther Methodist University, Dallas, TX, 1998.

P. Kleinschmidt, C. W. Lee, and H. Schannath, Transportation problem which can be solved by the use of Hirsch paths for the dual problems, Mathematical Programming 37, 1987, 153–168.

B. Klinz, R. Rudolf and G. J. Woeginger, On the recognition of permuted bottleneck Monge matrices, Discrete Applied Mathematics 60, 1995, 223–248.

D. König, Graphok és matrixok, Mat. Fiz. Lapok 38, 1931, 116–119.

J. M. Kurzberg, On approximation methods for the assignment problem, Journal of the ACM 9, 1962, 419–439.

H. W. Kuhn, The Hungarian method for the assignment and transportation problems, Naval Research Logistics Quarterly 2, 1955, 83–97.

E. L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, New York, 1976.

A. J. Lazarus, Certain expected values in the random assignment problem, Operations Research Letters 14, 1993, 207–214.

Y. Lee and J. B. Orlin, On very large scale assignment problems, in Large Scale Optimization: State of the Art, W. W. Hager, D. W. Hearn, and P. M. Pardalos, eds., Kluwer Academic Publishers, Dordrecht, The Netherlands, 1994, pp. 206–244.

R. E. Macho’, An application of the assignment problem, Operations Research 18, 1970, 745–746.

D. Magos, Tabu search for the planar three-index assignment problem, Journal of Global Optimization 8, 1996, 35–48.

D. Magos and P. Miliotis, An algorithm for the planar three-index assignment problem, European Journal of Operational Research 77, 1994, 141–153.

S. Martello, W. R. Pulleyblank, P. Toth, and D. de Werra, Balanced optimization problems, Operations Research Letters 3, 1984, 275–278.

S. Martello and P. Toth, Linear assignment problems, in Surveys in Combinatorial Optimization, Annals of Discrete Mathematics 31, S. Martello, G. Laporte, M. Minoux, and C. Ribeiro, eds., North-Holland, Amsterdam, 1987, pp. 259–282.

M. Mézard and G. Parisi, On the solution of the random link matching problems, Journal de Physique 48, 1987, 1451–1459.

D. Miller, J. Pekny, and G. L. Thompson, Solution of large dense transportation problems using a parallel primal algorithm, Operations Research Letters 9, 1990, 319–324.

K. Mulmuley, U. V. Vazirani, and V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica 7, 1087, 105–113.

R. Murphey, P. M. Pardalos, and L. S. Pitsoulis, A GRASP for the Multitarget Multisensor Tracking Problem, in Network Design: Connectivity and Facilities Location, P. M. Pardalos and D.-Z. Du, eds., DIMACS Series on Discrete Mathematics and Theoretical Computer Science 40, AMS, Providence, RI, 1998, pp. 277–302.

R. Murphey, P. M. Pardalos, and L. S. Pitsoulis, A Parallel GRASP for the Data Association Multidimensional Assignment Problem, in Parallel Processing of Discrete Problems, The IMA Volumes in Mathematics and its Applications 106, Springer Verlag, 1998, pp. 159–180.

B. Neng, Zur Erstellung von optimalen Triebfahrzeugplänen, Zeitschrift für Operations Research 25 , 1981, B159 - B185.

B. Olin, Asymptotic Properties of Random Assignment Problems, Ph.D. Thesis, Division of Optimization and Systems Theory, Department of Mathematics, Royal Institute of Technology, Stockholm, 1992.

J. B. Orlin, On the simplex algorithm for networks and generalized networks, Mathematical Programming Studies 24, 1985, 166–178.

J. B. Orlin and R. K. Ahuja, New scaling algorithms for the assignment and minimum cycle mean problems, Mathematical Programming 54, 1992, 41–56.

E. S. Page, A note on assignment problems, Computer Journal 6, 1963, 241–243.

K. Paparrizos, A non-dual signature method for the assignment problem and a generalization of the dual simplex method for the transportation problem, RAIRO Operations Research 22 , 1988, 269–289.

K. Paparrizos, A relaxation column signature method for assignment problems, European Journal of Operational Research 50 , 1991, 21 1219.

K. Paparrizos, An infeasible (exterior point) simplex algorithm for assignment problems, Mathematical Programming 5 1, 1991, 45–54.

P. M. Pardalos and K. G. Ramakrishnan, On the expected value of random assignment problems: Experimental results and open questions, Computational Optimization and Applications 2 , 1993, 261–271.

J. Peters, The network simplex method on a multiprocessor, Networks 20 , 1990, 845–859.

U. Pferschy, The random linear bottleneck assignment problem, RAIRO Operations Research 30, 1996, 127–142.

U. Pferschy, Solution methods and computational investigations for the linear bottleneck assignment problem, Computing 59, 1997, 237258.

C. Phillips and S. Zenios, Experiences with large scale network optimization on the connection machine, in The Impact of Recent Computing Advances on Operations Research, Operations Research Series 9 , Elsevier, 1989, pp. 169–180.

W. P. Pierskalla, The tri-substitution method for the three- multidimensional assignment problem, Canadian ORS Journal 5 , 1967, 71–81.

W. P. Pierskalla, The multidimensional assignment problem. Operations Research 16, 1968, 422–431.

A. B. Poore, Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking, Computation Optimization and Application 3 , 1994, 27–54.

A. B. Poore, A numerical study of some data association problems arising in multitarget tracking, in Large Scale Optimization: State of the Art, W. W. Hager, D. W. Hearn, and P. M. Pardalos, eds., Kluwer Academic Publishers, Dordrecht, The Netherlands, 1994, pp. 339–361.

A. B. Poore and N. Rijavec, Partitioning multiple data sets: multidimensional assignments and Lagrangian relaxation, in Quadratic assignment and related problems, P. M. Pardalos and H. Wolkowicz, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16, AMS, Providence, RI, 1994, pp. 317–342.

A. B. Poore, N. Rijavec, M. Liggins, and V. Vannicola, Data association problems posed as multidimensional assignment problems: problem formulation, in Signal and Data Processing of Small Targets, O. E. Drummond ed., SPIE, Bellingham, WA, 1993, pp. 552–561.

A. B. Poore and A. J. Robertson III, A new Lagrangean relaxation based algorithm for a class of multidimensional assignment problems, Computational Optimization and Applications 8 , 1997, 129–150.

J. Pusztaszeri, P. E. Reusing, and T. M. Liebling, Tracking elementary particles near their primary vertex: a combinatorial approach, Journal of Global Optimization 16 , 1995, 422–431.

A. P. Punnen and K. P. K. Nair, Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem, Discrete Applied Mathematics 55 , 1994, 91–93.

L. Qi, E. Balas, and G. Gwan, A new facet class and a polyhedral method for the three-index assignment problem, in Advances in Optimization, D.-Z. Du ed., Kluwer Academic Publishers, 1994, pp. 256–274.

K. G. Ramakrishnan, N. K. Karmarkar, and A. P. Kamath, An approximate dual projective algorithm for solving assignment problems, in Network flows and matching- First DIMACS Implementation Challenge, D. S. Johnson and C. C. McGeoch, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 12, AMS, Providence, RI, 1993, pp. 431–449.

F. Rendi, On the complexity of decomposing matrices arising in satellite communication, Operations Research Letters 4 , 1985, 5–8.

E. Roohy-Laleh, Improvements to the theoretical efficiency of the network simplex method, Ph.D. Thesis, Carleton University, Ottawa, 1980.

G. Rote and F. Rendi, Minimizing the density in lay-out design, Operations Research Letters 5 , 1986, 111–118.

J. Shao and W. Wei, A formula for the number of Latin squares, Discrete Mathematics 110 , 1992, 293–296.

J. T. Schwarz, Fast probabilistic algorithms for verification of polynomial identities, Journal of the ACM 27 , 1980, 701–717.

V. Srinivasan and G. L. Thompson, Cost operator algorithms for the transportation problem, Mathematical Programming 12 , 1977, 37 2391.

R. E. Tarjan, Data Structures and Network Algorithms, SIAM, Philadelphia, PA, 1983.

G. L. Thompson, A recursive method for solving assignment problems, in Studies on Graphs and Discrete Programming, Annals of Discrete Mathematics 11, P. Hansen ed., North Holland, Amsterdam, 1981, 319–343.

W. T. Tutte, The factorization of linear graphs, Journal of the London Mathematical Society 22 , 1947, 107–111.

L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8 , 1979, 189–201.

M. Vlach, Branch and bound method for the three-index assignment problem, Ekonomicko-Matematicky Obzor 12 , 1967, 181–191.

A. Volgenant, Linear and semi-assignment problems: A core oriented approach, Computers of Operations Research 23 , 1996, 917–932.

D. W. Walkup, On the expected value of a random assignment problem, SIAM Journal on Computing 8 , 1979, 440–442.

D. W. Walkup, Matching in random regular bipartite digraphs, Discrete Mathematics 31 , 1980, 59–64.

J. Wein and S. Zenios, Massively parallel auction algorithms for the assignment problem, Proceedings of the 3-rd Symposium on the Frontiers of Massively Parallel Computations, 1990, pp. 90–99.

J. Wein and S. Zenios, On the massively parallel solution of the assignment problem, Journal of the Parallel and Distributed Computing 13 , 1991, 221–236.

G. J. Woeginger, private communication.

H. Zaki, A comparison of two algorithms for the assignment problem, Technical Report ORL 90–002, Department of Mechanical and industrial Engineering, University of Illinois, Champaign-Urbana, IL, 1990.

Download references

Author information

Authors and affiliations.

Institute of Mathematics, Technical University Graz, Steyrergasse 30, A-8010, Graz, Austria

Rainer E. Burkard & Eranda Çela

You can also search for this author in PubMed   Google Scholar

Editor information

Editors and affiliations.

Department of Computer Science, University of Minnesota, USA

Ding-Zhu Du

Institute of Applied Mathematics, Academia Sinica, P. R. China

Department of Industrial and Systems Engineering, University of Florida, USA

Panos M. Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 1999 Springer Science+Business Media Dordrecht

About this chapter

Cite this chapter.

Burkard, R.E., Çela, E. (1999). Linear Assignment Problems and Extensions. In: Du, DZ., Pardalos, P.M. (eds) Handbook of Combinatorial Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-1-4757-3023-4_2

Download citation

DOI : https://doi.org/10.1007/978-1-4757-3023-4_2

Publisher Name : Springer, Boston, MA

Print ISBN : 978-1-4419-4813-7

Online ISBN : 978-1-4757-3023-4

eBook Packages : Springer Book Archive

Share this chapter

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

pip install lapx Copy PIP instructions

Released: Mar 21, 2024

Linear Assignment Problem solver (LAPJV/LAPMOD).

Project links

• Open issues:

View statistics for this project via Libraries.io , or by using our public dataset on Google BigQuery

License: BSD License (BSD-2-Clause)

Author: rathaROG

Tags Linear Assignment, LAPJV, LAPMOD, lap

Maintainers

Classifiers

• Science/Research
• OSI Approved :: BSD License
• Microsoft :: Windows
• Python :: 3
• Python :: 3.7
• Python :: 3.8
• Python :: 3.9
• Python :: 3.10
• Python :: 3.11
• Python :: 3.12
• Education :: Testing
• Scientific/Engineering
• Scientific/Engineering :: Mathematics
• Software Development
• Software Development :: Libraries

Project description

Linear Assignment Problem Solver

lapx basically is Tomas Kazmar's gatagat/lap with support for all Windows/Linux/macOS and Python 3.7/3.8/3.9/3.10/3.11/3.12.

• Based on: [ed04ab7752]
• License: BSD-2-Clause, see LICENSE @ gatagat

💽 Installation:

Install from PyPI :

¹ Windows ARM64 is experimental. ² Linux now includes both manylinux and musllinux .

Or install from GitHub repo directly (Require C++ compiler):

Or clone and build on your local machine (Require C++ compiler):

lapx is just the name for package distribution.

The same as lap , use import lap to import; for example:

lap: Linear Assignment Problem solver

lap is a linear assignment problem solver using Jonker-Volgenant algorithm for dense (LAPJV [1]) or sparse (LAPMOD [2]) matrices.

Both algorithms are implemented from scratch based solely on the papers [1,2] and the public domain Pascal implementation provided by A. Volgenant [3].

In my tests the LAPMOD implementation seems to be faster than the LAPJV implementation for matrices with a side of more than ~5000 and with less than 50% finite coefficients.

[1] R. Jonker and A. Volgenant, "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems", Computing 38, 325-340 (1987) [2] A. Volgenant, "Linear and Semi-Assignment Problems: A Core Oriented Approach", Computer Ops Res. 23, 917-932 (1996) [3] http://www.assignmentproblems.com/LAPJV.htm

The function lapjv(C) returns the assignment cost ( cost ) and two arrays, x, y . If cost matrix C has shape N x M, then x is a size-N array specifying to which column is row is assigned, and y is a size-M array specifying to which row each column is assigned. For example, an output of x = [1, 0] indicates that row 0 is assigned to column 1 and row 1 is assigned to column 0. Similarly, an output of x = [2, 1, 0] indicates that row 0 is assigned to column 2, row 1 is assigned to column 1, and row 2 is assigned to column 0.

Note that this function does not return the assignment matrix (as done by scipy's linear_sum_assignment and lapsolver's solve dense ). The assignment matrix can be constructed from x as follows:

Equivalently, we could construct the assignment matrix from y :

Finally, note that the outputs are redundant: we can construct x from y , and vise versa:

Project details

Release history release notifications | rss feed.

Mar 21, 2024

0.5.6 yanked

Mar 20, 2024

Reason this release was yanked:

Wrong info in LONG_DESCRIPTION

Oct 6, 2023

Jul 23, 2023

Jul 19, 2023

0.5.2.post1

Jun 25, 2023

0.5.2 yanked

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages .

Source Distribution

Uploaded Mar 21, 2024 Source

Built Distributions

Uploaded Mar 21, 2024 CPython 3.12 Windows ARM64

Uploaded Mar 21, 2024 CPython 3.12 Windows x86-64

Uploaded Mar 21, 2024 CPython 3.12 musllinux: musl 1.1+ x86-64

Uploaded Mar 21, 2024 CPython 3.12 musllinux: musl 1.1+ ARM64

Uploaded Mar 21, 2024 CPython 3.12 manylinux: glibc 2.17+ ARM64

Uploaded Mar 21, 2024 CPython 3.12 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

Uploaded Mar 21, 2024 CPython 3.12 macOS 11.0+ ARM64

Uploaded Mar 21, 2024 CPython 3.12 macOS 10.9+ x86-64

Uploaded Mar 21, 2024 CPython 3.11 Windows ARM64

Uploaded Mar 21, 2024 CPython 3.11 Windows x86-64

Uploaded Mar 21, 2024 CPython 3.11 musllinux: musl 1.1+ x86-64

Uploaded Mar 21, 2024 CPython 3.11 musllinux: musl 1.1+ ARM64

Uploaded Mar 21, 2024 CPython 3.11 manylinux: glibc 2.17+ ARM64

Uploaded Mar 21, 2024 CPython 3.11 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

Uploaded Mar 21, 2024 CPython 3.11 macOS 11.0+ ARM64

Uploaded Mar 21, 2024 CPython 3.11 macOS 10.9+ x86-64

Uploaded Mar 21, 2024 CPython 3.10 Windows ARM64

Uploaded Mar 21, 2024 CPython 3.10 Windows x86-64

Uploaded Mar 21, 2024 CPython 3.10 musllinux: musl 1.1+ x86-64

Uploaded Mar 21, 2024 CPython 3.10 musllinux: musl 1.1+ ARM64

Uploaded Mar 21, 2024 CPython 3.10 manylinux: glibc 2.17+ ARM64

Uploaded Mar 21, 2024 CPython 3.10 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

Uploaded Mar 21, 2024 CPython 3.10 macOS 11.0+ ARM64

Uploaded Mar 21, 2024 CPython 3.10 macOS 10.9+ x86-64

Uploaded Mar 21, 2024 CPython 3.9 Windows ARM64

Uploaded Mar 21, 2024 CPython 3.9 Windows x86-64

Uploaded Mar 21, 2024 CPython 3.9 musllinux: musl 1.1+ x86-64

Uploaded Mar 21, 2024 CPython 3.9 musllinux: musl 1.1+ ARM64

Uploaded Mar 21, 2024 CPython 3.9 manylinux: glibc 2.17+ ARM64

Uploaded Mar 21, 2024 CPython 3.9 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

Uploaded Mar 21, 2024 CPython 3.9 macOS 11.0+ ARM64

Uploaded Mar 21, 2024 CPython 3.9 macOS 10.9+ x86-64

Uploaded Mar 21, 2024 CPython 3.8 Windows x86-64

Uploaded Mar 21, 2024 CPython 3.8 musllinux: musl 1.1+ x86-64

Uploaded Mar 21, 2024 CPython 3.8 musllinux: musl 1.1+ ARM64

Uploaded Mar 21, 2024 CPython 3.8 manylinux: glibc 2.17+ ARM64

Uploaded Mar 21, 2024 CPython 3.8 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

Uploaded Mar 21, 2024 CPython 3.8 macOS 11.0+ ARM64

Uploaded Mar 21, 2024 CPython 3.8 macOS 10.9+ x86-64

Uploaded Mar 21, 2024 CPython 3.7m Windows x86-64

Uploaded Mar 21, 2024 CPython 3.7m musllinux: musl 1.1+ x86-64

Uploaded Mar 21, 2024 CPython 3.7m musllinux: musl 1.1+ ARM64

Uploaded Mar 21, 2024 CPython 3.7m manylinux: glibc 2.17+ ARM64

Uploaded Mar 21, 2024 CPython 3.7m manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

Uploaded Mar 21, 2024 CPython 3.7m macOS 10.9+ x86-64

Hashes for lapx-0.5.7.tar.gz

Hashes for lapx-0.5.7-cp312-cp312-win_arm64.whl, hashes for lapx-0.5.7-cp312-cp312-win_amd64.whl, hashes for lapx-0.5.7-cp312-cp312-musllinux_1_1_x86_64.whl, hashes for lapx-0.5.7-cp312-cp312-musllinux_1_1_aarch64.whl, hashes for lapx-0.5.7-cp312-cp312-manylinux_2_17_aarch64.manylinux2014_aarch64.whl, hashes for lapx-0.5.7-cp312-cp312-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl, hashes for lapx-0.5.7-cp312-cp312-macosx_11_0_arm64.whl, hashes for lapx-0.5.7-cp312-cp312-macosx_10_9_x86_64.whl, hashes for lapx-0.5.7-cp311-cp311-win_arm64.whl, hashes for lapx-0.5.7-cp311-cp311-win_amd64.whl, hashes for lapx-0.5.7-cp311-cp311-musllinux_1_1_x86_64.whl, hashes for lapx-0.5.7-cp311-cp311-musllinux_1_1_aarch64.whl, hashes for lapx-0.5.7-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl, hashes for lapx-0.5.7-cp311-cp311-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl, hashes for lapx-0.5.7-cp311-cp311-macosx_11_0_arm64.whl, hashes for lapx-0.5.7-cp311-cp311-macosx_10_9_x86_64.whl, hashes for lapx-0.5.7-cp310-cp310-win_arm64.whl, hashes for lapx-0.5.7-cp310-cp310-win_amd64.whl, hashes for lapx-0.5.7-cp310-cp310-musllinux_1_1_x86_64.whl, hashes for lapx-0.5.7-cp310-cp310-musllinux_1_1_aarch64.whl, hashes for lapx-0.5.7-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl, hashes for lapx-0.5.7-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl, hashes for lapx-0.5.7-cp310-cp310-macosx_11_0_arm64.whl, hashes for lapx-0.5.7-cp310-cp310-macosx_10_9_x86_64.whl, hashes for lapx-0.5.7-cp39-cp39-win_arm64.whl, hashes for lapx-0.5.7-cp39-cp39-win_amd64.whl, hashes for lapx-0.5.7-cp39-cp39-musllinux_1_1_x86_64.whl, hashes for lapx-0.5.7-cp39-cp39-musllinux_1_1_aarch64.whl, hashes for lapx-0.5.7-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl, hashes for lapx-0.5.7-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl, hashes for lapx-0.5.7-cp39-cp39-macosx_11_0_arm64.whl, hashes for lapx-0.5.7-cp39-cp39-macosx_10_9_x86_64.whl, hashes for lapx-0.5.7-cp38-cp38-win_amd64.whl, hashes for lapx-0.5.7-cp38-cp38-musllinux_1_1_x86_64.whl, hashes for lapx-0.5.7-cp38-cp38-musllinux_1_1_aarch64.whl, hashes for lapx-0.5.7-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl, hashes for lapx-0.5.7-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl, hashes for lapx-0.5.7-cp38-cp38-macosx_11_0_arm64.whl, hashes for lapx-0.5.7-cp38-cp38-macosx_10_9_x86_64.whl, hashes for lapx-0.5.7-cp37-cp37m-win_amd64.whl, hashes for lapx-0.5.7-cp37-cp37m-musllinux_1_1_x86_64.whl, hashes for lapx-0.5.7-cp37-cp37m-musllinux_1_1_aarch64.whl, hashes for lapx-0.5.7-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl, hashes for lapx-0.5.7-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl, hashes for lapx-0.5.7-cp37-cp37m-macosx_10_9_x86_64.whl.

• português (Brasil)

Supported by

Search code, repositories, users, issues, pull requests...

Provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications

Linear Assignment Problem solver (LAPJV/LAPMOD).

gatagat/lap

Folders and files, repository files navigation.

lap: Linear Assignment Problem solver

lap is a linear assignment problem solver using Jonker-Volgenant algorithm for dense (LAPJV [1]) or sparse (LAPMOD [2]) matrices.

Both algorithms are implemented from scratch based solely on the papers [1,2] and the public domain Pascal implementation provided by A. Volgenant [3].

In my tests the LAPMOD implementation seems to be faster than the LAPJV implementation for matrices with a side of more than ~5000 and with less than 50% finite coefficients.

[1] R. Jonker and A. Volgenant, "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems", Computing 38, 325-340 (1987) [2] A. Volgenant, "Linear and Semi-Assignment Problems: A Core Oriented Approach", Computer Ops Res. 23, 917-932 (1996) [3] http://www.assignmentproblems.com/LAPJV.htm

Installation

Runtime dependencies.

Running lap requires:

• Python (2.7, 3.7, 3.8, 3.9)
• NumPy (>=1.10.1)

In addition to above, running the tests requires:

• SciPy, pytest, pytest-timeout

Install using pip

You can install the latest release of lap from PyPI (recommended):

Alternatively, you can install lap directly from the repository:

In some cases installing from PyPI results in building the package, in these cases make sure to check "Install from source" below.

Install from source

Install a C++ compiler (e.g., g++)

Python headers (e.g., python-dev package on Debian/Ubuntu)

Install Cython (>=0.21)

Under the root of the repo

On Windows, the build may fail if there is a mismatch between the MSVC compiler version used for the build and the version used to build Python itself. For more information see this stackoverflow answer .

Tested under Linux, OS X, Windows.

The function lapjv(C) returns the assignment cost ( cost ) and two arrays, x, y . If cost matrix C has shape N x M, then x is a size-N array specifying to which column is row is assigned, and y is a size-M array specifying to which row each column is assigned. For example, an output of x = [1, 0] indicates that row 0 is assigned to column 1 and row 1 is assigned to column 0. Similarly, an output of x = [2, 1, 0] indicates that row 0 is assigned to column 2, row 1 is assigned to column 1, and row 2 is assigned to column 0.

Note that this function does not return the assignment matrix (as done by scipy's linear_sum_assignment and lapsolver's solve dense ). The assignment matrix can be constructed from x as follows:

Equivalently, we could construct the assignment matrix from y :

Finally, note that the outputs are redundant: we can construct x from y , and vise versa:

Released under the 2-clause BSD license, see LICENSE .

Copyright (C) 2012-2017, Tomas Kazmar

Used by 3.1k

Contributors 5

• Python 62.8%
• Cython 5.4%

• By logging in you accept our terms of service and privacy policy

lap05 Release 0.5.1

Release 0.5.1 toggle dropdown 0.5.1 0.5.0.

Linear Assignment Problem solver (LAPJV/LAPMOD).

Homepage PyPI Python

Documentation

lap: Linear Assignment Problem solver

lap is a linear assignment problem solver using Jonker-Volgenant algorithm for dense (LAPJV [1]) or sparse (LAPMOD [2]) matrices.

Both algorithms are implemented from scratch based solely on the papers [1,2] and the public domain Pascal implementation provided by A. Volgenant [3].

In my tests the LAPMOD implementation seems to be faster than the LAPJV implementation for matrices with a side of more than ~5000 and with less than 50% finite coefficients.

[1] R. Jonker and A. Volgenant, "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems", Computing 38, 325-340 (1987) [2] A. Volgenant, "Linear and Semi-Assignment Problems: A Core Oriented Approach", Computer Ops Res. 23, 917-932 (1996) [3] http://www.assignmentproblems.com/LAPJV.htm

Installation

Runtime dependencies.

Running lap requires:

• Python (2.7, 3.7, 3.8, 3.9)
• NumPy (>=1.10.1)

In addition to above, running the tests requires:

• SciPy, pytest, pytest-timeout

Install using pip

You can install the latest release of lap from PyPI (recommended):

Alternatively, you can install lap directly from the repository:

In some cases installing from PyPI results in building the package, in these cases make sure to check "Install from source" below.

Install from source

Install a C++ compiler (e.g., g++)

Python headers (e.g., python-dev package on Debian/Ubuntu)

Install Cython (>=0.21)

Under the root of the repo

On Windows, the build may fail if there is a mismatch between the MSVC compiler version used for the build and the version used to build Python itself. For more information see this stackoverflow answer .

Tested under Linux, OS X, Windows.

The function lapjv(C) returns the assignment cost ( cost ) and two arrays, x, y . If cost matrix C has shape N x M, then x is a size-N array specifying to which column is row is assigned, and y is a size-M array specifying to which row each column is assigned. For example, an output of x = [1, 0] indicates that row 0 is assigned to column 1 and row 1 is assigned to column 0. Similarly, an output of x = [2, 1, 0] indicates that row 0 is assigned to column 2, row 1 is assigned to column 1, and row 2 is assigned to column 0.

Note that this function does not return the assignment matrix (as done by scipy's linear_sum_assignment and lapsolver's solve dense ). The assignment matrix can be constructed from x as follows:

Equivalently, we could construct the assignment matrix from y :

Finally, note that the outputs are redundant: we can construct x from y , and vise versa:

Released under the 2-clause BSD license, see LICENSE .

Copyright (C) 2012-2017, Tomas Kazmar

The Tidelift Subscription provides access to a continuously curated stream of human-researched and maintainer-verified data on open source packages and their licenses, releases, vulnerabilities, and development practices.

See all contributors

Something wrong with this page? Make a suggestion

Export .ABOUT file for this package

Last synced: 2022-04-22 18:25:35 UTC

Login to resync this project

Linear (sum) assignment problem

Description.

Compute the best bipartite matching using one of three methods. For an n x n score matrix it find \max_{v\in \Pi_n} \sum_{i=1}^n score_{i, v(i)} where \Pi_n denotes all permutations on n objects.

Solves a linear assignment using one of three methods. "clue" uses solve_lsap from the clue package. "lapjv" uses the Jonker-Volgenaut approach implemented in this package. "lapmod" use a modification of JV that exploits sparsity in the score matrix.

Scores do not need to be non-negative. For "clue" the scores are pre-translated to be non-negative which preserves the LAP solution.

do_lap returns a vector which indicates the best matching column for each row.

R. Jonker, A. Volgenant (1987). A shortest augmenting path algorithm for dense and sparse linear assignment problems . Computing, pages 325-340.

A. Volgenant (1996). Linear and Semi-Assignment Problems: A Core Oriented Approach . Computer Ops Res., pages 917-932.

C. H. Papadimitriou and K. Steiglitz (1998). Combinatorial Optimization: Algorithms and Complexity . Courier Corporation.

Linear (sum) assignment problem

Compute the best bipartite matching using one of three methods. For an n x n score matrix it find \(\max_{v\in \Pi_n} \sum_{i=1}^n score_{i, v(i)}\) where \(\Pi_n\) denotes all permutations on n objects.

matrix of pairwise scores

One of "lapjv", "lapmod", or "clue"

do_lap returns a vector which indicates the best matching column for each row.

Solves a linear assignment using one of three methods. "clue" uses solve_lsap from the clue package. "lapjv" uses the Jonker-Volgenaut approach implemented in this package. "lapmod" use a modification of JV that exploits sparsity in the score matrix.

Scores do not need to be non-negative. For "clue" the scores are pre-translated to be non-negative which preserves the LAP solution.

R. Jonker, A. Volgenant (1987). A shortest augmenting path algorithm for dense and sparse linear assignment problems . Computing, pages 325-340.

A. Volgenant (1996). Linear and Semi-Assignment Problems: A Core Oriented Approach . Computer Ops Res., pages 917-932.

C. H. Papadimitriou and K. Steiglitz (1998). Combinatorial Optimization: Algorithms and Complexity . Courier Corporation.

dpmcsuss/iGraphMatch Tools for Graph Matching

• best_matches: Rank best matches
• C.Elegans: Chemical synapses and electrical synapses networks of...
• center_graph: Center adjacency matrix
• check_graph: Parameter checking for a graph-pair
• check_seeds: Standardize seeds input data type
• check_sim: Check the similarity matrix passed to a matching function
• do_lap: Linear (sum) assignment problem
• Enron: Email communication networks of Enron Corporation
• get_perm_mat: Get Permutation
• gm: Graph Matching Methods
• gm_fw: Frank-Wolfe Graph Matching Methods
• gm_isorank: Spectral Graph Matching Methods: IsoRank Algorithm
• gm_perco: Percolation Graph Matching Methods
• gm_Umeyama: Spectral Graph Matching Methods: Umeyama Algorithm
• graphMatch_constructor: Graph matching results class
• graphMatch_methods: Methods for the graphMatch class
• graphMatch_operators: Operator methods for graphMatch objects
• graphMatch_summary: Summary methods for graphMatch objects
• iGraphMatch-package: iGraphMatch: Tools for Graph Matching
• init_start: Initialization of the start matrix
• innerproduct: Matrix inner products
• lapjv: Solves a linear assignment problem using the Jonker-Vogenant...
• largest_common_cc: Find the largest common connected subgraph (LCCS) of two...
• matrix_list: Lists of Matrices
• pad: Pad a matrix object with extra rows/columns of 0s.
• plot_graphMatch: Plotting methods for visualizing matches
• sample_gnp: Sample correlated G(n,p) random graphs
• sample_ieg: Sample graphs from edge probability matrix and correlation...
• sample_sbm: Sample graphs pair from stochastic block model
• split_igraph: Split an igraph object into aligned graphs by attribute
• splr_constructor: Sparse Plus Low-Rank Matrices
• splrMatrix_method: "SPLR" Methods
• splr_sparse_plus_constant: Add a constant to a splrMatrix object
• splr_to_sparse: Convert splr "Matrix" to Sparse
• Transportation: Britain Transportation Network
• Browse all...

do_lap : Linear (sum) assignment problem In dpmcsuss/iGraphMatch: Tools for Graph Matching

View source: R/lap.R

Linear (sum) assignment problem

Description.

Compute the best bipartite matching using one of three methods. For an n x n score matrix it find \max_{v\in \Pi_n} \sum_{i=1}^n score_{i, v(i)} where \Pi_n denotes all permutations on n objects.

Solves a linear assignment using one of three methods. "clue" uses solve_lsap from the clue package. "lapjv" uses the Jonker-Volgenaut approach implemented in this package. "lapmod" use a modification of JV that exploits sparsity in the score matrix.

Scores do not need to be non-negative. For "clue" the scores are pre-translated to be non-negative which preserves the LAP solution.

do_lap returns a vector which indicates the best matching column for each row.

R. Jonker, A. Volgenant (1987). A shortest augmenting path algorithm for dense and sparse linear assignment problems . Computing, pages 325-340.

A. Volgenant (1996). Linear and Semi-Assignment Problems: A Core Oriented Approach . Computer Ops Res., pages 917-932.

C. H. Papadimitriou and K. Steiglitz (1998). Combinatorial Optimization: Algorithms and Complexity . Courier Corporation.

Related to do_lap in dpmcsuss/iGraphMatch ...

R package documentation, browse r packages, we want your feedback.

Add the following code to your website.

REMOVE THIS Copy to clipboard

For more information on customizing the embed code, read Embedding Snippets .