The \textit{Unsplittable Flow on a Path} (UFP) problem has sparked remarkable attention as a challenging combinatorial problem with profound practical implications. Steered by its prominent application in \textit{power engineering}, the present work formulates a novel generalization of UFP, wherein demands and capacities in the input instance are monotone step functions over the set of edges. As an initial step towards tackling this generalization, we draw on and extend ideas from prior research to devise a a quasi-polynomial time approximation scheme (QPTAS) under the premise that the demands and capacities lie in a quasi-polynomial range. Second, retaining the same assumption, an efficient logarithmic approximation is introduced for the single-source variant of the problem. Finally, we round up the contributions by designing a (kind of) black-box reduction that, under some mild conditions, allows to translate LP-based approximation algorithms for the studied problem into their counterparts for the \textit{Alternating Current Optimal Power Flow} (AC OPF) problem -- a fundamental workflow in operation and control of power systems.
翻译:\ textit{ 无法预测的路径流动 (UFP) 问题作为一个具有深刻实际影响的具有挑战性的组合问题引起了引人注目的注意。 由于在\ textit{ power工程} 中的突出应用, 目前的工作形成了对UFP的新型概括化, 输入实例中的需求和能力是一组边缘的单步函数。 作为解决这一普遍化的第一步, 我们从先前的研究中吸取并扩展了各种想法, 以设计一个准极时近似计划( QPTAS), 前提是需求和能力处于准极权范围。 其次, 保留同样的假设, 一种高效的对数近似为问题的单一源变量所引入。 最后, 我们通过设计一种( 一种) 黑箱的减少功能, 在一些温和的条件下, 能够将所研究问题的基于LP的近似算法转换为 用于 \ textitilt{ Alternateimal Power flow} (AC OPFPF) 问题的基本工作流程 。