A strongly polynomial simplex method for the linear fractional assignment problem

DOI10.1016/J.ORL.2007.12.001MaRDI QIDQ1003483zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(3)

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