Abstract:
This talk continues the series of talks on the reduction of complexity of dynamic programming for sequencing problems under precedence constraints. Turns out, in 1990, George Steiner had obtained a paramount result in this field.
Dynamic programming solutions are mostly constrained by memory requirements, hence the obvious need to know them in advance. The most popular way of doing so is by the use of poset ideals (i.e., the subsets of a poset that, for each their element, contain its predecessors), which easily relate to "feasible task lists" of routing problems.
The problem of counting the number N of ideals is #P-complete [Provan, Ball 1983]. However, some of its instances are polynomially solvable [Steiner, 1990]; those will form the prime matter of our report. We also intend to describe Steiner's algorithm that generates all the ideals in time O(poset's cardinality) per ideal and to mention Wild's algorithm [Wild 2012], which generates all ideals of given cardinality in output-polynomial time.
References:
Provan, J. Scott, and Michael O. Ball. "The complexity of counting cuts and of computing the probability that a graph is connected." SIAM Journal on Computing 12.4 (1983): 777-788.
Steiner, George. "On the complexity of dynamic programming for sequencing problems with precedence constraints." Annals of Operations Research 26.1 (1990): 103-123.
Wild, Marcel. "Output-polynomial enumeration of all fixed-cardinality ideals of a poset, respectively all fixed-cardinality subtrees of a tree." Order (2012): 1-15.
|
