Multicommodity flows and cuts in polymatroidal networks

DOI10.1145/2090236.2090268zbMath1347.68278arXiv1110.6832OpenAlexW2146728909MaRDI QIDQ2826073

Pramod Viswanath, Chandra Chekuri, Adnan Raja, Sreeram Kannan

Publication date: 7 October 2016

Published in: SIAM Journal on Computing, Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (Search for Journal in Brave)

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

zbMATH Keywords

multicommodity flowline embeddingpolymatroidal networksflow-cut gapflow-cut gapsline embeddingsnode-capacitated networkssub-modular flowspolymatroidal network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25) Flows in graphs (05C21)

Related Items (5)

Congestion-Free Rerouting of Flows on DAGs ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ The all-or-nothing flow problem in directed graphs with symmetric demand pairs ⋮ Graph cuts with interacting edge weights: examples, approximations, and algorithms ⋮ A node-capacitated Okamura-Seymour theorem

Cites Work

• Matroids and linking systems
• Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• A lower bound on the integrality gap for minimum multicut in directed networks
• A flow model based on polylinking system
• A node-capacitated Okamura-Seymour theorem
• On average distortion of embedding metrics into the line
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Multicommodity flows in planar graphs
• The reproducible properties of correct forecasts
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The dimensions of individual strings and sequences
• The geometry of graphs and some of its algorithmic applications
• Improved bounds on the max-flow min-cut ratio for multicommodity flows
• Approximating directed multicuts
• A 2-Approximation Algorithm for the Directed Multiway Cut Problem
• Divide-and-conquer approximation algorithms via spreading metrics
• Capacity of Multiple Unicast in Wireless Networks: A Polymatroidal Approach
• Compress-and-Forward Scheme for Relay Networks: Backword Decoding and Connection to Bisubmodular Flows
• Submodular Cost Allocation Problem and Applications
• Approximation Algorithms for Steiner and Directed Multicuts
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Polynomial flow-cut gaps and hardness of directed cut problems
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Vertex cuts, random walks, and dimension reduction in series-parallel graphs
• Improved approximation for directed cut problems
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• Directed metrics and directed graph partitioning problems
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• The Complexity of Forecast Testing
• Polymatroidal flow network models with multiple sinks
• Preemptive Scheduling with Release Times, Deadlines, and Due Times
• The Well-Calibrated Bayesian
• Computing Maximal “Polymatroidal” Network Flows
• Asymptotic calibration
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Dimension in Complexity Classes
• Universal prediction
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Submodular Function Minimization under Covering Constraints
• Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
• On the geometry of graphs with a forbidden minor
• Excluded minors, network decomposition, and multicommodity flow
• A Max-Flow/Min-Cut Algorithm for Linear Deterministic Relay Networks
• Wireless Network Information Flow: A Deterministic Approach
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Euclidean distortion and the sparsest cut
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Embedding k-Outerplanar Graphs into l1
• Approximation Algorithms for Submodular Multiway Partition
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• On dominated \(\ell_1\) metrics
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Multicommodity flows and cuts in polymatroidal networks