Multicommodity demand flow in a tree and packing integer programs

DOI10.1145/1273340.1273343zbMath1192.68879OpenAlexW2170344325MaRDI QIDQ3580938

Chandra Chekuri, F. Bruce Shepherd, Marcelo Mydlarz

Publication date: 14 August 2010

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

Full work available at URL: https://doi.org/10.1145/1273340.1273343

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Approximation algorithms (68W25)

Related Items (34)

Improved algorithms for resource allocation under varying capacity ⋮ Flexible bandwidth assignment with application to optical networks ⋮ Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract) ⋮ A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem ⋮ Resource allocation problem under single resource assignment ⋮ Optimizing bandwidth allocation in elastic optical networks with application to scheduling ⋮ All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs ⋮ Approximations for generalized unsplittable flow on paths with application to power systems optimization ⋮ The all-or-nothing flow problem in directed graphs with symmetric demand pairs ⋮ A knapsack intersection hierarchy ⋮ Improved Algorithm for Resource Allocation Problems ⋮ Approximability of sparse integer programs ⋮ Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ Complex-demand scheduling problem with application in smart grid ⋮ Stochastic Unsplittable Flows ⋮ Iterative Packing for Demand and Hypergraph Matching ⋮ How unsplittable-flow-covering helps scheduling with job-dependent cost functions ⋮ A constant factor approximation algorithm for the storage allocation problem ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Flexible resource allocation to interval jobs ⋮ Unnamed Item ⋮ Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ Pricing on Paths: A PTAS for the Highway Problem ⋮ The Prize-collecting Call Control Problem on Weighted Lines and Rings ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ On the complexity of anchored rectangle packing ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ Scheduling Resources for Throughput Maximization ⋮ A logarithmic approximation for unsplittable flow on line graphs ⋮ Unnamed Item ⋮ Parametric power supply networks ⋮ Stochastic makespan minimization in structured set systems

This page was built for publication: Multicommodity demand flow in a tree and packing integer programs