A (1+)-approximation for unsplittable flow on a path in fixed-parameter running time

DOI10.4230/LIPICS.ICALP.2017.67MaRDI QIDQ5111398zbMATH OpenOpenAlexFDO

Authors Andreas Wiese

Publication date 27 May 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.ICALP.2017.67

zbMATH Keywords

combinatorial optimizationapproximation algorithmsfixed-parameter algorithmsunsplittable flow on a path

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25) Flows in graphs (05C21) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• A mazing \(2+\epsilon\) approximation for unsplittable flow on a path
• A \((5/3+\varepsilon)\)-approximation for unsplittable flow on a path: placing small tasks into boxes
• New approximation schemes for unsplittable flow on a path
• A constant factor approximation algorithm for unsplittable flow on paths

Cited in

(20)

• Closing the Gap for Pseudo-Polynomial Strip Packing
• A \((5/3+\varepsilon)\)-approximation for unsplittable flow on a path: placing small tasks into boxes
• Parameterized approximation algorithms for bidirected Steiner network problems
• A quasi-PTAS for unsplittable flow on line graphs
• Improved approximation algorithms for unsplittable flow on a path with time windows
• A \((2+\varepsilon)\)-approximation algorithm for the storage allocation problem
• A constant-factor approximation algorithm for unsplittable flow on paths
• New approximation schemes for unsplittable flow on a path
• scientific article; zbMATH DE number 7051239 (Why is no real title available?)
• scientific article; zbMATH DE number 5899246 (Why is no real title available?)
• A mazing \(2+\epsilon\) approximation for unsplittable flow on a path
• A logarithmic approximation for unsplittable flow on line graphs
• Submodular unsplittable flow on trees
• To augment or not to augment: solving unsplittable flow on a path by creating slack
• Fixed-parameter approximation schemes for weighted flowtime
• Approximations for generalized unsplittable flow on paths with application to power systems optimization
• Fixed-parameter algorithms for unsplittable flow cover
• A constant factor approximation algorithm for unsplittable flow on paths
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path

This page was built for publication: A \((1+\varepsilon)\)-approximation for unsplittable flow on a path in fixed-parameter running time

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