Faigle-Kernの双対貪欲多面体とその一般化の研究

Faigle-Kern对偶贪多面体及其推广研究

基本信息

批准号：
13780353
负责人：
安藤和敏
金额：
$ 1.47万
依托单位：
Shizuoka University (2002)University of Tsukuba (2001)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13780353/
关键词：
Mobius function greedy algorithm poset submodular function convex function antimatroid convex geometry closure operator choice function matroid

项目摘要

Faigle and Kern (1996)によって導入された双対貪欲多面体と呼ばれる多面体のクラスに対していくつかの理論的成果が得られた.双対貪欲多面体は,左辺の係数行列として半順序集合の反鎖の特性ベクトルを持ち,右辺ベクトルとしてK-劣モジュラ関数とよばれるある種の劣モジュラ関数を持つ線形不等式系によって定義される多面体である.Faigle and Kern (1996)は,双対貪欲多面体上での線形計画問題に対して,双対貪欲算法の有効性を示している.Ando (2002)においては,双対貪欲多面体上での線形関数の最適値として,Lovasz拡張と呼ばれる関数を定義してこの関数の凸性がK-劣モジュラ性を特徴付けることを示した.さらに,与えられたベクトルxが双対貪欲多面体の端点であるかどうかを判定する多項式時間アルゴリズムを与えた.Ando (2003)においては,K-劣モジュラ関数の定義域が根付き森と呼ばれる半順序集合の反鎖集合であるときには,双対貪欲多面体は通常の劣モジュラ多面体のMobius写像と呼ばれる線形変換の像であることを示し,双対貪欲多面体上での最適化問題に関する種々の結果が,この線形変換を用いて明らかにされることを示した.例えば,双対貪欲多面体上での双対貪欲算法の有効性や双対貪欲多面体の交わりの定義不等式系の完全双対整数性に対する簡明な証明を与えた.さらに,Mobius変換の一つの応用として双対貪欲多面体上での最大最小定理を得た.

Faigle和Kern（1996）引入的一类称为双重贪婪多面体的多面体获得了几种理论结果。双重贪婪的多面体是由线性不等式系统定义的多面体，其特征性向量是部分有序的集合作为左侧系数矩阵的特征矢量，而某些称为k-submodular函数作为右侧矢量的函数。 Faigle和Kern（1996）证明了双重贪婪计算在双重贪婪多面体上对线性编程问题的有效性。 Ando在（2002）中，我们将一个称为lovasz扩展的函数定义为双贪婪polyhedra上线性函数的最佳值，以表明此函数的凸度表征k-submodularity。此外，我们给出了一种多项式时算法，该算法确定给定矢量X是否是双贪婪多面体的终点。 Ando在（2003年）中，当k子管函数的结构域是一个称为根森林的部分有序集的反链集时，双贪婪的多面体多面性多面体是一个线性转换的图像，称为普通的次生型多面体的Mobius映射，并表明，在多面性的恋爱中，它在多面性的过程中表明了各种结果。例如，我们提供了一个简单的证据，证明了双重贪婪计算对双重贪婪多面体的有效性以及双重贪婪多面体相交的不平等的完美双重完整性。此外，我们在双重贪婪多面体上获得了最大定理，作为Mobius转换的应用。