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

匹配理论与拟阵理论在组合优化中的融合

基本信息

批准号：
07J01587
负责人：
高澤兼二郎
金额：
$ 1.73万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2007
资助国家：
日本
起止时间：
2007 至 2009
项目状态：
已结题

项目摘要

本年度上げた成果は,主に以下の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の解法によって多項式時間可解であることが知られていた.本成果は,重みつきマッチングおよび重みつきマトロイド交叉に対する古典的なアルゴリズムの共通の拡張する組合せ的アルゴリズムを与えた.

今年取得的成果主要涉及以下1和2： 1. Kt，二分图中的t-free t-matching； 2. Kt，具有独立偶数因子的二分图中的t-matching；不包括完整二分图 Kt,t 作为简单二分图的子图和大于或等于 2 的整数 t。特别是当 t=2 是无平方时它被称为2-匹配，具有汉密尔顿循环问题的松弛问题的方面。本研究的结果如下：(1)加权二分图中的加权Kt，满足具有边权的性质，构建无 t 匹配问题的组合算法； (2) 加权无平方； 2-证明通过匹配推导跳跃系统上的M个凸函数与分支权重具有(a-1)中处理的性质这一事实之间存在充要关系。成果(1)是这样的。对于以前仅使用不切实际的椭球体方法给出多项式时间算法的问题，我们开发了一种组合算法，可以实现实用的计算时间。另外，(2)中跳跃系统上的M凸函数是一个框架，其中包括许多已知在多项式时间内求解的组合优化问题。结果(2)是，在构造多项式时间算法的研究意识中，（1）中处理的加权二分图类被认为是有效的。第 2 节中处理的独立偶数因子问题是匹配问题和拟阵交叉问题的常见推广，这是因子问题的组合算法的构造。虽然加权独立偶数因子问题通常是 NP 困难的，已知一类称为Mitsuki奇循环对称图的加权图可以使用Cunningham和Geelen的求解方法在多项式时间内求解。这项工作基于加权匹配和加权拟阵交叉的经典算法给出了通用的扩展组合算法。