Multicommodity flows and cuts in polymatroidal networks
type: Item
instance of: scholarly article
title: Multicommodity flows and cuts in polymatroidal networks
zbMATH Open document ID: 1347.68278
zbMATH Open document ID: 1346.90698
DOI: 10.1145/2090236.2090268
DOI: 10.1137/130906830
author: Chandra Chekuri
author: Sreeram Kannan
author: Adnan Raja
author: P. Viswanath
published in: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference
published in: SIAM Journal on Computing
publication date: 2016-10-07T00:00:00Z
publication date: 2015-08-03T00:00:00Z
full work available at URL: https://arxiv.org/abs/1110.6832
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 05C21
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6636360
zbMATH DE Number: 6468890
zbMATH Keywords: flow-cut gaps
zbMATH Keywords: line embeddings
zbMATH Keywords: node-capacitated networks
zbMATH Keywords: polymatroidal networks
zbMATH Keywords: sub-modular flows
zbMATH Keywords: multicommodity flow
zbMATH Keywords: flow-cut gap
zbMATH Keywords: polymatroidal network
zbMATH Keywords: line embedding
MaRDI profile type: Publication
OpenAlex ID: W2146728909
OpenAlex ID: W2111999854
arXiv ID: 1110.6832
cites work: Wireless Network Information Flow: A Deterministic Approach
cites work: Improved approximation for directed cut problems
cites work: O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
cites work: Q4633867
cites work: Euclidean distortion and the sparsest cut
cites work: An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
cites work: On Lipschitz embedding of finite metric spaces in Hilbert space
cites work: Vertex cuts, random walks, and dimension reduction in series-parallel graphs
cites work: Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
cites work: Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
cites work: Directed metrics and directed graph partitioning problems
cites work: Embedding k-Outerplanar Graphs into l1
cites work: Submodular Cost Allocation Problem and Applications
cites work: Approximation Algorithms for Submodular Multiway Partition
cites work: Submodular function maximization via the multilinear relaxation and contention resolution schemes
cites work: Approximating directed multicuts
cites work: Polynomial flow-cut gaps and hardness of directed cut problems
cites work: Q4149476
cites work: Divide-and-conquer approximation algorithms via spreading metrics
cites work: Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
cites work: Polymatroidal flow network models with multiple sinks
cites work: Improved Approximation Algorithms for Minimum Weight Vertex Separators
cites work: Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
cites work: Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
cites work: A flow model based on polylinking system
cites work: Q4471328
cites work: Cuts, trees and \(\ell_1\)-embeddings of graphs
cites work: Submodular Function Minimization under Covering Constraints
cites work: Capacity of Multiple Unicast in Wireless Networks: A Polymatroidal Approach
cites work: Excluded minors, network decomposition, and multicommodity flow
cites work: Approximation Algorithms for Steiner and Directed Multicuts
cites work: Computing Maximal “Polymatroidal” Network Flows
cites work: A node-capacitated Okamura-Seymour theorem
cites work: On the geometry of graphs with a forbidden minor
cites work: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
cites work: The geometry of graphs and some of its algorithmic applications
cites work: Q3682236
cites work: Preemptive Scheduling with Release Times, Deadlines, and Due Times
cites work: On dominated \(\ell_1\) metrics
cites work: A 2-approximation algorithm for the directed multiway cut problem
cites work: Multicommodity flows in planar graphs

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: Improved bounds on the max-flow min-cut ratio for multicommodity flows

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: On average distortion of embedding metrics into the line

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: Compress-and-Forward Scheme for Relay Networks: Backword Decoding and Connection to Bisubmodular Flows

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: A lower bound on the integrality gap for minimum multicut in directed networks

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: Matroids and linking systems

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: A Max-Flow/Min-Cut Algorithm for Linear Deterministic Relay Networks

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: Effective Strong Dimension in Algorithmic Information and Computational Complexity

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: Q5515914

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: The Well-Calibrated Bayesian

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: The Complexity of Forecast Testing

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: Asymptotic calibration

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: Dimension in Complexity Classes

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: The dimensions of individual strings and sequences

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: Universal prediction

Multicommodity flows and cuts in polymatroidal networks (cites work)
cites work: The reproducible properties of correct forecasts