Convex Resource Allocation Problems on Directed Acyclic Graphs: Duality, Complexity, Special Cases, and Extensions
Convex Resource Allocation Problems on Directed Acyclic Graphs: Duality, Complexity, Special Cases, and Extensions
复制标题
DOI：
10.1287/moor.15.4.736
复制
发表时间：
1990-10
期刊：
影响因子：
--
通讯作者：
C. Monma;A. Schrijver;M. Todd;V. Wei
中科院分区：
文献类型：
--
作者：
C. Monma;A. Schrijver;M. Todd;V. Wei
考虑以下有向非循环图（优先图）上的资源分配问题。每个顶点都有一个已知的工作负载，并且有一个固定的总资源可用。处理顶点所需的时间与分配给它的资源量成反比。完成所有工作的时间是完成图中最长链的时间长度。在有限的资源条件下，找到一个最小化完成所有工作所需时间的分配问题可以表述为一个可分离的凸规划问题。我们使用拉格朗日对偶凸规划，长度，宽度不等式，和Dilworth定理的有向无环图的结果，得到这个问题的最优解和它的对偶之间的强关系。这使我们能够获得封闭形式的解决方案，某些特殊类别的图，并导致推广的LYM性质的偏序集。一般问题的计算复杂性是一个悬而未决的问题。然而，椭球方法产生一个全多项式近似方案，并可以在相关的决策问题上有所启发。本文的结果被证明是扩展到完美图上的资源分配问题。
Consider the following resource allocation problem on a directed acyclic graph the precedence graph. Each vertex has a known work load, and a fixed amount of total resource is available. The time required to process a vertex is inversely proportional to the amount of the resource allocated to it. The time to complete all of the work is the length of time to complete a longest chain in the graph. The problem of finding an allocation which minimizes the time required to complete all of the work subject to the limited resource availability can be formulated as a separable convex programming problem. We use results from Lagrangian duality for convex programs, the length-width inequality, and Dilworth's Theorem for directed acyclic graphs, to obtain a strong relationship between optimal solutions of this problem and its dual. This allows us to obtain closed-form solutions for certain special classes of graphs, and leads to a generalization of the LYM Property for partially ordered sets. The computational complexity of the general problem is an open question. However, the ellipsoid method yields a fully-polynomial approximation scheme, and some light can be shed on the associated decision problem. The results of this paper are shown to extend to resource allocation problems on perfect graphs.