A strongly polynomial simplex method for the linear fractional assignment problem

DOI10.1016/J.ORL.2007.12.001zbMATH Open1155.90456OpenAlexW2003327511MaRDI QIDQ1003483FDOQ1003483

Authors: Santosh N. Kabadi, Abraham P. Punnen 

Publication date: 4 March 2009

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2007.12.001

Recommendations

• A competitive (dual) simplex method for the assignment problem
• A simplex-based labelling algorithm for the linear fractional assignment problem
• A sequential dual simplex algorithm for the linear assignment problem
• A genuinely polynomial primal simplex algorithm for the assignment problem
• An algorithm for fractional assignment problems

zbMATH Keywords

assignment problemcomplexitysimplex methodlinear fractional programmingstrongly polynomial algorithms

Mathematics Subject Classification ID

Linear programming (90C05) Fractional programming (90C32) Extreme-point and pivoting methods (90C49)

Cites Work

• Network flows. Theory, algorithms, and applications.
• On Nonlinear Fractional Programming
• Title not available (Why is that?)
• A polynomial time primal network simplex algorithm for minimum cost flows
• Title not available (Why is that?)
• An algorithm for fractional assignment problems
• Combinatorial Optimization with Rational Objective Functions
• Parametric flows, weighted means of cuts, and fractional combinatorial optimization
• Linear-fractional programming. Theory, methods, applications and software.
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• Theoretical Properties of the Network Simplex Method
• Technical Note—A Polynomial Simplex Method for the Assignment Problem
• The Scaling Network Simplex Algorithm
• A genuinely polynomial primal simplex algorithm for the assignment problem
• The alternating basis algorithm for assignment problems
• A network simplex algorithm with O(\(n\)) consecutive degenerate pivots
• Hyperbolic 0-1 programming and query optimization in information retrieval
• On the simplex algorithm for networks and generalized networks
• (0, 1) hyperbolic programming problems
• Upper bound problem in linear fractional functionals programming
• SOME ASPECTS OF LINEAR FRACTIONAL FUNCTIONALS PROGRAMMING
• A new pivot selection rule for the network simplex algorithm
• Title not available (Why is that?)
• Anti-stalling Pivot Rule for Linear Programs with Totally Unimodular Coefficient Matrix

Cited In (3)

• The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption
• A simplex-based labelling algorithm for the linear fractional assignment problem
• Determining type II sensitivity ranges of the fractional assignment problem

This page was built for publication: A strongly polynomial simplex method for the linear fractional assignment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1003483)