Submodular unsplittable flow on trees
type: Item
instance of: scholarly article
title: Submodular unsplittable flow on trees
zbMATH Open document ID: 1411.90285
author: Anna Adamaszek
author: Parinya Chalermsook
author: Alina Ene
author: Andreas Wiese
published in: Mathematical Programming. Series A. Series B
publication date: 2018-10-26T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6966242
zbMATH Keywords: unsplittable flow problem
zbMATH Keywords: submodular functions
zbMATH Keywords: approximation algorithms
MaRDI profile type: Publication
full work available at URL: s10107-017-1218-4
OpenAlex ID: W2783467389
cites work: A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
cites work: Proof verification and the hardness of approximation problems
cites work: A quasi-PTAS for unsplittable flow on line graphs
cites work: New Approximation Schemes for Unsplittable Flow on a Path
cites work: A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths
cites work: An improved approximation algorithm for resource allocation
cites work: Improved Algorithms for Resource Allocation under Varying Capacity
cites work: Approximation algorithms for the unsplittable flow problem
cites work: Q4633902
cites work: Approximation algorithms for maximum independent set of pseudo-disks
cites work: Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
cites work: Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
cites work: The PCP theorem by gap amplification
cites work: On Linear Programming Relaxations for Unsplittable Flow in Trees
cites work: Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows
cites work: Q2941641
cites work: Tree-width, path-width, and cutwidth
cites work: Q3096108
cites work: An analysis of approximations for maximizing submodular set functions—I
cites work: Optimization, approximation, and complexity classes
DOI: 10.1007/S10107-017-1218-4
Recommended article: Submodular Unsplittable Flow on Trees
Recommended article: Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees
Recommended article: On Linear Programming Relaxations for Unsplittable Flow in Trees
Recommended article: FPT and FPT-Approximation Algorithms for Unsplittable Flow on Trees
Recommended article: Submodular functions and rooted trees
Recommended article: Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions
Recommended article: Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties
Recommended article: An application of submodular flows
Recommended article: Q3220319
Recommended article: Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
description: scientific article; zbMATH DE number 6966242