A strongly polynomial algorithm for line search in submodular polyhedra

DOI10.1016/j.disopt.2007.09.002zbMath1157.90513OpenAlexW2073209873MaRDI QIDQ2427694

Kiyohito Nagano

Publication date: 14 May 2008

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2007.09.002

zbMATH Keywords

submodular functionnetwork flowexchange capacity

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Combinatorial optimization (90C27)

Related Items

Zonotopes and the LP-Newton method, Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, Minimizing submodular functions on diamonds via generalized fractional matroid matchings, Equivalence of convex minimization problems over base polytopes, Submodular function minimization, Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A theorem on flows in networks
• Submodular functions and optimization
• A note on Schrijver's submodular function minimization algorithm.
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A fully combinatorial algorithm for submodular function minimization.
• A Submodular Optimization Problem with Side Constraints
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• The Partial Order of a Polymatroid Extreme Point
• Minimum cuts, modular functions, and matroid polyhedra
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Combinatorial Optimization with Rational Objective Functions
• Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
• Optimal flows in networks with multiple sources and sinks
• Maximal Closure of a Graph and Applications to Combinatorial Problems
• Discrete Convex Analysis
• A Faster Scaling Algorithm for Minimizing Submodular Functions
• A strongly polynomial time algorithm for a constrained submodular optimization problem