Convex resource allocation problems on directed acyclic graphs: Duality, complexity, special cases, and extensions

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. The authors 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 them 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.