Signature Methods for the Assignment Problem

M. L. Balinski
M. L. Balinski
C.N.R.S., Laboratoire d'Econométrie de I'Ecole Polytechnique, Paris
Search for more papers by this author

C.N.R.S., Laboratoire d'Econométrie de I'Ecole Polytechnique, Paris

Published Online:1 Jun 1985https://doi.org/10.1287/opre.33.3.527

Abstract

The “signature” of a dual feasible basis of the assignment problem is an n-vector whose ith component is the number of nonbasic activities of type (i, j). This paper uses signatures to describe a method for finding optimal assignments that terminates in at most (n − 1)(n − 2)/2 pivot steps and takes at most O(n³) work.

Cited by
- Exact algorithm for the integrated berth and quay crane allocation problem considering tidal impact
  11 August 2025 | Transportmetrica A: Transport Science, Vol. 53
- Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
  3 July 2024 | Journal of Combinatorial Optimization, Vol. 47, No. 5
- On Cone Partitions for the Min-Cut and Max-Cut Problems with Non-negative Edges
  21 September 2023
- Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-Regular Multigraph
  19 February 2023 | Automatic Control and Computer Sciences, Vol. 56, No. 7
- A review of the use of optimal transport distances for high resolution seismic imaging based on the full waveform
  27 September 2022 | MathematicS In Action, Vol. 11, No. 1
- A dual approach to multi-dimensional assignment problems
  18 January 2021 | Journal of Global Optimization, Vol. 81, No. 3
- Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search
  30 September 2020 | Journal of Combinatorial Optimization, Vol. 42, No. 2
- Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph
  24 March 2021 | Modeling and Analysis of Information Systems, Vol. 28, No. 1
- Multi-UAV Path Planning in a Spreading Wildfire
  4 January 2021
- An Iterative ILP Approach for Constructing a Hamiltonian Decomposition of a Regular Multigraph
  21 September 2021
- A Shift-Daily Planning of Freight Trains Composition and Transit Using Maximum Network Flow Approach
- Decentralizing Coordination in Open Vehicle Fleets for Scalable and Dynamic Task Allocation
  Complexity, Vol. 2020
- Adaptive Task Allocation for Heterogeneous Multi-Robot Teams with Evolving and Unknown Robot Capabilities
- A novel convex dual approach to three-dimensional assignment problem: theoretical analysis
  28 May 2019 | Computational Optimization and Applications, Vol. 74, No. 2
- A Branch-and-Price Algorithm for the Integrated Berth Allocation and Quay Crane Assignment Problem
  Fanrui Xie,
  Tao Wu,
  Canrong Zhang
  28 August 2019 | Transportation Science, Vol. 53, No. 5
- A graph space optimal transport distance as a generalization of Lp distances: application to a seismic imaging inverse problem
  3 July 2019 | Inverse Problems, Vol. 35, No. 8
- Closed-loop task allocation in robot swarms using inter-robot encounters
  11 June 2019 | Swarm Intelligence, Vol. 13, No. 2
- On Vertex Adjacencies in the Polytope of Pyramidal Tours with Step-Backs
  12 June 2019
- Simulated Annealing Approach to Verify Vertex Adjacencies in the Traveling Salesperson Polytope
  12 June 2019
- Critical objective function values in linear sum assignment problems
  16 December 2017 | Journal of Combinatorial Optimization, Vol. 35, No. 3
- Cloud Robotic Platform on Basis of Fog Computing Approach
  19 August 2018
- A Distributed Version of the Hungarian Method for Multirobot Assignment
  IEEE Transactions on Robotics, Vol. 33, No. 4
- Efficient data replica placement for sensor clouds
  1 November 2016 | IET Communications, Vol. 10, No. 16
- Efficient index reduction algorithm for large scale systems of differential algebraic equations
  Applied Mathematics and Computation, Vol. 277
- Exterior point simplex-type algorithms for linear and network optimization problems
  1 January 2015 | Annals of Operations Research, Vol. 229, No. 1
- Multiple objective community service resources matching with priority
- Solving the Assignment Problem with the Improved Dual Neural Network
- A distributed joint-learning and auction algorithm for target assignment
- Continuous spatial assignment of moving users
  6 June 2009 | The VLDB Journal, Vol. 19, No. 2
- Optimal matching between spatial datasets under capacity constraints
  3 May 2010 | ACM Transactions on Database Systems, Vol. 35, No. 2
- Perfectly matchable subgraph problem on a bipartite graph
  8 February 2010 | RAIRO - Operations Research, Vol. 44, No. 1
- Bibliography
  15 August 2011
- Assignment problems with changeover cost
  27 August 2009 | Annals of Operations Research, Vol. 172, No. 1
- Worst case examples of an exterior point algorithm for the assignment problem
  Discrete Optimization, Vol. 5, No. 3
- Advances in Assignment Problem and comparison of algorithms
- Perfect matchings and extended polymatroid
  25 June 2008 | Cybernetics and Systems Analysis, Vol. 44, No. 3
- A real-time multitarget tracking system with robust multichannel CNN-UM algorithms
  IEEE Transactions on Circuits and Systems I: Regular Papers, Vol. 52, No. 7
- Effective Approaches for Low Temperature Polysilicon TFT LCD Post-Mapping Yield Control Problem
  IEEE Transactions on Automation Science and Engineering, Vol. 2, No. 2
- The Dynamic Assignment Problem
  Michael Z. Spivey,
  Warren B. Powell,
  1 November 2004 | Transportation Science, Vol. 38, No. 4
- An improved data assignment solution for ML-based relaxation approach for multitarget tracking problem
- Fusion of active phased array radars within a quick reaction time using multidimensional data association
- AN IMPROVED SOLUTION TO ML-BASED MULTITARGET MOTION TRACKING WITH BEARINGS-ONLY MEASUREMENTS
  International Journal of Computational Engineering Science, Vol. 03, No. 04
- A faster data assignment algorithm for maximum likelihood-based multitarget motion tracking with bearings-only measurements
  Mathematics and Computers in Simulation, Vol. 57, No. 1-2
- Polarity-free automatic classification of chromosomes
  Computational Statistics & Data Analysis, Vol. 35, No. 3
- m-best S-D assignment algorithm with application to multitarget tracking
  IEEE Transactions on Aerospace and Electronic Systems, Vol. 37, No. 1
- Algorithms and codes for dense assignment problems: the state of the art
  Discrete Applied Mathematics, Vol. 100, No. 1-2
- Linear Assignment Problems and Extensions
- Distributed‐ and shared‐memory parallelizationsof assignment‐based data association formultitarget tracking
  Annals of Operations Research, Vol. 90, No. 0
- Dynamically adaptable m-best 2-D assignment algorithm and multilevel parallelization
  IEEE Transactions on Aerospace and Electronic Systems, Vol. 35, No. 4
- An adaptive m-best SD assignment algorithm and parallelization for multitarget tracking
- A new algorithm for the assignment problem: An alternative to the Hungarian method
  Computers & Operations Research, Vol. 24, No. 11
- Outliers in statistical pattern recognition and an application to automatic chromosome classification
  Pattern Recognition Letters, Vol. 18, No. 6
- Parallel Algorithms for Network Problems
- Computational Complexity Results of Robust Discrete Optimization Problems
- Max-min matching problems with multiple assignments
  Journal of Optimization Theory and Applications, Vol. 91, No. 2
- A non improving simplex algorithm for transportation problems
  29 March 2011 | RAIRO - Operations Research, Vol. 30, No. 1
- The singly constrained assignment problem: An AP basis algorithm
  Computational Optimization and Applications, Vol. 4, No. 4
- Automatic context-sensitive karyotyping of human chromosomes based on elliptically symmetric statistical distributions
  Pattern Recognition, Vol. 28, No. 6
- A strongly polynomial algorithm for the transportation problem
  Mathematical Programming, Vol. 68, No. 1-3
- Adjacency on combinatorial polyhedra
  Discrete Applied Mathematics, Vol. 56, No. 2-3
- Order-preserving assignments
  Naval Research Logistics, Vol. 41, No. 3
- On Very Large Scale Assignment Problems
- The Diameter of Polytopes and Related Applications
- On the Complexity of the Simplex Method
- A genuinely polynomial primal simplex algorithm for the assignment problem
  Discrete Applied Mathematics, Vol. 45, No. 2
- Signature classes of transportation polytopes
  Mathematical Programming, Vol. 60, No. 1-3
- Polynomial dual network simplex algorithms
  Mathematical Programming, Vol. 60, No. 1-3
- Polynomial-time primal simplex algorithms for the minimum cost network flow problem
  Algorithmica, Vol. 8, No. 1-6
- Personnel placement in a fuzzy environment
  Computers & Operations Research, Vol. 19, No. 2
- A new relaxation algorithm and passive sensor data association
  IEEE Transactions on Automatic Control, Vol. 37, No. 2
- Parallel synchronous and asynchronous implementations of the auction algorithm
  Parallel Computing, Vol. 17, No. 6-7
- An infeasible (exterior point) simplex algorithm for assignment problems
  Mathematical Programming, Vol. 51, No. 1-3
- An efficient transportation algorithm for automatic chromosome karyotyping
  Pattern Recognition Letters, Vol. 12, No. 2
- A relaxation column signature method for assignment problems
  European Journal of Operational Research, Vol. 50, No. 2
- A dual feasible forest algorithm for the linear assignment problem
  29 March 2011 | RAIRO - Operations Research, Vol. 25, No. 4
- Sparse dual transportation polyhedra: Extreme points and signatures
  Operations Research Letters, Vol. 9, No. 2
- Gel Electrophoresis and Graph Matching
- Scheduling unit processing time jobs on a single machine with multiple criteria
  Computers & Operations Research, Vol. 17, No. 1
- Algorithms for assignment problems on an array processor
  Parallel Computing, Vol. 11, No. 2
- Chapter IV Network flows
- Comparison of assignment algorithms with applications to the passive sensor data association problem
- The auction algorithm: A distributed relaxation method for the assignment problem
  Annals of Operations Research, Vol. 14, No. 1
- Algorithms and codes for the assignment problem
  Annals of Operations Research, Vol. 13, No. 1
- A sequential dual simplex algorithm for the linear assignment problem
  Operations Research Letters, Vol. 7, No. 3
- MULTIDIMENSIONAL ASSIGNMENT PROBLEMS
  7 June 2007 | Decision Sciences, Vol. 19, No. 2
- A non-dual signature method for the assignment problem and a generalization of the dual simplex method for the transportation problem
  29 March 2011 | RAIRO - Operations Research, Vol. 22, No. 3
- A shortest augmenting path algorithm for dense and sparse linear assignment problems
  Computing, Vol. 38, No. 4
- Transportation problems which can be solved by the use of hirsch-paths for the dual problems
  Mathematical Programming, Vol. 37, No. 2
- An efficient labeling technique for solving sparse assignment problems
  Computing, Vol. 36, No. 4
- Improving the Hungarian assignment algorithm
  Operations Research Letters, Vol. 5, No. 4
- Efficient dual simplex algorithms for the assignment problem
  Mathematical Programming, Vol. 34, No. 3
- A competitive (dual) simplex method for the assignment problem
  Mathematical Programming, Vol. 34, No. 2

Volume 33, Issue 3

May-June 1985

Pages 469-703

Article Information

Metrics

Information

Published Online:June 01, 1985

Cite as

M. L. Balinski, (1985) Signature Methods for the Assignment Problem. Operations Research 33(3):527-536.

https://doi.org/10.1287/opre.33.3.527

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Signature Methods for the Assignment Problem

Abstract

Volume 33, Issue 3

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News