Multicommodity flow in trees: packing via covering and iterated relaxation
type: Item
instance of: scholarly article
title: Multicommodity flow in trees: packing via covering and iterated relaxation
zbMATH Open document ID: 1360.90259
author: Yong-Cai Geng
author: Sumit K. Garg
published in: Algorithmica
publication date: 2017-05-17T00:00:00Z
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 05C21
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C57
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 6718314
zbMATH Keywords: multicommodity flow
zbMATH Keywords: approximation algorithms
zbMATH Keywords: iterated LP relaxation
zbMATH Keywords: polyhedral combinatorics
MaRDI profile type: Publication
full work available at URL: s00453-012-9701-z
OpenAlex ID: W2164903952
cites work: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
cites work: A polynomial algorithm for b-matchings: An alternative approach
cites work: Additive Guarantees for Degree-Bounded Directed Network Design
cites work: ``Integer-making'' theorems
cites work: A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths
cites work: \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
cites work: On Column-Restricted and Priority Covering Integer Programs
cites work: Q5743501
cites work: Multicommodity demand flow in a tree and packing integer programs
cites work: Q4938792
cites work: Complexity of approximating bounded variants of optimization problems
cites work: Q5675543
cites work: Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow
cites work: Conversion of coloring algorithms into maximum weight independent set algorithms
cites work: Path problems in generalized stars, complete graphs, and brick wall graphs
cites work: On the Complexity of Timetable and Multicommodity Flow Problems
cites work: Iterated rounding algorithms for the smallest \(k\)-edge connected spanning subgraph
cites work: Approximating the smallest k -edge connected spanning subgraph by LP-rounding
cites work: Primal-dual approximation algorithms for integral flow and multicut in trees
cites work: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
cites work: A factor 2 approximation algorithm for the generalized Steiner network problem
cites work: On the approximability of the maximum common subgraph problem
cites work: Global wire routing in two-dimensional arrays
cites work: Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
cites work: Survivable Network Design with Degree or Order Constraints
cites work: Simpler analysis of LP extreme points for traveling salesman and survivable network design problems
cites work: On the disjoint paths problem
cites work: Iterative Packing for Demand and Hypergraph Matching
cites work: Throughput Maximization for Periodic Packet Routing on Trees and Grids
cites work: k-Edge-Connectivity: Approximation and LP Relaxation
cites work: Approximability of sparse integer programs
cites work: Randomized rounding: A technique for provably good algorithms and algorithmic proofs
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: The Demand-Matching Problem
cites work: Approximating minimum bounded degree spanning trees to within one of optimal
DOI: 10.1007/S00453-012-9701-Z
description: scientific article; zbMATH DE number 6718314