Ulrich Faigle
Abstract
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.
- 1 BJORNER, A.RUVKA, O.O jistem problemu minimalnim. Prace Moravske Prirodovedecke Spolecnosti 3 (1926), 37-53.Google Scholar
- 2 boruvka o jistem problemu minimalnium prace moravske prirodvedeckeGoogle Scholar
- 3 CRAPO, H.Selectors: A theory of formal languages, semimodular lattices and shelling processes. Adv. Math. 54 (1984), 233-277.Google Scholar
- 4 EDMONDS, J.Submodular functions, matroids, and certain polyhedra, in Proceedings of the Calgary International Conference on Combinatorial Structure and Their Applications, R. Guy, Ed. Gordon and Breach, New York, 1970, pp. 69-87.Google Scholar
- 5 EDMONDS, J. Matroids and the greedy algorithm Math. Progr. 1 (1971), 127-- 136.Google Scholar
- 6 FAIGLE, U.The greedy algorithm for partially ordered sets. Discr. Math. 28 (1979), 153-159.Google Scholar
- 7 FAIGLE, U.Geometries on partially ordered sets. J. Combin. Theory B 28 (1980), 26-51.Google Scholar
- 8 FUJISHIGE, S.Submodular systems and related topics. Math. Prog. Stud. 22 (1984), 113-131.Google Scholar
- 9 KORTE, B., AND LOVA, SZ, L.Mathematical structures underlying greedy algorithms. In Fundamentals of Computation Theory, F. Grcseg, Ed. Lecture Notes in Computer Science, ,vol. 1.i 7. Springer Verlag, New York, 1981, pp. 205-209. Google Scholar
- 10 KORTE, B., AND LOV/I, SZ, L.Greedoids--A structural framework for the greedy algorithm. In Progress in Combinatorial Optimization, W. R. Pulleyblank. Ed. Academic Press, Toronto, 1984, pp. 221-243.Google Scholar
- 11 KORTE, B., AND LOV~,SZ, L.Structural properties of greedoids. Combinatorica 3 (1983), 259-374.Google Scholar
- 12 KORTE, B., AND LOVASZ, L. Greedoids and linear objective functions. SIAM J. Algor. Discrete Meth. 2(1984), 229-238.Google Scholar
- 13 STOER, J., AND WITZGALL, C.Convexity and optimization in finite dimensions, vol. I. Springer Vedag, New York, 1970.Google Scholar
Index Terms
- On ordered languages and the optimization of linear functions by greedy algorithms
Recommendations
Dual greedy polyhedra, choice functions, and abstract convex geometries
We consider a system of linear inequalities and its associated polyhedron for which we can maximize any linear objective function by finding tight inequalities at an optimal solution in a greedy way. We call such a system of inequalities a dual greedy ...
Randomized greedy algorithms for covering problems
GECCO '18: Proceedings of the Genetic and Evolutionary Computation ConferenceGreedy algorithms provide a fast and often also effective solution to many combinatorial optimization problems. However, it is well known that they sometimes lead to low quality solutions on certain instances. In this paper, we explore the use of ...
Greedy by Chance - Stochastic Greedy Algorithms
ICAS '10: Proceedings of the 2010 Sixth International Conference on Autonomic and Autonomous SystemsFor many complex combinatorial optimization problems, obtaining good solutions quickly is of value either by itself or as part of an exact algorithm. Greedy algorithms to obtain such solutions are known for many problems. In this paper we present ...
Comments