A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem

DOI10.1007/S10107-021-01683-6MaRDI QIDQ2089770zbMATH OpenOpenAlexFDO

Authors Hiroshi Hirai, Motoki Ikeda

Publication date 24 October 2022

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.01599

zbMATH Keywords

discrete convex analysissubmodular flowcost-scaling methodminimum-cost node-capacitated multiflowreducible bisubmodular flow

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Flows in graphs (05C21)

Abstract: In this paper, we address the minimum-cost node-capacitated multiflow problem in an undirected network. For this problem, Babenko and Karzanov (2012) showed strongly polynomial-time solvability via the ellipsoid method. Our result is the first combinatorial weakly polynomial-time algorithm for this problem. Our algorithm finds a half-integral minimum-cost maximum multiflow in $O(mlog(nCD)mathrmSF(kn,m,k))$ time, where $n$ is the number of nodes, $m$ is the number of edges, $k$ is the number of terminals, $C$ is the maximum node capacity, $D$ is the maximum edge cost, and $mathrmSF(n^{\prime },m^{\prime },eta)$ is the time complexity of solving the submodular flow problem in a network of $n^{\prime }$ nodes, $m^{\prime }$ edges, and a submodular function with $eta$-time-computable exchange capacity. Our algorithm is built on discrete convex analysis on graph structures and the concept of reducible bisubmodular flows.

Recommendations

• A dual descent algorithm for node-capacitated multiflow problems and its applications
• Min-cost multiflows in node-capacitated undirected networks
• A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
• Minimum cost multiflows in undirected networks
• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem

Cites work

• scientific article; zbMATH DE number 8667 (Why is no real title available?)
• scientific article; zbMATH DE number 3550435 (Why is no real title available?)
• A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
• A dual descent algorithm for node-capacitated multiflow problems and its applications
• BALANCED BISUBMODULAR SYSTEMS AND BIDIRECTED FLOWS
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Connections in combinatorial optimization
• Discrete Convex Analysis
• Discrete convex functions on graphs and their algorithmic applications
• Finding feasible vectors of Edmonds-Giles polyhedra
• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
• Min-cost multiflows in node-capacitated undirected networks
• Minimum cost multiflows in undirected networks
• Multiway cuts in node weighted graphs
• New algorithms for the intersection problem of submodular systems
• On \(0,\pm 1\) matrices, odd vectors, and bisubmodular polyhedra
• On some connectivity properties of Eulerian graphs
• Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost
• Some new results on node-capacitated packing of A-paths
• Submodular functions and optimization.
• \(L\)-convexity on graph structures

Cited in

(7)

• A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
• Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity
• Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost
• Minimum cost multiflows in undirected networks
• Min-cost multiflows in node-capacitated undirected networks
• A dual descent algorithm for node-capacitated multiflow problems and its applications

This page was built for publication: A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem

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