Submodular Unsplittable Flow on Trees

DOI10.1007/978-3-319-33461-5_28zbMath1419.90108OpenAlexW2504092734WikidataQ58203657 ScholiaQ58203657MaRDI QIDQ3186514

Anna Adamaszek, Alina Ene, Parinya Chalermsook, Andreas Wiese

Publication date: 10 August 2016

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/21.11116/0000-0000-73B6-1

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (4)

Improved algorithms for resource allocation under varying capacity ⋮ Approximations for generalized unsplittable flow on paths with application to power systems optimization ⋮ Temporal flows in temporal networks ⋮ A knapsack intersection hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation algorithms for the unsplittable flow problem
• Tree-width, path-width, and cutwidth
• Improved Algorithms for Resource Allocation under Varying Capacity
• A quasi-PTAS for unsplittable flow on line graphs
• An improved approximation algorithm for resource allocation
• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
• An analysis of approximations for maximizing submodular set functions—I
• On Linear Programming Relaxations for Unsplittable Flow in Trees
• New Approximation Schemes for Unsplittable Flow on a Path
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths

This page was built for publication: Submodular Unsplittable Flow on Trees