A strongly polynomial simplex method for the linear fractional assignment problem

DOI10.1016/j.orl.2007.12.001zbMath1155.90456OpenAlexW2003327511MaRDI 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

complexitylinear fractional programmingsimplex methodassignment problemstrongly polynomial algorithms

Mathematics Subject Classification ID

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

Related Items (3)

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 ⋮ A simplex-based labelling algorithm for the linear fractional assignment problem

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

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