Back to Search
Start Over
NEIGHBOR SYSTEMS AND THE GREEDY ALGORITHM.
- Source :
- SIAM Journal on Discrete Mathematics; 2010, Vol. 24 Issue 4, p1637-1661, 24p
- Publication Year :
- 2010
-
Abstract
- A neighbor system, introduced in this paper, is a collection of integral vectors in ℝ<superscript>n</superscript> with some special structure. Such collections (slightly) generalize jump systems, which, in turn, generalize integral bisubmodular polyhedra, integral polymatroids, delta-matroids, matroids, and other structures. We show that neighbor systems provide a systematic and simple way to characterize these structures. One of our main results is a simple greedy algorithm for optimizing over (finite) neighbor systems starting from any feasible vector. The algorithm is (essentially) identical to the usual greedy algorithm on matroids and integral polymatroids when the starting vector is zero. But in all other cases, from matroids through jump systems, it appears to be a new greedy algorithm. We end the paper by introducing another structure, which is more general than neighbor systems, and indicate that essentially the same greedy algorithm also works for this structure. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 24
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 64279017
- Full Text :
- https://doi.org/10.1137/090777463