Greedy and Optimal Paths in a Weighted Graph Without Circuits and Applications to a Class of Optimization Problems on Finite Posets

Abstract

**Please note that the full text is embargoed** ABSTRACT: 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.