An Algorithmic Characterization of Antimatroids

U. Faigle, E. Andrew Boyd

Research output: Contribution to journalArticleAcademicpeer-review

65 Downloads (Pure)

Abstract

In an article entitled “Optimal sequencing of a single machine subject to precedence constraints” E.L. Lawler presented a now classical minmax result for job scheduling. In essence, Lawler's proof demonstrated that the properties of partially ordered sets were sufficient to solve the posed scheduling problem. These properties are, in fact, common to a more general class of combinatorial structures known as antimatroids, which have recently received considerable attention in the literature. It is demonstrated that the properties of antimatroids are not only sufficient but necessary to solve the scheduling problem posed by Lawler, thus yielding an algorithmic characterization of antimatroids. Examples of problems solvable by the general result are provided.
Original languageEnglish
Pages (from-to)197-206
Number of pages10
JournalDiscrete applied mathematics
Volume28
Issue number3
DOIs
Publication statusPublished - 1990

Fingerprint Dive into the research topics of 'An Algorithmic Characterization of Antimatroids'. Together they form a unique fingerprint.

Cite this