Opening book details…
Can I read On Ordered Languages and the Optimization of Linear Functions by Greedy Algorithms on EtoBox?
On Ordered Languages and the Optimization of Linear Functions by Greedy Algorithms by Ulrich Faigle is a Computer Science article available to read on EtoBox.
What is On Ordered Languages and the Optimization of Linear Functions by Greedy Algorithms about?
The optimization problem for linear functions on finite languages is studied, and an (almost) complete characterization of those functions for which a primal and a dual greedy algorithm work well with respect to a canonically associated linear programming problem is given. The discussion in this paper is within the framework of ordered languages, and the characterization uses the notion of rank feasibility of a weighting with respect to an ordered language. This yields a common generalization of a sufficient condition, obtained recently by Korte and Lovász for greedoids, and the greedy algorithm for ordered sets in Faigel's paper [6]. Ordered greedoids are considered the appropriate generalization of greedoids, and the connection is established between ordered languages, polygreedoids, and Coxeteroids. Answering a question of Björner, the author shows in particular that a polygreedoid is a Coxeteroid if and only if it is derived from an integral polymatroid.
Who reads On Ordered Languages and the Optimization of Linear Functions by Greedy Algorithms?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Ulrich Faigle
- Publisher
- Association for Computing Machinery; Association for Computing Machinery (ACM) (ISSN 0004-5411)
- Published
- 1985
- Language
- EN
- Field
- Computer Science (Physical Sciences)