Neighbor Systems: Algorithms and the Relationship with Jump Systems and Bisubmodular Polyhedra

摘要

The concept of neighbor system, introduced by Hartvigsen (2009), is a set of integral vectors satisfying a certain combinatorial property. In this paper, we reveal the relationship of neighbor systems with jump systems and with bisubmodular polyhedra. We firstly prove that for every neighbor system, there exists a jump system which has the same neighborhood structure as the original neighbor system. This shows that the concept of neighbor system is essentially equivalent to that of jump system. We next show that the convex closure of a neighbor system is an integral bisubmodular polyhedron. In addition, we give a characterization of neighbor systems using bisubmodular polyhedra. Finally, we consider the problem of minimizing a separable convex function on a neighbor system. By using the relationship between neighbor systems and jump systems shown in this paper, we prove that the problem can be solved in weakly-polynomial time for a class of neighbor systems.%Hartvigsen（2009）によって導入された近傍システムの概念は，ある種の組合せ的な性質を満たす整数格子点の集合である．本論文では，近傍システムに対し，ジャンプシステムや双劣モジュラ多面体との関係を明らかにする．本論文ではまず，任意の近傍システムに対し，その近傍システムと同じ近傍構造を有するジャンプシステムが存在することを示す．これは，近傍システムの概念がジャンプシステムと本質的に等価であることを示す．次に，近傍システムの凸閉包が整数双劣モジュラ多面体であることを示す．さらに，双劣モジュラ多面体を用いた近傍システムの特徴付けを与える．最後に，近傍システム上での分離凸関数の最小化問題について考える．本論文で示した近傍システムとジャンプシステムの関係を用いることにより，ある種のクラスの近傍システムに対して分離凸関数最小化問題が弱多項式時間で解けることを示す．