Budget-constrained minimum cost flows

DOI10.1007/S10878-015-9865-YMaRDI QIDQ281825zbMATH OpenOpenAlexFDO

Authors Michael Holzhauser, Clemens Thielen, Sven O. Krumke

Publication date 11 May 2016

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-015-9865-y

zbMATH Keywords

algorithmscomplexityminimum cost flownetwork improvementNP-completeness

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• On the complexity and approximability of budget-constrained minimum cost flows
• A network simplex method for the budget-constrained minimum cost flow problem
• On budget-constrained flow improvement.
• Minimum cost flows with minimum quantities
• The budgeted minimum cost flow problem with unit upgrading cost

Cites work

• A capacity scaling algorithm for the constrained maximum flow problem
• Analysis of a flow problem with fixed charges
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Approximation algorithms for certain network improvement problems
• Combinatorial Optimization with Rational Objective Functions
• Finding the Minimum-Cost Maximum Flow in a Series-Parallel Network
• scientific article; zbMATH DE number 5917374 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• Minimum cost flow algorithms for series-parallel networks
• Multicriteria Optimization
• Network flows. Theory, algorithms, and applications.
• On budget-constrained flow improvement.
• On the flow cost lowering problem
• Optimizing cost flows by edge cost and capacity upgrade
• Solving Bicriterion Mathematical Programs
• The accessibility arc upgrading problem
• The quickest flow problem
• The Recognition of Series Parallel Digraphs

Cited in

(13)

• A network simplex method for the budget-constrained minimum cost flow problem
• Minimum cost flows with minimum quantities
• A novel approach to subgraph selection with multiple weights on arcs
• On the complexity and approximability of budget-constrained minimum cost flows
• Minimum cost multi-product flow lines
• scientific article; zbMATH DE number 1696527 (Why is no real title available?)
• The p-median problem with upgrading of transportation costs and minimum travel time allocation
• \(\Gamma\)-robust optimization of project scheduling problems
• On the minimum \(s-t\) cut problem with budget constraints
• The complexity of the timetable‐based railway network design problem
• A generalized approximation framework for fractional network flow and packing problems
• Exploring the discrete and continuous edge improvement problems: models and algorithms
• Network design on undirected series-parallel graphs

This page was built for publication: Budget-constrained minimum cost flows

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