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

DOI10.1007/s10479-022-05054-yOpenAlexW3181112546MaRDI QIDQ2678593

Sid Chi-Kin Chau, Areg Karapetyan, Majid Khonji, Khaled M. 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

LP roundingAC optimal power flowlogarithmic approximationunsplittable flow problempower systems engineeringQPTAS

Mathematics Subject Classification ID

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

Cites Work

• Caching is hard -- even in the fault model
• Approximation algorithms for the unsplittable flow problem
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Maximizing the value of a space mission
• Off-line admission control for general scheduling problems
• Convex quadratic relaxations for mixed-integer nonlinear programs in power systems
• Complex-demand scheduling problem with application in smart grid
• Approximation schemes for \(r\)-weighted minimization knapsack problems
• Approximation Algorithms for Single-Source Unsplittable Flow
• A quasi-PTAS for unsplittable flow on line graphs
• Exact Convex Relaxation of Optimal Power Flow in Radial Networks
• Submodular Unsplittable Flow on Trees
• A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem
• Multicommodity demand flow in a tree and packing integer programs
• Optimal Power Flow With Inelastic Demands for Demand Response in Radial Distribution Networks
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Combinatorial Optimization of AC Optimal Power Flow With Discrete Demands in Radial Networks
• A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes
• Convex Relaxation of Optimal Power Flow—Part I: Formulations and Equivalence
• Convex Relaxation of Optimal Power Flow—Part II: Exactness
• Quadratically Constrained Quadratic Programs on Acyclic Graphs With Application to Power Flow
• New Approximation Schemes for Unsplittable Flow on a Path
• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• A logarithmic approximation for unsplittable flow on line graphs
• A unified approach to approximating resource allocation and scheduling
• Unnamed Item
• Unnamed Item

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