On the length of simplex paths: The assignment case

DOI10.1007/BF02591931MaRDI QIDQ3698637zbMATH OpenOpenAlexFDO

Authors Snjólfur Ólafsson, P. O. Lindberg

Publication date 1984

Published in Mathematical Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02591931

zbMATH Keywords

polynomial growthoptimal assignment problemnumber of pivotslength of simplex paths

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On Shortest Paths in Polyhedral Spaces
• scientific article; zbMATH DE number 3876620
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• On the length of monotone paths in polyhedra
• On the convexity of paths of length two in undirected graphs
• On the complexity of vertex-disjoint length-restricted path problems
• On approximating the longest path in a graph
• Simple paths with exact and forbidden lengths
• On the complexity of finding paths in a two-dimensional domain I: Shortest paths

Cites work

• scientific article; zbMATH DE number 5968600 (Why is no real title available?)
• scientific article; zbMATH DE number 3648423 (Why is no real title available?)
• scientific article; zbMATH DE number 3126895 (Why is no real title available?)
• scientific article; zbMATH DE number 3726093 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 3630477 (Why is no real title available?)
• A bad network problem for the simplex method and other minimum cost flow algorithms
• How to Solve Linear Inequalities
• Implementation and computational comparisons of primal, dual and primal-dual computer codes for minimum cost network flow problems
• On the length of simplex paths: The assignment case
• Some experiments with the pathological linear programs of N. Zadeh
• Some results in probabilistic geometry
• The Average number of pivot steps required by the Simplex-Method is polynomial
• The Hirsch Conjecture for Dual Transportation Polyhedra
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• The simplex algorithm with the pivot rule of maximizing criterion improvement
• ZufÄllige konvexe Polygone in einem Ringgebiet

Cited in

(5)

• The monotonic diameter of the perfect matching and shortest path polytopes
• On the length of simplex paths: The assignment case
• On a negative-equivalency theorem in associative optimal path problems
• Affirmative action algorithms
• On the average length of lexicographic paths

This page was built for publication: On the length of simplex paths: The assignment case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3698637)