Convex Resource Allocation Problems on Directed Acyclic Graphs: Duality, Complexity, Special Cases, and Extensions
研究了有向无环图上最小化最长链完成时间的资源分配问题，利用拉格朗日对偶和Dilworth定理得到最优解与对偶的强关系，给出了特例的闭式解，并提出了全多项式近似方案。
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.