Multicommodity demand flow in a tree and packing integer programs

DOI10.1145/1273340.1273343zbMATH Open1192.68879OpenAlexW2170344325MaRDI QIDQ3580938FDOQ3580938

Authors: Chandra Chekuri, Marcelo Mydlarz, F. Bruce Shepherd 

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) Approximation algorithms (68W25) Integer programming (90C10)

Cited In (34)

• Routing in undirected graphs with constant congestion
• 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 makespan minimization in structured set systems (extended abstract)
• Flexible resource allocation to interval jobs
• Stochastic makespan minimization in structured set systems
• Stochastic unsplittable flows
• Improved algorithms for resource allocation under varying capacity
• Resource allocation problem under single resource assignment
• Scheduling Resources for Throughput Maximization
• A \((2+\varepsilon)\)-approximation algorithm for the storage allocation problem
• Parametric power supply networks
• How unsplittable-flow-covering helps scheduling with job-dependent cost functions
• Pricing on paths: a PTAS for the highway problem
• All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs
• The prize-collecting call control problem on weighted lines and rings
• Flexible bandwidth assignment with application to optical networks
• New algorithms for maximum disjoint paths based on tree-likeness
• The all-or-nothing flow problem in directed graphs with symmetric demand pairs
• Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators
• Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators
• A logarithmic approximation for unsplittable flow on line graphs
• A knapsack intersection hierarchy
• Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
• Optimizing bandwidth allocation in elastic optical networks with application to scheduling
• Iterative packing for demand and hypergraph matching
• Title not available (Why is that?)
• Approximations for generalized unsplittable flow on paths with application to power systems optimization
• On the complexity of anchored rectangle packing
• Title not available (Why is that?)
• Improved algorithm for resource allocation problems
• A constant factor approximation algorithm for the storage allocation problem
• Multicommodity flow in trees: packing via covering and iterated relaxation

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

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