Faigle-Kernの双対貪欲多面体とその一般化の研究
Faigle-Kernの双対貪欲多面体とその一般化の研究
Faigle-Kern对偶贪多面体及其推广研究
批准号：
13780353
负责人：
安藤 和敏
金额：
$1.47万
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2001
资助国家：
日本
项目状态：
已结题
起止时间：
2001 至 2002
中文摘要
翻译
点击翻译按钮获取中文摘要
英文摘要
Faigle and Kern (1996)によって導入された双対貪欲多面体と呼ばれる多面体のクラスに対していくつかの理論的成果が得られた.双対貪欲多面体は,左辺の係数行列として半順序集合の反鎖の特性ベクトルを持ち,右辺ベクトルとしてK-劣モジュラ関数とよばれるある種の劣モジュラ関数を持つ線形不等式系によって定義される多面体である.Faigle and Kern (1996)は,双対貪欲多面体上での線形計画問題に対して,双対貪欲算法の有効性を示している.Ando (2002)においては,双対貪欲多面体上での線形関数の最適値として,Lovasz拡張と呼ばれる関数を定義してこの関数の凸性がK-劣モジュラ性を特徴付けることを示した.さらに,与えられたベクトルxが双対貪欲多面体の端点であるかどうかを判定する多項式時間アルゴリズムを与えた.Ando (2003)においては,K-劣モジュラ関数の定義域が根付き森と呼ばれる半順序集合の反鎖集合であるときには,双対貪欲多面体は通常の劣モジュラ多面体のMobius写像と呼ばれる線形変換の像であることを示し,双対貪欲多面体上での最適化問題に関する種々の結果が,この線形変換を用いて明らかにされることを示した.例えば,双対貪欲多面体上での双対貪欲算法の有効性や双対貪欲多面体の交わりの定義不等式系の完全双対整数性に対する簡明な証明を与えた.さらに,Mobius変換の一つの応用として双対貪欲多面体上での最大最小定理を得た.
期刊论文(5)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
K.Ando: "K-submodular functions and convexity of their Lovasz extention"Discrete Applied Mathematics. 122. 1-12 (2002)
K.Ando：“K-子模函数及其 Lovasz 扩展的凸性”离散应用数学。
K.Ando：“K-子模函数及其 Lovasz 扩展的凸性”离散应用数学。
DOI：
--
发表时间：
期刊：
影响因子：
--
作者：
[]
通讯作者：
K.Ando: "Mobius functions of rooted forests and Faigle-Kern's dual greedy polyhedra"IEICE Transactions on Fundamentals. (掲載予定). (2003)
K.Ando：“有根森林的莫比乌斯函数和 Faigle-Kern 的双贪婪多面体”IEICE 基础知识交易（即将出版）。
K.Ando：“有根森林的莫比乌斯函数和 Faigle-Kern 的双贪婪多面体”IEICE 基础知识交易（即将出版）。
DOI：
--
发表时间：
期刊：
影响因子：
--
作者：
[]
通讯作者：
Kazutoshi Ando: "Characterizations of convex geometries by extreme point operator"Discussion Paper Series,Institute of Policy and Planning Sciences,University of Tsukuba. 957. (2001)
安藤一俊：“极值点算子对凸几何的表征”讨论论文系列，筑波大学政策与规划科学研究所。
安藤一俊：“极值点算子对凸几何的表征”讨论论文系列，筑波大学政策与规划科学研究所。
DOI：
--
发表时间：
期刊：
影响因子：
--
作者：
[]
通讯作者：
安藤和敏, 小原朱理, 山本芳嗣: "相互評価の下での可能性定理"Discussion Paper Series,Institute of Policy and Planning Sciences,University of Tsukuba. 960. (2001)
Kazutoshi Ando、Akari Ohara、Yoshitsugu Yamamoto：“相互评价下的可能性定理”讨论论文系列，筑波大学政策与规划科学研究所 960。（2001）
Kazutoshi Ando、Akari Ohara、Yoshitsugu Yamamoto：“相互评价下的可能性定理”讨论论文系列，筑波大学政策与规划科学研究所 960。（2001）
DOI：
--
发表时间：
期刊：
影响因子：
--
作者：
[]
通讯作者：
Kazutoshi Ando: "Extreme point axioms for closure spaces"Discussion Paper Series,Institute of Policy and Planning Sciences,University of Tsukuba. 969. (2002)
安藤一俊：“封闭空间的极值点公理”讨论论文系列，筑波大学政策与规划科学研究所。
安藤一俊：“封闭空间的极值点公理”讨论论文系列，筑波大学政策与规划科学研究所。
DOI：
--
发表时间：
期刊：
影响因子：
--
作者：
[]
通讯作者：
Development of Algorithms for Ultrametric Tree Optimization and Hierarchical Clustering Optimization
-
批准号：22K11921
-
项目类别：Grant-in-Aid for Scientific Research (C)
-
资助金额：$1.58万
-
财政年份：2022
-
负责人：安藤 和敏
-
依托单位：
海外基金