Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs

DOI10.1007/978-3-642-03685-9_4zbMath1254.68353OpenAlexW2103363383MaRDI QIDQ3638868

Alina Ene, Chandra Chekuri, Nitish Korula

Publication date: 28 October 2009

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03685-9_4

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items (16)

Improved algorithms for resource allocation under varying capacity ⋮ A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem ⋮ Submodular Unsplittable Flow on Trees ⋮ A knapsack intersection hierarchy ⋮ Approximability of sparse integer programs ⋮ Stochastic Unsplittable Flows ⋮ Iterative Packing for Demand and Hypergraph Matching ⋮ A constant factor approximation algorithm for the storage allocation problem ⋮ Parametric Power Supply Networks ⋮ Unnamed Item ⋮ Pricing on Paths: A PTAS for the Highway Problem ⋮ The Prize-collecting Call Control Problem on Weighted Lines and Rings ⋮ Submodular unsplittable flow on trees ⋮ On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines ⋮ A logarithmic approximation for unsplittable flow on line graphs ⋮ Parametric power supply networks

This page was built for publication: Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs