Neighbor systems, jump systems, and bisubmodular polyhedra (Q5891686)

The paper presents results on the relationships between neighbor systems, jump systems, and bisubmodular polyhedra. The author first gives definitions of neighbor and jump systems as well as examples of neighbor systems that are not jump systems. He proves that for every (all-)neighbor system there exists a jump system with the same neighborhood structure. An all-neighbor system is a neighbor system with a neighbor function which returns, for any set \(\mathcal F \subset \mathbb{Z}\) and \(x \in {\mathcal F}\), all neighbors of \(x\) in \(\mathcal F.\) He then shows that the convex closure of every all-neighbor system is an integral bisubmodular polyhedron, extending an analogous result for jump systems. Next, the validity of a Greedy algorithm for linear optimization over a neighbour system is proved, and this algorithm is compared to an earlier one. Finally, the author shows that separable convex optimization over neighbor systems can be solved in weakly polynomial time for a certain class of neighbor systems.