An algorithmic characterization of antimatroids (Q2640448)

This paper provides an algorithmic characterization of truncated antimatroids that helps to provide further insight into the structure and algorithmic relevance of antimatroids. The \(1| prec| f_{\max}\) scheduling problem is generalized in a more abstract form to the minmax nesting problem: Given a simple language (E,\({\mathcal L})\) with an f- monotone maximum nesting function W and a nonnegative integer \(k\leq rank \rho ({\mathcal L})\), find \(\alpha_ k\in {\mathcal L}\) such that \(W(\alpha_ k)=\min \{W(\beta_ k):\beta_ k\in {\mathcal L}\}.\) The main result of the paper is the theorem 5.1: Let (E,\({\mathcal L})\) be a simple language. The greedy algorithm solves the minmax nesting problem for every f-monotone maximum nesting function W if and only if (E,\({\mathcal L})\) is a truncated antimatroid. This theorem extends Lawler's result for job scheduling to a more general class of combinatorial structures. Two examples of problems captured by theorem 5.1 are given in the last section: job scheduling under precedence constraints and road construction in a deflationary period.