Neighbor Systems and the Greedy Algorithm : Extended Abstract (Combinatorial Optimization and Discrete Algorithms)
David Hartvigsen · Kyoto University Research Information Repository (Kyoto University) · 2010
A neighbor system, introduced in this paper, is a collection of integral vectors in \Re^{n} 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.A main result of the paper 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. §1. IntroductionThis paper introduces a new structure, called a neighbor system, over which a straightforward greedy algorithm always finds an optimal solution.This system generalizes a variety of structures (matroids and generalizations of matroids) that have been developed since the 1930\mathrm{s} and gives a new, standardized way of defining them.This paper is an extended abstract/excerpt of the full version of the paper; in particular, all non-trivial proofs have been removed.The full version will appear elsewhere.Before discussing our results in more detail, let us briefly review some key structures and re- sults from the literature.(Except where noted, the greedy algorithms discussed below optimize these structures over linear objective functions.)Matroids.Hassler Whitney in 1935 [27] introduced both the structure of matroids and the basic greedy algorithm for optimizing over them.Generalized matroids.This structure was introduced by Tardos [26], along with a greedy algorithm, as a generalization of matroids.