Greedoids and Linear Objective Functions
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper gives slimming procedures for obtaining such greedoids from matroids and it gives briefly some (negative) oracle results about greedoid optimization and greedoid recognition.
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.