1980/08/01 by Robert E. Bixby, William H. Cunningham · 3 citations
Computer Science · Decision Sciences · Engineering · Mathematics · #Algorithm #Arithmetic #Binary number #Bounded function #Combinatorics #Computer science #Data Management and Algorithms #Discrete mathematics #Flow network #Linear programming #Mathematical optimization #Mathematics #Matroid #Multi-Criteria Decision Making #Optimization and Packing Problems #Row #Scaling #Variable (mathematics)
paper · doi:10.1287/moor.5.3.321
openalex publication_date 1980/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
We describe an algorithm which converts a linear program mincx ∣ Ax = b, x ≥ 0 to a network flow problem, using elementary row operations and nonzero variable-scaling, or shows that such a conversion is impossible. If A is in standard form, the computational effort required is bounded by O(rn), where r is the number of rows and n is the number of nonzero entries of A. A method for determining whether a “binary matroid” is “graphic” plays an important role in the algorithm.