総説・解説等

マトロイド・劣モジュラ関数の研究の流れを汲んだ離散凸解析による統一的枠組みの中で,離散最適化問題を効率的に解く各種アルゴリズムが提案されてきた.離散凸解析理論の普及を目的として,これらの成果を応用分野の研究者・実務家が享受できるように,関連するアルゴリズムを紹介するデモンストレーションソフトウェアと,アプリケーションソフトウェアを開発した.ソルバ及びデモンストレーションソフトウェアの WEB 公開について報告する.

対称二部グラフとは,二つの頂点集合を分ける軸で線対称性を持つ二部グラフである.本発表では,対称な二部グラフのマッチング構造を調べることを目的とする.まず対称な二部グラフに対しDulmage-Mendelsohn分解を行なうと,得られた成分(マッチング被覆グラフ)は対称性を有することが分かる.マッチング被覆二部グラフは,耳分解により,ある辺に長さ奇数のパスを繰り返し付け加えることで構成できる.本研究では,マッチング被覆二部グラフが対称ならば高々2本のパスを付け加えることで対称性を保持したまま耳分解できることを示す.さらに,対称二部グラフの組合せ的行列理論への応用として,Polyaの問題を一般化した問題を提案し,その問題が多項式可解であることを述べる.

We consider the minimum-cost b-edge dominating set problem. This is a generalization of the edge dominating set problem, but the computational complexity for trees is an astonishing open problem. We make steps toward the resolution of this open problem in the following three directions. (1) We give the first combinatorial polynomial-time algorithm for paths. Prior to our work, the polynomial-time algorithm for paths used linear programming, and it was known that the linear-programming approach could not be extended to trees. Thus, our algorithm would yield an alternative approach to a possible polynomial-time algorithm for trees. (2) We give a fixed-parameter algorithm for trees with the number of leaves as a parameter. Thus, a possible NP-hardness proof for trees should make use of trees with unbounded number of leaves. (3) We give a fully polynomial-time approximation scheme for trees. Prior to our work, the best known approximation factor was two. If the problem is NP-hard, then a possible proof cannot be done via a gap-preserving reduction from any APX-hard problem unless P = NP.We consider the minimum-cost b-edge dominating set problem. This is a generalization of the edge dominating set problem, but the computational complexity for trees is an astonishing open problem. We make steps toward the resolution of this open problem in the following three directions. (1) We give the first combinatorial polynomial-time algorithm for paths. Prior to our work, the polynomial-time algorithm for paths used linear programming, and it was known that the linear-programming approach could not be extended to trees. Thus, our algorithm would yield an alternative approach to a possible polynomial-time algorithm for trees. (2) We give a fixed-parameter algorithm for trees with the number of leaves as a parameter. Thus, a possible NP-hardness proof for trees should make use of trees with unbounded number of leaves. (3) We give a fully polynomial-time approximation scheme for trees. Prior to our work, the best known approximation factor was two. If the problem is NP-hard, then a possible proof cannot be done via a gap-preserving reduction from any APX-hard problem unless P = NP.

線形相補性問題(LCP)とは,線形計画や凸二次計画を特殊ケースとして含む数理計画問題である.LCPが符号可解であるとは,解の取りうる符号パターンの集合が係数要素の大きさによらずに定まることを言う.本研究では,係数行列の対角要素が全て非零であるLCPに対して,その符号可解性に対する必要十分条件を与える.そして,符号可解LCPの解の符号パターンを効率的に得るための組合せ的解法を提案する.その計算量はO(γ)(γは係数の非零要素数の和)である.