A strongly polynomial time algorithm for a constrained submodular optimization problem

DOI10.1016/S0166-218X(00)00285-7zbMath1086.90049MaRDI QIDQ5951962

David B. Hartvigsen

Publication date: 2001

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

zbMATH Keywords

Base polyhedronMax flowMin cost spanning treeSubmodular function

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (1)

A strongly polynomial algorithm for line search in submodular polyhedra

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Duality for balanced submodular flows
• On submodular function minimization
• Submodular functions and optimization
• Minimizing symmetric submodular functions
• Towards equitable distribution via proportional equity constraints
• A Submodular Optimization Problem with Side Constraints
• Maximal Flow Through a Network
• Submodular systems and related topics
• Optimal sharing
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• The Sharing Problem

This page was built for publication: A strongly polynomial time algorithm for a constrained submodular optimization problem