A strongly polynomial simplex method for the linear fractional assignment problem

DOI10.1016/j.orl.2007.12.001zbMath1155.90456MaRDI QIDQ1003483

Abraham P. Punnen, Santosh N. Kabadi

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

zbMATH Keywords

complexity; linear fractional programming; simplex method; assignment problem; strongly polynomial algorithms

Mathematics Subject Classification ID

90C32: Fractional programming

90C05: Linear programming

90C49: Extreme-point and pivoting methods

Related Items

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

Cites Work

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