組合せ最適化におけるマッチング理論とマトロイド理論の融合

点击翻译按钮获取中文摘要

本年度上げた成果は,主に以下の1,2を扱ったものである:1.二部グラフにおけるKt,t-free t-マッチング;2.独立偶因子.1.の二部グラフにおけるKt,t-free t-マッチングとは,単純二部グラフと2以上の整数tに対して,完全二部グラフKt,tを部分グラフとして含まないt-マッチングのことである.特にt=2の場合はsquare-free 2-マッチングと呼ばれ,ハミルトン閉路問題の緩和問題としての側面を持っ.本研究の成果は以下の二つである:(1)枝重みがある性質をみたす重みつき二部グラフにおける重みつきKt,t-free t-マッチング問題に対する組合せ的アルゴリズムの構築;(2)重みつきsquare-free 2-マッチングがジャンプシステム上のM凸関数を導出することと,枝重みが(a-1)で扱った性質を持つことが必要十分の関係を持つことの証明.成果(1)は,これまで楕円体法という実用的でない方法でのみ多項式時間アルゴリズムが与えられていた問題に対し,実用的な計算時間を達成する組合せ的アルゴリズムを構築したものである.また,(2)におけるジャンプシステム上のM凸関数とは,多項式時間で解くことが知られている組合せ最適化問題を多く含む枠組である.成果(2)は,多項式時間アルゴリズムを構築するという研究意識においては,(1)で扱った重みつき二部グラフのクラスが妥当であるという裏付けを与えるものである.2.で扱った独立偶因子問題は,マッチング問題とマトロイド交叉問題の共通の一般化である.本研究の成果は,重みつき奇閉路対称グラフにおける重みつき独立偶因子問題に対する組合せ的アルゴリズムの構築である.重みつき独立偶因子問題は一般にはNP困難である一方,重みつき奇閉路対称グラフと呼ばれる重みつきグラフのクラスにおいてはCunninghamとGeelenの解法によって多項式時間可解であることが知られていた.本成果は,重みつきマッチングおよび重みつきマトロイド交叉に対する古典的なアルゴリズムの共通の拡張する組合せ的アルゴリズムを与えた.