Greedoids and Linear Objective Functions

Abstract

Greedoids were introduced by the authors as generalizations of matroids providing a framework for the greedy algorithm. They can be characterized algorithmically via the optimality of the greedy algorithm for a class of objective functions, which are in general not linear and do not include all linear functions. It is therefore natural to ask the following questions: (1) What are those linear objective functions which can be optimized over any greedoid by the greedy algorithm; (2) what are those greedoids over which the linear objective function can be optimized by the greedy algorithm. This paper gives an answer to both questions. Moreover, it gives slimming procedures for obtaining such greedoids from matroids and it gives briefly some (negative) oracle results about greedoid optimization and greedoid recognition.