Submodular unsplittable flow on trees

DOI10.1007/s10107-017-1218-4zbMath1411.90285OpenAlexW2783467389MaRDI QIDQ1801021

Anna Adamaszek, Alina Ene, Andreas Wiese, Parinya Chalermsook

Publication date: 26 October 2018

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-017-1218-4

zbMATH Keywords

approximation algorithmssubmodular functionsunsplittable flow problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (1)

On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation algorithms for the unsplittable flow problem
• Optimization, approximation, and complexity classes
• Tree-width, path-width, and cutwidth
• Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows
• Improved Algorithms for Resource Allocation under Varying Capacity
• A quasi-PTAS for unsplittable flow on line graphs
• Proof verification and the hardness of approximation problems
• 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
• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• On Linear Programming Relaxations for Unsplittable Flow in Trees
• New Approximation Schemes for Unsplittable Flow on a Path
• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths
• The PCP theorem by gap amplification

This page was built for publication: Submodular unsplittable flow on trees