jvc assignment algorithm

• Presentations
• Advanced Photonics
• Advanced Photonics Nexus
• Biophotonics Discovery
• Journal of Applied Remote Sensing
• Journal of Astronomical Telescopes, Instruments, and Systems
• Journal of Biomedical Optics
• Journal of Electronic Imaging
• Journal of Medical Imaging
• Journal of Micro/Nanopatterning, Materials, and Metrology
• Journal of Nanophotonics
• Journal of Optical Microsystems
• Journal of Photonics for Energy
• Neurophotonics
• Optical Engineering
• Photonics Insights
• Google Scholar citations
• Citing works
• DOWNLOAD PAPER SAVE TO MY LIBRARY

Show All Keywords

Keywords/phrases, publication years.

IEEE Account

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

Solve linear assignment problem using LAPJV

Use the algorithm of Jonker and Volgenant (1987) to solve the Linear Sum Assignment Problem (LSAP).

Matrix of costs.

LAPJV() returns a list with two entries: score , the score of the optimal matching; and matching , the columns matched to each row of the matrix in turn.

The Linear Assignment Problem seeks to match each row of a matrix with a column, such that the cost of the matching is minimized.

The Jonker & Volgenant approach is a faster alternative to the Hungarian algorithm (Munkres 1957) , which is implemented in clue::solve_LSAP() .

Note: the JV algorithm expects integers. In order to apply the function to a non-integer n , as in the tree distance calculations in this package, each n is multiplied by the largest available integer before applying the JV algorithm. If two values of n exhibit a trivial difference – e.g. due to floating point errors – then this can lead to interminable run times. (If numbers of the magnitude of billions differ only in their last significant digit, then the JV algorithm may undergo billions of iterations.) To avoid this, integers over 2^22 that differ by a value of 8 or less are treated as equal.

Jonker R, Volgenant A (1987). “A shortest augmenting path algorithm for dense and sparse linear assignment problems.” Computing , 38 , 325–340. doi:10.1007/BF02278710 . Munkres J (1957). “Algorithms for the assignment and transportation problems.” Journal of the Society for Industrial and Applied Mathematics , 5 (1), 32–38. doi:10.1137/0105003 .

Implementations of the Hungarian algorithm exist in adagio , RcppHungarian , and clue and lpSolve ; for larger matrices, these are substantially slower. (See discussion at Stack Overflow .)

The JV algorithm is implemented for square matrices in the Bioconductor package GraphAlignment::LinearAssignment() .

C++ code by Roy Jonker, MagicLogic Optimization Inc. [email protected] , with contributions from Yong Yang [email protected] , after Yi Cao

• DOI: 10.1117/12.392018
• Corpus ID: 62540202

Performance comparison of 2D assignment algorithms for assigning truth objects to measured tracks

• M. Levedahl
• Published in SPIE Defense + Commercial… 13 July 2000
• Computer Science, Engineering, Mathematics

22 Citations

Explicit pattern matching assignment algorithm, don't be greedy, be neighborly, a new assignment algorithm, a comparison of track to truth assignment methods, a track purity approach for tracking metrics, on implementing 2d rectangular assignment algorithms, some assignment problems arising from multiple target tracking, pattern metrics for groups of target tracks, advances in displaying uncertain estimates of multiple targets, estimation, decision and applications to target tracking, 5 references, algorithms for the assignment and transiortation troblems*, best hypothesis target tracking and sensor fusion, related papers.

Showing 1 through 3 of 0 Related Papers

Solve linear assignment problem using LAPJV

Description.

Use the algorithm of Jonker and Volgenant (1987) to solve the Linear Sum Assignment Problem (LSAP).

The Linear Assignment Problem seeks to match each row of a matrix with a column, such that the cost of the matching is minimized.

The Jonker & Volgenant approach is a faster alternative to the Hungarian algorithm (Munkres 1957), which is implemented in clue::solve_LSAP() .

Note: the JV algorithm expects integers. In order to apply the function to a non-integer n , as in the tree distance calculations in this package, each n is multiplied by the largest available integer before applying the JV algorithm. If two values of n exhibit a trivial difference – e.g. due to floating point errors – then this can lead to interminable run times. (If numbers of the magnitude of billions differ only in their last significant digit, then the JV algorithm may undergo billions of iterations.) To avoid this, integers over 2^22 that differ by a value of 8 or less are treated as equal.

LAPJV() returns a list with two entries: score , the score of the optimal matching; and matching , the columns matched to each row of the matrix in turn.

C++ code by Roy Jonker, MagicLogic Optimization Inc. [email protected] , with contributions from Yong Yang [email protected] , after Yi Cao

Jonker R, Volgenant A (1987). “A shortest augmenting path algorithm for dense and sparse linear assignment problems.” Computing , 38 , 325–340. doi:10.1007/BF02278710 . Munkres J (1957). “Algorithms for the assignment and transportation problems.” Journal of the Society for Industrial and Applied Mathematics , 5 (1), 32–38. doi:10.1137/0105003 .

Implementations of the Hungarian algorithm exist in adagio , RcppHungarian , and clue and lpSolve ; for larger matrices, these are substantially slower. (See discussion at Stack Overflow .)

The JV algorithm is implemented for square matrices in the Bioconductor package GraphAlignment::LinearAssignment() .

Evaluation of the Jonker-Volgenant-Castanon (JVC) assignment algorithm for track association

• Malkoff, Donald B.

The Jonker-Volgenant-Castanon (JVC) assignment algorithm was used by Lockheed Martin Advanced Technology Laboratories (ATL) for track association in the Rotorcraft Pilot's Associate (RPA) program. RPA is Army Aviation's largest science and technology program, involving an integrated hardware/software system approach for a next generation helicopter containing advanced sensor equipments and applying artificial intelligence `associate' technologies. ATL is responsible for the multisensor, multitarget, onboard/offboard track fusion. McDonnell Douglas Helicopter Systems is the prime contractor and Lockheed Martin Federal Systems is responsible for developing much of the cognitive decision aiding and controls-and-displays subsystems. RPA is scheduled for flight testing beginning in 1997. RPA is unique in requiring real-time tracking and fusion for large numbers of highly-maneuverable ground (and air) targets in a target-dense environment. It uses diverse sensors and is concerned with a large area of interest. Target class and identification data is tightly integrated with spatial and kinematic data throughout the processing. Because of platform constraints, processing hardware for track fusion was quite limited. No previous experience using JVC in this type environment had been reported. ATL performed extensive testing of the JVC, concentrating on error rates and run- times under a variety of conditions. These included wide ranging numbers and types of targets, sensor uncertainties, target attributes, differing degrees of target maneuverability, and diverse combinations of sensors. Testing utilized Monte Carlo approaches, as well as many kinds of challenging scenarios. Comparisons were made with a nearest-neighbor algorithm and a new, proprietary algorithm (the `Competition' algorithm). The JVC proved to be an excellent choice for the RPA environment, providing a good balance between speed of operation and accuracy of results.

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

Tracking Closely Maneuvering Targets in Clutter with an IMM-JVC Algorithm

2002, Multisensor Fusion

Introduction to Assignment Methods in Tracking Systems

In a multiple target tracking (MTT) system, one or more sensors generate multiple detections from multiple targets in a scan. To track these targets, one essential step is to assign these detections correctly to the targets or tracks maintained in the tracker so that these detections can be used to update these tracks. If the number of targets or detections is large, or there are conflicts between different assignment hypotheses, assigning detections is challenging.

Depending on the dimension of the assignment, assignment problems can be categorized into:

2-D assignment problem – assigns n targets to m observations. For example, assign 5 tracks to 6 detections generated from one sensor at one time step.

S-D assignment problem – assigns n targets to a set ( m 1 , m 2 , m 3 , …) of observations. For example, assign 5 tracks to 6 detections from one sensor, and 4 detections from another sensor at the same time. This example is a typical 3-D assignment problem.

To illustrate the basic idea of an assignment problem, consider a simple 2-D assignment example. One company tries to assign 3 jobs to 3 workers. Because of the different experience levels of the workers, not all workers are able to complete each job with the same effectiveness. The cost (in hours) of each worker to finish each job is given by the cost matrix shown in the table. An assignment rule is that each worker can only take one job, and one job can only be taken by one worker. To guarantee efficiency, the object of this assignment is to minimize the total cost.

Since the numbers of workers and jobs are both small in this example, all the possible assignments can be obtained by enumeration, and the minimal cost solution is highlighted in the table with assignment pairs (1, 3), (2, 2) and (3, 1). In practice, as the size of the assignment becomes larger, the optimal solution is difficult to obtain for 2-D assignment. For an S-D assignment problem, the optimal solution may not be obtainable in practice.

2-D Assignment in Multiple Target Tracking

In the 2-D MTT assignment problem, a tracker tries to assign multiple tracks to multiple detections. Other than the dimensionality challenge mentioned above, a few other factors can significantly change the complexity of the assignment:

Target or detection distribution — If targets are sparsely distributed, associating a target to its corresponding detection is relatively easy. However, if targets or detections are densely distributed, assignments become ambiguous because assigning a target to a detection or another nearby detection rarely makes any differences on the cost.

Probability of detection ( P d ) of the sensor — P d describes the probability that a target is detected by the sensor if the target is within the field of view of the sensor. If the P d of a sensor is small, then the true target may not give rise to any detection during a sensor scan. As a result, the track represented by the true target may steal detections from other tracks.

Sensor resolution — Sensor resolution determines the sensor’s ability to distinguish the detections from two targets. If the sensor resolution is low, then two targets in proximity may only give rise to one detection. This violates the common assumption that each detection can only be assigned to one track and results in unresolvable assignment conflicts between tracks.

Clutter or false alarm rate of the sensor — False alarms introduce additional possible assignments and therefore increase the complexity of data assignment.

The complexity of the assignment task can determine which assignment methods to apply. In Sensor Fusion and Tracking Toolbox™ toolbox, three 2-D assignment approaches are employed corresponding to three different trackers:

trackerGNN — adopts a global nearest data assignment approach

trackerJPDA — adopts a joint probability data association approach

trackerTOMHT — adopts a tracker-oriented multiple hypothesis tracking approach

Note that each tracker processes the data from sensors sequentially, meaning that each tracker only deals with the assignment problem with the detections of one sensor at a time. Even with this treatment, there may still be too many assignment pairs. To reduce the number of track and detection pairs considered for assignment, the gating technique is frequently used.

Gating is a screening mechanism to determine which observations are valid candidates to update existing tracks and eliminate unlikely detection-to-track pairs using the distribution information of the predicted tracks. To establish the validation gate for a track at the current scan, the estimated track for the current step is predicted from the previous step.

For example, a tracker confirms a track at time t k and receives several detections at time t k +1 . To form a validation gate at time t k +1 , the tracker first needs to obtain the predicted measurement as:

y ^ k + 1 = h ( x ^ k + 1 | k )

where x ^ k + 1 | k is the track estimate predicted from time t k and h ( x ^ k + 1 | k ) is the measurement model that outputs the expected measurement given the track state. The observation residual vector is

y ˜ = y k + 1 − y ^ k + 1

where y k +1 is the actual measurement. To establish the boundary of the gate, the detection residual covariance S is used to form an ellipsoidal validation gate. The ellipsoidal gate that establishes a spatial ellipsoidal region in the measurement space is defined in Mahalanobis distance as:

d 2 ( y k + 1 ) = y ˜ T S − 1 y ˜ ≤ G

where G is the gating threshold which you can specify based on the assignment requirement. Increasing the threshold can incorporate more detections into the gate.

After the assignment gate is established for each track, the gating status of each detection y i ( i = 1,…, n ) can be determined by comparing its Mahalanobis distance d 2 ( y i ) with the gating threshold G . If d 2 ( y i ) < G , then detection y i is inside the gate of the track and will be considered for association. Otherwise, the possibility of the detection associated with the track is removed. In Figure 1, T 1 represents a predicted track estimate, and O 1 – O 6 are six detections. Based on the gating result, O 1 , O 2 , and O 3 are within the validation gate in the figure.

Global Nearest Neighbor (GNN) Method

The GNN method is a single hypothesis assignment method. For each new data set, the goal is to assign the global nearest observations to existing tracks and to create new track hypotheses for unassigned detections.

The GNN assignment problem can be easily solved if there are no conflicts of association between tracks. The tracker only needs to assign a track to its nearest neighbor. However, conflict situations (see Figure 2) occur when there is more than one observation within a track’s validation gate or an observation is in the gates of more than one track. To resolve these conflicts, the tracker must evaluate a cost matrix.

The elements of a cost matrix for the GNN method includes the distance from tracks to detections and other factors you might want to consider. For example, one approach is to define a generalized statistical distance between observation j to track i as:

C i j = d i j + ln ( | S i j | )

where d ij is the Mahalanobis distance and ln(| S ij |), the logarithm of the determinant of the residual covariance matrix, is used to penalize tracks with greater prediction uncertainty.

For the assignment problem given in Figure 2, the following table shows a hypothetical cost matrix. The nonallowed assignments, which failed the gating test, are denoted by X. (In practice, the costs of nonallowed assignments can be denoted by large values, such as 1000.)

For this problem, the highlighted optimal solution can be found by enumeration. Detection O 3 is unassigned, so the tracker will use it to create a new tentative track. For more complicated GNN assignment problems, more accurate formulations and more efficient algorithms to obtain the optimal or suboptimal solution are required.

A general 2-D assignment problem can be formed as following. Given the cost matrix element C ij , find an assignment Z = { z ij } that minimizes

J = ∑ i = 0 n ∑ j = 0 m C i j z i j

subject to two constraints:

∑ i = 0 m z i j = 1 , ∀ j ∑ j = 0 n z i j = 1 , ∀ i

If track i is assigned to observation j , then z ij = 1. Otherwise, z ij = 0. z i 0 = 1 represents the hypothesis that track i is not assigned to any detection. Similarly, z 0 j = 1 represents the hypothesis that observation j is not assigned to any track. The first constraint means each detection can be assigned to no more than one track. The second constraint means each track can be assigned to no more than one detection.

Sensor Fusion and Tracking Toolbox provides multiple functions to solve 2-D GNN assignment problems:

assignmunkres – Uses the Munkres algorithm, which guarantees an optimal solution but may require more calculation operations.

assignauction – Uses the auction algorithm, which requires fewer operations but can possibly converge on an optimal or suboptimal solution.

assignjv – Uses the Jonker-Volgenant algorithm, which also converges on an optimal or suboptimal solution but usually with a faster converging speed.

In trackerGNN , you can select the assignment algorithm by specifying the Assignment property.

K Best Solutions to the 2-D Assignment Problem

Because of the uncertainty nature of assignment problems, only obtaining a solution (optimal or suboptimal) may not be sufficient. To account for multiple hypotheses about the assignment between tracks and detections, multiple suboptimal solutions are required. These suboptimal solutions are called K best solutions to the assignment problem.

The K best solutions are usually obtained by varying the solution obtained by any of the previously mentioned assignment functions. Then, at the next step, the K best solution algorithm removes one track-to-detection pair in the original solution and finds the next best solution. For example, for this cost matrix:

[ 10 5 8 9 7 × 20 × × × 21 1 5 × 17 × × × × 1 6 22 ]

each row represents the cost associated with a track, and each column represents the cost associated with a detection. As highlighted, the optimal solution is (7,15,16, 9) with a cost of 47. In the next step, remove the first pair (corresponding to 7), and the next best solution is (10,15, 20, 22) with a cost of 67. After that, remove the second pair (corresponding to 15), and the next best solution is (7, 5,16, 9) with a cost of 51. After a few steps, the five best solutions are:

See the Find Five Best Solutions Using Assignkbest example, which uses the assignkbest function to find the K best solutions.

Joint Probability Data Association (JPDA) Method

While the GNN method makes a rigid assignment of a detection to a track, the JPDA method applies a soft assignment so that detections within the validation gate of a track can all make weighted contributions to the track based on their probability of association.

For example, for the gating results shown in Figure 1, a JPDA tracker calculates the possibility of association between track T 1 and observations O 1 , O 2 , and O 3 . Assume the association probability of these three observations are p 11 , p 12 , and p 13 , and their residuals relative to track T 1 are y ˜ 11 , y ˜ 12 , and y ˜ 13 , respectively. Then the weighted sum of the residuals associated with track T 1 is:

y ˜ 1 = ∑ j = 1 3 p 1 j y ˜ 1 j

In the tracker, the weighted residual is used to update track T 1 in the correction step of the tracking filter. In the filter, the probability of unassignment, p 10 , is also required to update track T 1 . For more details, see JPDA Correction Algorithm for Discrete Extended Kalman Filter .

The JPDA method requires one more step when there are conflicts between assignments in different tracks. For example, in the following figure, track T 2 conflicts with T 1 on the assignment of observation O 3 . Therefore, to calculate the association probability p 13 , the joint probability that T 2 is not assigned to O 3 (that is T 2 is assigned to O 6 or unassigned) must be accounted for.

Track-Oriented Multiple Hypothesis Tracking (TOMHT) Method

Unlike the JPDA method, which combines all detections within the validation gate using a weighted sum, the TOMHT method generates multiple hypotheses or branches of the tracks based on the detections within the gate and propagates high-likelihood branches between scan steps. After propagation, these hypotheses can be tested and pruned based on the new set of detections.

For example, for the gating scenario shown in Figure 1, a TOMHT tracker considers the following four hypotheses:

Assign no detection to T 1 resulting in hypothesis T 10

Assign O 1 to T 1 resulting in hypothesis T 11

Assign O 2 to T 1 resulting in hypothesis T 12

Assign O 3 to T 1 resulting in hypothesis T 13

Given the assignment threshold, the tracker will calculate the possibility of each hypothesis and discard hypotheses with probability lower than the threshold. Hypothetically, if only p 10 and p 11 are larger than the threshold, then only T 10 and T 11 are propagated to the next step for detection update.

S-D Assignment in Multiple Target Tracking

In an S-D assignment problem, the dimension of assignment S is larger than 2. Note that all three trackers ( trackerGNN , trackerJPDA , and trackerTOMHT ) process detections from each sensor sequentially, which results in a 2-D assignment problem. However, some applications require a tracker that processes simultaneous observations from multiple sensor scans all at once, which requires solving an S-D assignment problem. Meanwhile, the S-D assignment is widely used in tracking applications such as static data fusion, which preprocesses the detection data before fed to a tracker.

An S-D assignment problem for static data fusion has S scans of a surveillance region from multiple sensors simultaneously, and each scan consists of multiple detections. The detection sources can be real targets or false alarms. The object is to detect an unknown number of targets and estimate their states. For example, as shown in the Figure 4, three sensor scans produce six detections. The detections in the same color belong to the same scan. Since each scan generates two detections, there are probably two targets in the region of surveillance. To choose between different assignment or association possibilities, evaluate the cost matrix.

The calculation of the cost can depend on many factors, such as the distance between detections and the covariance distribution of each detection. To illustrate the basic concept, the assignment costs for a few hypotheses are hypothetically given in the table [1] .

In the table, 0 denotes a track is associated with no detection in that scan. Assume the hypotheses not shown in the table are truncated by gating or neglected because of high costs. To concisely represent each track, use c ijk to represent the cost for association of observation i in scan 1, j in scan 2, and k in scan 3. For example, for the assignment hypothesis 1, c 011 = -10.2. Several track hypotheses conflict with other in the table. For instance, the two most likely assignments, c 111 and c 121 are incompatible because they share the same observation in scans 1 and 3.

The goal of solving an S-D assignment problem is to find the most likely compatible assignment hypothesis accounting for all the detections. When S ≥ 3, however, the problem is known to scale with the number of tracks and detections at an exponential rate (NP-hard). The Lagrangian relaxation method is commonly used to obtain the optimal or sub-optimal solution for an S-D assignment problem efficiently.

Brief Introduce to the Lagrangian Relaxation Method for 3-D Assignment

Three scans of data have a number of M 1 , M 2 , and M 3 observations, respectively. Denote an observation of scan 1, 2, and 3 as i , j , and k , respectively. For example, i = 1, 2, …, M 1 . Use z ijk to represent the track formation hypothesis of O 1 i , O 2 j , and O 3 k . If the hypothesis is valid, then z ijk = 1; otherwise, z ijk = 0. As mentioned, c ijk is used to represent the cost of z ijk association. c ijk is 0 for false alarms and negative for possible associations. The S-D optimization problem can be formulated as:

J ( z ) = min i , j , k ∑ i = 0 M 1 ∑ j = 0 M 2 ∑ k = 0 M 3 c i j k z i j k

subject to three constraints:

∑ i = 0 M 1 ∑ j = 0 M 2 z i j k = 1 , ∀ k = 1 , 2 , … , M 3 ∑ i = 0 M 1 ∑ k = 0 M 3 z i j k = 1 , ∀ j = 1 , 2 , … , M 2 ∑ j = 0 M 2 ∑ k = 0 M 3 z i j k = 1 , ∀ i = 1 , 2 , … , M 1

The optimization function chooses associations to minimize the total cost. The three constraints ensure that each detection is accounted for (either included in an assignment or treated as false alarm).

The Lagrangian relaxation method approaches this 3-D assignment problem by relaxing the first constraint using Lagrange multipliers. Define a new function L ( λ ) :

L ( λ ) = ∑ k = 0 M 3 λ k [ ∑ i = 0 M 1 ∑ j = 0 M 2 z i j k − 1 ]

where λ k , k = 1, 2, …, M 3 are Lagrange multipliers. Subtract L from the original object function J ( z ) to get a new object function, and the first constraint in k is relaxed. Therefore, the 3-D assignment problem reduces to a 2-D assignment problem, which can be solved by any of the 2-D assignment method. For more details, see [1] .

The Lagrangian relaxation method allows the first constraint to be mildly violated, and therefore can only guarantee a suboptimal solution. For most applications, however, this is sufficient. To specify the solution accuracy, the method uses the solution gap, which defines the difference between the current solution and the potentially optimistic solution. The gap is nonnegative, and a smaller solution gap corresponds to a solution closer to the optimal solution.

Sensor Fusion and Tracking Toolbox provides assignsd to solve for S-D assignment using the Lagrangian relaxation method. Similar to the K best 2-D assignment solver assignkbest , the toolbox also provides a K best S-D assignment solver, assignkbestsd , which is used to provide multiple suboptimal solutions for an S-D assignment problem.

See Tracking Using Distributed Synchronous Passive Sensors for the application of S-D assignment in static detection fusion.

assignTOMHT | assignauction | assignjv | assignkbest | assignkbestsd | assignmunkres | assignsd | trackerGNN | trackerJPDA | trackerTOMHT

[1] Blackman, S., and R. Popoli. Design and Analysis of Modern Tracking Systems. Artech House Radar Library, Boston, 1999.

[2] Musicki, D., and R. Evans. "Joint Integrated Probabilistic Data Association: JIPDA." IEEE Transactions on Aerospace and Electronic Systems. Vol. 40, Number 3, 2004, pp 1093 –1099.

MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

• Switzerland (English)
• Switzerland (Deutsch)
• Switzerland (Français)
• 中国 (English)

You can also select a web site from the following list:

How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

• América Latina (Español)
• Canada (English)
• United States (English)
• Belgium (English)
• Denmark (English)
• Deutschland (Deutsch)
• España (Español)
• Finland (English)
• France (Français)
• Ireland (English)
• Italia (Italiano)
• Luxembourg (English)
• Netherlands (English)
• Norway (English)
• Österreich (Deutsch)
• Portugal (English)
• Sweden (English)
• United Kingdom (English)

Asia Pacific

• Australia (English)
• India (English)
• New Zealand (English)

Contact your local office

Navigation Menu

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 You must be signed in to change notification settings

Jonker-Volgenant / LAPJV algorithm for the linear assignment problem, in C language

yongyanghz/LAPJV-algorithm-c

Folders and files.

Repository files navigation

Lapjv-algorithm-c.

version 1.0 - 4 September 1996 author: Roy Jonker @ MagicLogic Optimization Inc. e-mail: [email protected]

Code for Linear Assignment Problem, according to

"A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems," Computing 38, 325-340, 1987

R. Jonker and A. Volgenant, University of Amsterdam.

CHANGED 2016-05-13 by Yong Yang( [email protected] ) in column reduction part according to matlab version of LAPJV algorithm(Copyright (c) 2010, Yi Cao All rights reserved)--

Additional information:

The original code is download from python wrapper for C++ code on github https://github.com/hrldcpr/pyLAPJV . LAPJV comes from the paper:

R. Jonker and A. Volgenant, "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems," Computing, vol. 38, pp. 325-340, 1987.

According to that paper, it is notably faster than the Hungarian algorithm (a.k.a. Munkres' algorithm) and several other linear assignment algorithms.

The C++ source comes from: http://www.magiclogic.com/assignment.html

If any of those links are broken then try them in the Wayback Machine! For example the original C++ source zip can be obtained at: https://web.archive.org/web/*/http://www.magiclogic.com/assignment/lap_cpp.zip

The matlab code of lap JV algorithm comes from: https://www.mathworks.com/matlabcentral/fileexchange/26836-lapjv-jonker-volgenant-algorithm-for-linear-assignment-problem-v3-0 :

Usage Example

Contributors 2.

• CMake 29.2%