An algorithmic characterization of antimatroids (Q2640448): Difference between revisions
From MaRDI portal
Revision as of 14:31, 21 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An algorithmic characterization of antimatroids |
scientific article |
Statements
An algorithmic characterization of antimatroids (English)
0 references
1990
0 references
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.
0 references
algorithmic characterization
0 references
truncated antimatroids
0 references
minmax nesting problem
0 references
greedy algorithm
0 references
job scheduling
0 references
precedence constraints
0 references