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

DOI10.1007/S10107-021-01683-6zbMATH Open1504.90124arXiv1909.01599OpenAlexW3204303505MaRDI QIDQ2089770FDOQ2089770

Authors: Hiroshi Hirai, Motoki Ikeda 

Publication date: 24 October 2022

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

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.

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

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

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)

Cites Work

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

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
• A dual descent algorithm for node-capacitated multiflow problems and its applications
• Min-cost multiflows in node-capacitated undirected networks

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)