A dual descent algorithm for node-capacitated multiflow problems and its applications

DOI10.1145/3291531zbMATH Open1457.90026arXiv1508.07065OpenAlexW2962788224WikidataQ128728039 ScholiaQ128728039MaRDI QIDQ4629985FDOQ4629985

Hiroshi Hirai

Publication date: 28 March 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Abstract: In this paper, we develop an $O((mlogk)mMSF(n,m,1))$-time algorithm to find a half-integral node-capacitated multiflow of the maximum total flow-value in a network with $n$ nodes, $m$ edges, and $k$ terminals, where $mMSF(n^{\prime },m^{\prime },gamma)$ denotes the time complexity of solving the maximum submodular flow problem in a network with $n^{\prime }$ nodes, $m^{\prime }$ edges, and the complexity $gamma$ of computing the exchange capacity of the submodular function describing the problem. By using Fujishige-Zhang algorithm for submodular flow, we can find a maximum half-integral multiflow in $O(m{n}^{3}logk)$ time. This is the first combinatorial strongly polynomial time algorithm for this problem. Our algorithm is built on a developing theory of discrete convex functions on certain graph structures. Applications include "ellipsoid-free" combinatorial implementations of a 2-approximation algorithm for the minimum node-multiway cut problem by Garg, Vazirani, and Yannakakis.

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

Recommendations

• A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem
• A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
• Min-cost multiflows in node-capacitated undirected networks
• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
• Minimum cost multiflows in undirected networks

zbMATH Keywords

discrete convex analysissubmodular flownode-capacitated multiflownode-multiway cut

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Approximation algorithms (68W25)

Cited In (3)

• Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity
• An efficient graph technique based dual-type algorithm for NMNF problems with large capacity constraints
• A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem

This page was built for publication: A dual descent algorithm for node-capacitated multiflow problems and its applications

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