An algorithm for fractional assignment problems

DOI10.1016/0166-218X(93)00094-GzbMath0820.90121MaRDI QIDQ1842662

Maiko Shigeno, Tomomi Matsui, Yasufumi Saruwatari

Publication date: 14 September 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

bipartite graph; polynomial-time algorithm; fractional assignment; approximate binary search method

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C31: Sensitivity, stability, parametric optimization

90C32: Fractional programming

90C27: Combinatorial optimization

Related Items

A fifth bibliography of fractional programming^*, Assignment problems: a golden anniversary survey, A strongly polynomial simplex method for the linear fractional assignment problem, A labeling algorithm for the fuzzy assignment problem.

Cites Work

• Unnamed Item
• Unnamed Item
• A strongly polynomial minimum cost circulation algorithm
• A linear time randomizing algorithm for searching ranked functions
• New scaling algorithms for the assignment and minimum mean cycle problems
• The auction algorithm: A distributed relaxation method for the assignment problem
• Combinatorial Optimization with Rational Objective Functions
• Minimal ratio spanning trees
• Fractional knapsack problems
• Fibonacci heaps and their uses in improved network optimization algorithms
• On Some Properties of Programming Problems in Parametric form Pertaining to Fractional Programming
• On Nonlinear Fractional Programming
• (0, 1) hyperbolic programming problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Fractional programming