An algorithmic characterization of antimatroids

Combinatorial aspects of matroids and geometric lattices (05B35) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Review text

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.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: An algorithmic characterization of antimatroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2640448)