article · 1999
The Greedy Algorithm for a Class of Lattice Polyhedra and its Consequences
Kazutoshi Ando
Cited by 0Abstract and details only
Abstract
We consider a class of lattice polyhedra introduced by Hoffman and Schwartz. The polyhedra are defined in terms of a kind of submodular function defined on the set of antichains of a poset. Recently, Krüger [U. Krüger: Structural aspects of ordered polymatroids. Discrete Applied Mathematics (to appear)] showed the validity of a greedy algorithm for this class of lattice polyhedra, which had been proved to be valid for less general class of polyhedra by Faigle and Kern. In this paper, we investigate submodular functions in Krüger's sense and the associated polyhedra. Namely, we see that Lovasz extension of a submodular function in the Krüger's sense is convex, and vice versa. Furthermore, we show an O(n²) time algorithm to test a vector for being an extreme point of the associated polyhedron, where n is the cardinality of the ground set.
Cite this paper
Ando, K. (1999). The Greedy Algorithm for a Class of Lattice Polyhedra and its Consequences.
Ando, Kazutoshi. “The Greedy Algorithm for a Class of Lattice Polyhedra and its Consequences.” 1999.
Ando, Kazutoshi. 1999. “The Greedy Algorithm for a Class of Lattice Polyhedra and its Consequences.”
Ando, K. (1999) ‘The Greedy Algorithm for a Class of Lattice Polyhedra and its Consequences’.
@article{ando1999greedy,
title = {{The Greedy Algorithm for a Class of Lattice Polyhedra and its Consequences}},
author = {Ando, Kazutoshi},
year = {1999}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.