dense and sparse linear assignment problems

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 for .NET.

fuglede/linearassignment

pymatgen.optimization package
Edit on GitHub

pymatgen.optimization package 

Optimization utilities.

Submodules 

Pymatgen.optimization.linear_assignment module .

This module contains an algorithm to solve the Linear Assignment Problem

Bases: object

This class finds the solution to the Linear Assignment Problem. It finds a minimum cost matching between two sets, given a cost matrix.

This class is an implementation of the LAPJV algorithm described in: R. Jonker, A. Volgenant. A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38, 325-340 (1987)

costs – The cost matrix of the problem. cost[i,j] should be the cost of matching x[i] to y[j]. The cost matrix may be rectangular

epsilon – Tolerance for determining if solution vector is < 0

pymatgen.optimization.neighbors module 

For each point in center_coords , get all the neighboring points in all_coords that are within the cutoff radius r . All the coordinates should be Cartesian.

all_coords – (np.ndarray[double, dim=2]) all available points. When periodic boundary is considered, this is all the points in the lattice.

center_coords – (np.ndarray[double, dim=2]) all centering points

r – (float) cutoff radius

pbc – (np.ndarray[long, dim=1]) whether to set periodic boundaries

lattice – (np.ndarray[double, dim=2]) 3x3 lattice matrix

tol – (float) numerical tolerance

min_r – (float) minimal cutoff to calculate the neighbor list directly. If the cutoff is less than this value, the algorithm will calculate neighbor list using min_r as cutoff and discard those that have larger distances.

index1 (n, ), index2 (n, ), offset_vectors (n, 3), distances (n, ). index1 of center_coords, and index2 of all_coords that form the neighbor pair offset_vectors are the periodic image offsets for the all_coords.

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

A shortest augmenting path algorithm for dense and sparse linear assignment problems

6,693 citations

2,229 citations

1,753 citations

View 1 citation excerpt

Cites methods from "A shortest augmenting path algorith..."

... Here we present a tracking algorithm that uses one mathematical framework, the linear assignment problem (LAP ...

1,726 citations

... In this work we report results using graph matching (Jonker and Volgenant, 1987). ...

1,091 citations

... Jonker–Volgenant–Castanon (JVC) assignment algorithm [16] to solve this assignment problem. ...

22,704 citations

View 1 reference excerpt

"A shortest augmenting path algorith..." refers methods in this paper

... It requires only a simple modification of the shortest path method of Dijkstra [12]. ...

11,096 citations

7,221 citations

... Linear assignment is a special case of minimum cost flow, for which an algorithm exists called "Buildup" in Papadimitriou and Steiglitz [26]. ...

4,341 citations

3,478 citations

Related Papers (5)

Ask Copilot

A comparison of two algorithms for the assignment problem

Published: January 1995
Volume 4 , pages 23–45, ( 1995 )

Cite this article

Hossam A. Zaki 1

117 Accesses

7 Citations

Explore all metrics

State-of-the-art computational results have shown that the shortest augmenting path (SAP) methods are more efficient than other primal-dual and primal-simplex based methods for solving the linear assignment problem on uniprocessor computers. There is, however, some controversy concerning their merits when compared with Bertsekas' auction algorithm on multiprocessor computers. In this study we investigate the performance of these competing methods on the Alliant FX/8. For each method, theoretical motivation, sources of parallelism and computational results are presented.

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

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Primal–Dual and Dual-Fitting Analysis of Online Scheduling Algorithms for Generalized Flow-Time Problems

Spyros Angelopoulos, Giorgio Lucarelli & Nguyen Kim Thang

Primal-Dual and Dual-Fitting Analysis of Online Scheduling Algorithms for Generalized Flow Time Problems

Partial Solutions and MultiFit Algorithm for Multiprocessor Scheduling

Giuseppe Paletta & Alex J. Ruiz-Torres

R.K. Ahuja, T.L. Magnanti and J.B. Orlin, 1989, “Network Flows”, Chapter IV in Handbooks of Operations Research and Management Science, Volume 1: Optimization , G. Nemhauser, A. Rinnooy Kan, and M. Todd (eds.), North-Holland, Amsterdam.

Google Scholar

E. Balas, D. Miller, J. Pekny and P. Toth, 1989, “A Parallel Shortest Path Algorithm for the Assignment Problem”, Technical Report No. MSRR 552, Carnegie Mellon University, Pittsburgh, PA.

D. Bertsekas, 1981, “A New Algorithm for the Assignment Problem”, Mathematical Programming , 21, 152–171.

D. Bertsekas, 1988, “The Auction Algorithm: A Distributed Relaxation Method for the Assignment Problem”, Annals of Operations Research , 14, 105–123.

D. Bertsekas and J. Eckstein, 1988, “Dual Coordinate Step Methods for Linear Network Flow Problems”, Mathematical Programming , Series B, 42, 203–243.

D. Bertsekas and J.N. Tsitsiklis, 1989, Parallel and Distributed Computation: Numerical Methods , Prentice-Hall, Englewood Cliffs, NJ.

J. Derigs, 1985, “The Shortest Augmenting Path Method for Solving Assignment Problems-Motivation and Computational Experience”, Annals of Operations Research , 4, 57–102.

J. Edmonds and R.M. Karp, 1972, “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems”, Journal of the ACM , 19, 248–264.

R. Jonker and T. Volgenant, 1987, “A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems”, Computing , 38, 325–340.

R.M. Karp, 1980, “An Algorithm to Solve the m×n Assignment Problem in Expected Time O( mn log n )”, Networks , 10, 143–152.

D. Kempka, J. Kennington and H. Zaki, 1991, “Performance Characteristics of the Jacobi and the Gauss-Seidel Versions of the Auction Algorithm on the Alliant FX/8”, ORSA Journal on Computing , 3, 92–106.

J. Kennington and Z. Wang, 1991, “An Empirical Analysis of the Dense Assignment Problem: Sequential and Parallel Implementations”, ORSA Journal on Computing , 3, 299–306.

N. Tomizawa, 1971, “On Some Techniques Useful for the Solution of Transportation Problems”, Networks , 1, 173–194.

Download references

Author information

Authors and affiliations.

SABRE Decision Technologies, DFW Airport, Box 619616-MD4479, 75261-9616, TX

Hossam A. Zaki

You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Zaki, H.A. A comparison of two algorithms for the assignment problem. Comput Optim Applic 4 , 23–45 (1995). https://doi.org/10.1007/BF01299157

Download citation

Received : 30 March 1993

Revised : 23 February 1994

Issue Date : January 1995

DOI : https://doi.org/10.1007/BF01299157

Share this article

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

auction algorithm
shortest augmenting path method
parallel computing
Find a journal
Publish with us
Track your research

IMAGES

[PDF] A shortest augmenting path algorithm for dense and sparse linear
Dense and Sparse Graphs
Linear Systems and Sparse Matrices with Numpy and Scipy
Sparse vs. Dense Matrices Lecture 20 Sparse Matrix Algorithms
Sparse Matrices · Matt Eding
[PDF] A shortest augmenting path algorithm for dense and sparse linear

VIDEO

Scipy: Sparse Linear Algebra
sparse matrics assignment 1
Black Holes: The Unseen Universe #usa #india #canada #uk #brasil #australia #philippines #germany
Any Subgroup of (R,+) is either cyclic or dense in R
LINEAR REGRESSION DEK3033
SPARSE MULTIPLICATION||DSA||VIDEO||ASSIGNMENT

COMMENTS

PDF A shortest augmenting path algorithm for dense and sparse linear
A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems 327 In this group two algorithms, both of complexity O (n3), stand out: Hung and Rom's [18] and Tomizawa's [29]. The former is the more ingenious, but the latter the fastest, as shown in Section 8.
PDF and sparse linear assignment problems
A shortest augmenting path algorithm for dense and sparse linear assignment problems Roy Jonker Ton Volgenant The linear assignment problem (LAP) is useful as a relaxation for difficult combinatorial optimization problems (quadratic assignment, travelling sales man). Theoretical developments for the LAP can often be extended to prob ...
A shortest augmenting path algorithm for dense and sparse linear
We develop a shortest augmenting path algorithm for the linear assignment problem. It contains new initialization routines and a special implementation of Dijkstra's shortest path method. For both dense and sparse problems computational experiments show this algorithm to be uniformly faster than the best algorithms from the literature. A Pascal implementation is presented.
Linear Assignment Problems and Extensions
Abstract. 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".
Linear assignment procedures
The Linear Assignment Problem (LAP) is both useful itself as well as a relaxation for difficult combinatorial optimization problems like quadratic assignment and the Traveling Salesman Problem. ... Derigs and Metz (1986) have suggested to exploit the speed of algorithms for sparse problems for the solution of dense problems by selecting the ...
sg:pub.10.1007/bf02278710
We develop a shortest augmenting path algorithm for the linear assignment problem. It contains new initialization routines and a special implementation of Dijkstra's shortest path method. For both dense and sparse problems computational experiments show this algorithm to be uniformly faster than the best algorithms from the literature.
lapjv · PyPI
R. Jonker and A. Volgenant, "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems," Computing, vol. 38, pp. 325-340, 1987. This paper is not publicly available though a brief description exists on sciencedirect.com. JV is faster in than the Hungarian algorithm in practice, though the complexity is the same - O(n 3).
GitHub
R. Jonker and A. Volgenant. A Shortest Augmenting Path Algorithm for. Dense and Sparse Linear Assignment Problems. *Computing*, 38:325-340. December 1987. and our implementation is a port of the Pascal code available here. We also include a different method based on the pseudoflow approach to solving minimum cost flow problems.
Algorithm 1015: A Fast Scalable Solver for the Dense Linear (Sum
We present a new algorithm for solving the dense linear (sum) assignment problem and an efficient, parallel implementation that is based on the successive shortest path algorithm. More specifically, we introduce the well-known epsilon scaling approach ...
A Shortest Augmenting Path Algorithm for the Semi-Assignment Problem
The software implementations of our algorithm are fastest for the semi-assignment problems that we tested. Our dense code is also faster than the best software for assignment problems. ... R., AND T. VOLGENANT. 1987. A Shortest Aug menting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38, 325-340. Google Scholar ...
A shortest augmenting path algorithm for dense and sparse linear
We develop a shortest augmenting path algorithm for the linear assignment problem. It contains new initialization routines and a special implementation of Dijkstra's shortest path method. For both dense and sparse problems computational experiments show this algorithm to be uniformly faster than the best algorithms from the literature.
A shortest augmenting path algorithm for dense and sparse linear
Abstract. The linear assignment problem (LAP) is useful as a relaxation for difficult combinatorial optimization problems (quadratic assignment, travelling salesman). Theoretical developments for the LAP can often be extended to problems as minimum cost flow and transportation. Download to read the full chapter text.
pymatgen.optimization package
This class finds the solution to the Linear Assignment Problem. It finds a minimum cost matching between two sets, given a cost matrix. This class is an implementation of the LAPJV algorithm described in: R. Jonker, A. Volgenant. A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38, 325-340 (1987)
A parallel shortest augmenting path algorithm for the assignment problem
21 MARTELLO, S. AND TOTH, P. Linear assignment problems. Ann. Dis. Math. 31 (1987), 259-282. Google Scholar; ... Tests of the parallel algorithm, implemented for both sparse and dense problems on a 14-processor Butterfly computer, indicate substantial speedup over SAP and suggest that the efficiency of the algorithm depends heavily on the ratio ...
lapx · PyPI
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].
The shortest augmenting path method for solving assignment problems
This paper discusses the shortest augmenting path method for solving assignment problems and introduces this basic concept using matching theory, which naturally leads to a new, highly efficient hybrid approach for solving large-scale dense assignment problems. In this paper we discuss the shortest augmenting path method for solving assignment problems in the following respect:we introduce ...
The Linear Assignment Problem
We present a broad survey of recent polynomial algorithms for the linear assignment problem. They all use essentially alternating trees and/or strongly feasible trees. ... R. Jonker and A. Volgenant, A shortest path algorithm for dense and sparse linear assignment problems, Computing 38 (1987) 325-340. Article MathSciNet MATH Google Scholar ...
A shortest augmenting path algorithm for dense and sparse linear
(DOI: 10.1007/BF02278710) We develop a shortest augmenting path algorithm for the linear assignment problem. It contains new initialization routines and a special implementation of Dijkstra's shortest path method. For both dense and sparse problems computational experiments show this algorithm to be uniformly faster than the best algorithms from the literature. A Pascal implementation is ...
A shortest augmenting path algorithm for dense and sparse linear
The multiple pairs shortest path problem (MPSP) arises in many applications where the shortest paths and distances between only some specific pairs of origin-destination (OD) nodes in a network are desired. The traditional repeated single-source ... The input to an inverse shortest path lengths problem (ISPL) consists of a graph G with arc ...
An efficient labeling technique for solving sparse assignment problems
A new implementation of the shortest augmenting path approach for solving sparse assignment problems and computational experience documenting its efficiency is described. We describe a new implementation of the shortest augmenting path approach for solving sparse assignment problems and report computational experience documenting its efficiency.ZusammenfassungWir beschreiben eine neue ...
Deep Learning for Bipartite Assignment Problems<sup>*</sup>
Many assignment problems cannot be solved to optimality in real-time. The existing literature tends to focus on the development of handcrafted heuristics that exploit the structure of a particular assignment problem. We instead seek a general-purpose approach that can automatically learn such heuristics.
A comparison of two algorithms for the assignment problem
State-of-the-art computational results have shown that the shortest augmenting path (SAP) methods are more efficient than other primal-dual and primal-simplex based methods for solving the linear assignment problem on uniprocessor computers. There is, however, some controversy concerning their merits when compared with Bertsekas' auction algorithm on multiprocessor computers. In this study we ...