Free Access

Technical Note—An Improved Algorithm for the Bottleneck Assignment Problem

Robert S. Garfinkel
Robert S. Garfinkel
The University of Rochester, Rochester, New York
Search for more papers by this author

Robert S. Garfinkel

The University of Rochester, Rochester, New York

Search for more papers by this author

Published Online:1 Dec 1971https://doi.org/10.1287/opre.19.7.1747

Cited by
- LEAD: Towards Learning-Based Equity-Aware Decarbonization in Ridesharing Platforms
  23 June 2025
- A distributed algorithm for the multi-robot minimum time task allocation problem
  6 December 2024 | Industrial Robot: the international journal of robotics research and application, Vol. 52, No. 3
- An efficient solution approach to capacitated three-level hierarchical time minimization transportation problem
  Expert Systems with Applications, Vol. 249
- A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem
  IEEE Transactions on Automatic Control, Vol. 69, No. 2
- Robust Bidirectional Poly-Matching
  IEEE Transactions on Knowledge and Data Engineering, Vol. 35, No. 10
- Speed of Performance of a Group of Controlled Objects
  11 November 2023 | Journal of Computer and Systems Sciences International, Vol. 62, No. 5
- Speed of Performance of a Group of Controlled Objects
  1 September 2023 | Известия Российской академии наук. Теория и системы управления, No. 5
- Mathematical Formulation of the Component Assignment Problem in PCB Assembly Lines
- Task preference-based bottleneck assignment problem
  2 September 2022 | Computational and Applied Mathematics, Vol. 41, No. 7
- A greedy and distributable approach to the Lexicographic Bottleneck Assignment Problem with conditions on exactness
  Automatica, Vol. 140
- Time-Correlated Sparsification for Efficient Over-the-Air Model Aggregation in Wireless Federated Learning
- Time–cost trade-off in a multi-choice assignment problem
  25 February 2021 | Engineering Optimization, Vol. 54, No. 4
- An alternate approach to solve two-level priority based assignment problem
  10 January 2022 | Computational Optimization and Applications, Vol. 81, No. 2
- A MIP-Based Heuristic for Pickup and Delivery on Rectilinear Layout
  30 July 2022
- Swap dynamics in single-peaked housing markets
  19 May 2021 | Autonomous Agents and Multi-Agent Systems, Vol. 35, No. 2
- Time-cost trade-off analysis of a priority based assignment problem
  4 November 2020 | OPSEARCH, Vol. 58, No. 2
- Chance Constrained Simultaneous Path Planning and Task Assignment with Bottleneck Objective
- Optimal Matching for Observational Studies That Integrate Quantitative and Qualitative Research
  17 June 2021 | Statistics and Public Policy, Vol. 8, No. 1
- Comment: Matching Methods for Observational Studies Derived from Large Administrative Databases
  Statistical Science, Vol. 35, No. 3
- Rejoinder: Matching Methods for Observational Studies Derived from Large Administrative Databases
  Statistical Science, Vol. 35, No. 3
- A priority based unbalanced time minimization assignment problem
  6 August 2019 | OPSEARCH, Vol. 57, No. 1
- Various Practical Issues in Matching
  14 July 2020
- Line-Up Elections: Parallel Voting with Shared Candidate Pool
  8 September 2020
- Exploiting Structure in the Bottleneck Assignment Problem
  IFAC-PapersOnLine, Vol. 53, No. 2
- Spatial Two-Sided Online Bottleneck Matching With Deadlines
  IEEE Access, Vol. 8
- Distributed Algorithm for Solving the Bottleneck Assignment Problem
- Uncertain random simulation algorithm with application to bottleneck assignment problem
  27 November 2018 | Soft Computing, Vol. 23, No. 21
- Multirobot Simultaneous Path Planning and Task Assignment on Graphs with Stochastic Costs
- An improved algorithm for two stage time minimization assignment problem
  22 June 2018 | Journal of Combinatorial Optimization, Vol. 37, No. 2
- The Fair OWA One-to-One Assignment Problem: NP-Hardness and Polynomial Time Special Cases
  30 March 2018 | Algorithmica, Vol. 81, No. 1
- Optimal Spectrum Sensor Assignment in Multi-channel Multi-user Cognitive Radio Networks
  28 December 2018 | Journal of Telecommunications and Information Technology, Vol. 4, No. 2018
- Imposing Minimax and Quantile Constraints on Optimal Matching in Observational Studies
  16 February 2017 | Journal of Computational and Graphical Statistics, Vol. 26, No. 1
- Serve or skip: the power of rejection in online bottleneck matching
  2 September 2015 | Journal of Combinatorial Optimization, Vol. 32, No. 4
- Bottleneck-aware arrangement over event-based social networks: the max-min approach
  8 December 2015 | World Wide Web, Vol. 19, No. 6
- A priority based assignment problem
  Applied Mathematical Modelling, Vol. 40, No. 17-18
- Optimal Solution for a Joint Power Allocation and Relay Assignment Problem
  IEEE Transactions on Vehicular Technology, Vol. 65, No. 8
- Exact solution approaches for bilevel assignment problems
  11 November 2015 | Computational Optimization and Applications, Vol. 64, No. 1
- An Linear Bottleneck Assignment Problem (LBAP) Algorithm Using the Improving Method of Solution for Linear Minsum Assignment Problem (LSAP)
  Journal of the Korea Society of Computer and Information, Vol. 21, No. 1
- Minimizing maximum weight of subsets of a maximum matching in a bipartite graph
  Discrete Applied Mathematics, Vol. 196
- On bottleneck-aware arrangement for event-based social networks
- Model for Assigning Project Members to Maximize Personality Balance
  1 May 2014 | Applied Mechanics and Materials, Vol. 556-562
- A turnpike approach to solving the linear bottleneck assignment problem
  20 December 2013 | The International Journal of Advanced Manufacturing Technology, Vol. 71, No. 5-8
- The Multiple Unmanned Air Vehicle Persistent Surveillance Problem: A Review
  2 January 2014 | Machines, Vol. 2, No. 1
- The Power of Rejection in Online Bottleneck Matching
  13 November 2014
- Multi-Robot Formation Shape Control Using Convex Optimization and Bottleneck Assignment
  Journal of Industrial and Intelligent Information, Vol. 2, No. 1
- Linear Bottleneck Assignment Problem Based on Reverse-delete Algorithm
  The Journal of the Institute of Webcasting, Internet and Telecommunication, Vol. 13, No. 6
- Assignment of project members considering capability and personality balance
  Kybernetes, Vol. 42, No. 7
- A Determinant Elimination Method for Bottleneck Assignment and Generalized Assignment Problems
  1 December 2012 | Applied Mechanics and Materials, Vol. 239-240
- References
  21 September 2012
- The dominance assignment problem
  Discrete Optimization, Vol. 9, No. 3
- Assignment problems with changeover cost
  27 August 2009 | Annals of Operations Research, Vol. 172, No. 1
- Bottleneck flows in unit capacity networks
  Information Processing Letters, Vol. 109, No. 6
- Two-stage time minimizing assignment problem
  Omega, Vol. 36, No. 5
- Persistent Surveillance Using Multiple Unmanned Air Vehicles
- General Bottleneck Assignment Problem and its Algorithm
- Bilevel time minimizing assignment problem
  Applied Mathematics and Computation, Vol. 183, No. 2
- An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
  Discrete Applied Mathematics, Vol. 154, No. 9
- Study on the method for 2-D fuzzy bottleneck assignment problem
- Selected topics on assignment problems
  Discrete Applied Mathematics, Vol. 123, No. 1-3
- An Oracle Strongly Polynomial Algorithm for Bottleneck Expansion Problems
  27 October 2010 | Optimization Methods and Software, Vol. 17, No. 1
- A class of bottleneck expansion problems
  Computers & Operations Research, Vol. 28, No. 6
- The stochastic bottleneck linear programming problem
  Top, Vol. 7, No. 1
- Linear Assignment Problems and Extensions
- Max-min matching problems with multiple assignments
  Journal of Optimization Theory and Applications, Vol. 91, No. 2
- A bilevel bottleneck programming problem
  European Journal of Operational Research, Vol. 86, No. 2
- On bilevel fractional programming
  Optimization, Vol. 35, No. 3
- The three-dimensional bottleneck assignment problem with capacity constraints
  European Journal of Operational Research, Vol. 73, No. 3
- An algorithm for the bottleneck generalized assignment problem
  Computers & Operations Research, Vol. 20, No. 4
- Bicriteria bottleneck linear programming problem
  Optimization, Vol. 28, No. 2
- Solving linear bottleneck assignment problems via strong spanning trees
  Operations Research Letters, Vol. 12, No. 3
- On the solution of a stochastic bottleneck assignment problem and its variations
  Naval Research Logistics, Vol. 39, No. 3
- An O (n2.5) Time Heuristic Algorithm for a Class of Large Weighted Edge Colouring Problems
- Algorithms for two bottleneck optimization problems
  Journal of Algorithms, Vol. 9, No. 3
- MULTIDIMENSIONAL ASSIGNMENT PROBLEMS
  7 June 2007 | Decision Sciences, Vol. 19, No. 2
- Bottleneck generalized assignment problems
  Engineering Costs and Production Economics, Vol. 14, No. 1
- Die Säulenordnungen
- The three dimensional bottleneck assignment problem and its variants
  29 August 2008 | Optimization, Vol. 16, No. 2
- A perfect matching algorithm for sparse bipartite graphs
  Discrete Applied Mathematics, Vol. 9, No. 3
- A study of the bottleneck single source transportation problem
  Computers & Operations Research, Vol. 11, No. 1
- On Some Decision Problems in the Network with Fuzzy Parameters
  IFAC Proceedings Volumes, Vol. 16, No. 13
- On the bottleneck linear programming problem
  European Journal of Operational Research, Vol. 9, No. 4
- Bibliography
- On two methods for solving the bottleneck matching problem
- Ranking assignments in order of increasing completion time
  27 June 2007 | Mathematische Operationsforschung und Statistik. Series Optimization, Vol. 11, No. 3
- Travelling Salesman and Assignment Problems: A Survey
- UNCONSTRAINED DISCRETE NONLINEAR PROGRAMMING
  Engineering Optimization, Vol. 4, No. 2
- OPTIMAL SELECTION OF MATCHED PAIRS FROM LARGE DATA BASES
  7 June 2007 | Decision Sciences, Vol. 10, No. 1
- An augmenting path method for solving Linear Bottleneck Assignment problems
  Computing, Vol. 19, No. 4
- The Bottleneck Traveling Salesman Problem
  1 July 1978 | Journal of the ACM, Vol. 25, No. 3
- The Concept of Market Components and the Spatial Organization of Periodic Markets
  1 November 1977 | Environment and Planning A: Economy and Space, Vol. 9, No. 11
- Bottleneck linear programming
  Mathematical Programming, Vol. 11, No. 1
- Application of optimization methods to the hematological support of patients with disseminated malignancies
  Mathematical Biosciences, Vol. 25, No. 1-2
- References††The first comprehensive references list is due to Balinski and Spielberg (1969). A later list appears in the work of Garfinkel and Nemhauser (1972b).
- Un algorithme pour le problème de partitionnement
  29 March 2011 | Revue française d'automatique, informatique, recherche opérationnelle. Recherche opérationnelle, Vol. 8, No. V1

Volume 19, Issue 7

November-December 1971

Pages 1553-1769

Article Information

Metrics

Information

Published Online:December 01, 1971

Cite as

Robert S. Garfinkel, (1971) Technical Note—An Improved Algorithm for the Bottleneck Assignment Problem. Operations Research 19(7):1747-1751.

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

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Technical Note—An Improved Algorithm for the Bottleneck Assignment Problem

Volume 19, Issue 7

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News