Approximations for generalized unsplittable flow on paths with application to power systems optimization

DOI10.1007/S10479-022-05054-YMaRDI QIDQ2678593zbMATH OpenOpenAlexFDO

Authors Areg Karapetyan, Majid Khonji, Sid Chi-Kin Chau, Khaled Elbassioni

Publication date 23 January 2023

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.05876

zbMATH Keywords

AC optimal power flowlogarithmic approximationLP roundingpower systems engineeringQPTASunsplittable flow problem

Mathematics Subject Classification ID

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

Recommendations

• A (1+)-approximation for unsplittable flow on a path in fixed-parameter running time
• Approximation algorithms for the unsplittable flow problem on paths and trees
• A constant factor approximation algorithm for unsplittable flow on paths
• Combinatorial algorithms for the unsplittable flow problem
• A mazing \(2+\epsilon\) approximation for unsplittable flow on a path

Cites work

• A (2+)-approximation algorithm for the storage allocation problem
• A (5/3+)-approximation for unsplittable flow on a path: placing small tasks into boxes
• A logarithmic approximation for unsplittable flow on line graphs
• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• A quasi-PTAS for unsplittable flow on line graphs
• A unified approach to approximating resource allocation and scheduling
• Approximation algorithms for single-source unsplittable flow
• Approximation algorithms for the unsplittable flow problem
• Approximation schemes for \(r\)-weighted minimization knapsack problems
• Caching is hard -- even in the fault model
• Combinatorial Optimization of AC Optimal Power Flow With Discrete Demands in Radial Networks
• Convex quadratic relaxations for mixed-integer nonlinear programs in power systems
• Convex Relaxation of Optimal Power Flow—Part I: Formulations and Equivalence
• Convex Relaxation of Optimal Power Flow—Part II: Exactness
• Exact Convex Relaxation of Optimal Power Flow in Radial Networks
• scientific article; zbMATH DE number 1305389 (Why is no real title available?)
• scientific article; zbMATH DE number 2086936 (Why is no real title available?)
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Maximizing the value of a space mission
• Multicommodity demand flow in a tree and packing integer programs
• New approximation schemes for unsplittable flow on a path
• Off-line admission control for general scheduling problems
• Optimal Power Flow With Inelastic Demands for Demand Response in Radial Distribution Networks
• Quadratically Constrained Quadratic Programs on Acyclic Graphs With Application to Power Flow
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Submodular unsplittable flow on trees

Cited in

(3)

• Efficient computation of optimal energy and fractional weighted flow trade-off schedules
• Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules
• a generalized network flow model with application to power supply-demand problems

This page was built for publication: Approximations for generalized unsplittable flow on paths with application to power systems optimization

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