New polynomial-time algorithms for Camion bases

Komei Fukuda and Antoine Musitelli
Discrete Mathematics
Volume 306, Issue 24 , 28 December 2006, Pages 3302-3306
http://dx.doi.org/10.1016/j.disc.2006.06.015

お世話になりっぱなしの福田先生の論文．
行列Mに対して，その(列)基底Bを考える．非基底をNとしてM=(B N)と書くことにする．
基底BがMのCamion基底であるとは，Mのいくつかの列の符号を逆転させることによってB^{-1}N≧Oとすることができることである．
(幾何的に言うと，これはMが生成する中心アレンジメントにおいてBが単体領域を生成することである．)
Camion (1968) はCamion基底が常に存在することを示したが，Camion基底を発見する多項式時間アルゴリズムは知られていない (困難性も知られていない)．
Fonlupt and Raco (1984) はMが完全ユニモジュラの場合の多項式時間アルゴリズムを設計している．
この論文ではFonlupt and Racoよりも高速なアルゴリズムを提案している．