ブール理論に基づく離散システムの構造解析と計算限界の研究
ブール理論に基づく離散システムの構造解析と計算限界の研究
基于布尔理论的离散系统结构分析及计算极限研究
批准号：
16092217
负责人：
牧野 和久
金额：
$8.83万
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
2004
资助国家：
日本
项目状态：
已结题
起止时间：
2004 至 2007
中文摘要
翻译
点击翻译按钮获取中文摘要
英文摘要
社会システムや産業活動などに関連して現れる生産計画,環境計画,スケジューリング,最適投資などを始めとする重要な問題の多くは,ブール理論あるいは,擬ブール理論に基づく離散システム上の問題として捉えることができる,例えば,線形計画問題(LP)も,有向マトロイドを用いて,擬ブール理論に基づく離散システム上の問題と見なせる,本研究では,これまで申請者が培ってきた(擬)ブール理論,劣モジュラ関数による構造解析手法を用いて,離散システムの有用な構造的性質の抽出し,その性質を利用することで,計算限界を明らかにすること(高速アルゴリズムの開発,および,計算量下界の提示)を試みた.本年度は最終年度として,ホーン理論の解構造の連結性,その内包,外包に対する演繹推論問題に対してその計算量を明らかにした。また,自己双対論理関数の彩色に関する特徴付け,ラミナー制約をもつ単調な凹関数最小化に対するアルゴリズムの開発,連結度要求に基づく施設配置問題に対する近似アルゴリズムの開発を行った.
期刊论文(16)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
Minimum Cost Source Location Problems with Flow Requirements
最低成本源位置与流量要求的问题
最低成本源位置与流量要求的问题
DOI：
--
发表时间：
2006
期刊：
LATIN 2006, Lecture Notes in Computer Science 3887
影响因子：
--
作者：
[M.Sakashita, K.Makino, S.Fujishige]
通讯作者：
S.Fujishige
How to Collect Balls Moving in the Euclidean Plane
如何收集在欧几里得平面上移动的球
如何收集在欧几里得平面上移动的球
DOI：
--
发表时间：
期刊：
Discrete Applied Mathematics (to appear)
影响因子：
--
作者：
[Y.Asahiro, T.Horiyama, K.Makino, H.Ono, T.Sakuma, M.Yamashita]
通讯作者：
M.Yamashita
Minimizing a Montone Concave Function with Laminar Covering Constraints. ISAAC 2005:
使用层流覆盖约束最小化单调凹函数。
使用层流覆盖约束最小化单调凹函数。
DOI：
--
发表时间：
2005
期刊：
Lecture Notes in Computer Science 3827
影响因子：
--
作者：
[M.Sakashita, K.Makino, S.Fujishige]
通讯作者：
S.Fujishige
On the Boolean connectivity problem for Horn relations
Horn关系的布尔连通性问题
Horn关系的布尔连通性问题
DOI：
10.1016/j.dam.2010.08.019
发表时间：
2010
期刊：
Discrete Applied Mathematics
影响因子：
1.1
作者：
[K. Makino, S.Tamaki, and M. Yamamoto]
通讯作者：
and M. Yamamoto
DOI：
10.1016/j.disc.2008.01.028
发表时间：
2007-08
期刊：
影响因子：
--
作者：
[D. Gaur;K. Makino]
通讯作者：
D. Gaur;K. Makino
共 11 条
局所構造を利用した高速なアルゴリズムの開発
-
批准号：19K22841
-
项目类别：Grant-in-Aid for Challenging Research (Exploratory)
-
资助金额：$4.16万
-
财政年份：2019
-
负责人：牧野 和久
-
依托单位：
離散構造を有する列挙問題の解法に関する研究
-
批准号：15700013
-
项目类别：Grant-in-Aid for Young Scientists (B)
-
资助金额：$2.24万
-
财政年份：2003
-
负责人：牧野 和久
-
依托单位：
ネットワークフロー問題に対する高速かつ実用的アルゴリズムに関する研究
-
批准号：13780229
-
项目类别：Grant-in-Aid for Young Scientists (B)
-
资助金额：$1.6万
-
财政年份：2001
-
负责人：牧野 和久
-
依托单位：
現実データからの知識獲得問題に対するブール関数的アプローチ
-
批准号：11750059
-
项目类别：Grant-in-Aid for Encouragement of Young Scientists (A)
-
资助金额：$1.54万
-
财政年份：1999
-
负责人：牧野 和久
-
依托单位：
海外基金