Document Type


Source Publication Title

Technical Report 197


In several recent papers B. Korte and L. Lovasz considered a mathematical structure called a simple language on which a greedy algorithm can operate (see [31,J41, OD. The concept of greedoid has been defined by relaxing an axiom and strengthening an other axiom from the definition of the matroid. Under some constraints imposed to the objective function of a combinatorial optimization problem on a greedoid, the greedy algorithm provides an efficient method for solving the problem. An algorithmic characterization of the greedoids, similar to that of the matroids, was further searched. The effort has been justified-by several examples of combinatorial optimization problems defined on greedoids. A class of greedoids connected to finite posets has been also considered by U. Faigle (see 121). In this paper we consider a class of simple languages called the nonextendible languages without circuits and we examine the combinatorial optimization problems on such a language, under the Korte-Lovasz constraints imposed to the objective functions. The main result is that a greedy algorithm works for all such objective functions if and only if the non extendible language without circuits is a greedoid. The structure of these greedoids is clarified by means of the graph associated to a simple language, which has in this case particular properties. The problem of giving an algorithmic characterization of the greedoids underlined by extendible languages or non extendible languages with circuits is still an open question. The application of the results to a simple language defined on a finite poset is also discussed.


Mathematics | Physical Sciences and Mathematics

Publication Date




Included in

Mathematics Commons



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.