Computational Efficiency of Discrete Optimization Algorithms and Discrete Structures
Computational Efficiency of Discrete Optimization Algorithms and Discrete Structures
批准号:
10205217
负责人:
FUJISHIGE Satoru
金额:
$11.2万
依托单位:
依托单位国家:
日本
项目类别:
Grant-in-Aid for Scientific Research on Priority Areas (B)
财政年份:
1998
资助国家:
日本
项目状态:
已结题
起止时间:
1998 至 2000
中文摘要
本研究项目的目的是研究可有效解决的优化问题的潜在组合结构,并给出为这类组合优化问题设计有效算法的统一原则。我们这个项目的主要成果如下:我们成功地解决了设计最小化子模函数的组合(强)多项式算法的长期开放问题。这对离散优化领域产生了很大的影响。根据这一结果,我们还开发了子模函数最小化的全组合强多项式算法和双子模函数最小化的组合多项式时间算法,这是子模函数最小化的推广。第二组结果与网络优化问题有关。考虑无向网络中具有流量要求的源定位问题,设计了一种快速求解算法。采用参数化方法,提出了求解最小割问题的L_∞-极小极大反问题的有效算法,并得到了广义流边界多面体的所谓多基多面体的一个表征。作为第三组结果,我们开发了一种多项式时间算法,用于在分布式系统中寻找最优小圈子,我们成功地构建了伪多项式时间算法,用于枚举数据挖掘和学习理论领域中出现的超图的部分截线和多截线。除了这些结果外,我们还通过展示M^?-不可分商品匹配(或均衡)模型中相关集合函数的凹性和总量替代条件。
英文摘要
The objective of this research project is to examine the underlying combinatorial structure of optimization problems that can be solved efficiently, and to give a unifying principle for designing efficient algorithms for such a class of combinatorial optimization problems. Our major results of the project are the following.1. We succeeded in resolving the long-standing open problem of devising a combinatorial (strongly) polynomial algorithm for minimizing submodular functions. This gave great impact on the field of discrete optimization. Following this result, we also developed a fully combinatorial strongly polynomial algorithm for submodular function minimization, and a combinatorial polynomial-time algorithm for bisubmodular function minimization, a generalization of submodular function minimization.2. The second cluster of results are concerned with network optimization problems. We considered a source location problem with flow requirements in undirected networks and devised a fast algorithm for solving it. Also we developed an efficient algorithm for L_∞-minimax inverse problem of the minimum cut problem by taking a parametric approach, and we obtained a characterization of the so-called polybasic polyhedra that generalize the boundary polyhedra of generalized flows.3. As the third cluster of results, we developed a polynomial-time algorithm for finding an optimal coterie in distributed systems, and we succeeded in constructing pseudopolynomial-time algorithms for enumerating partial transversals and multiple transversals of hypergraphs arising in the fields of data mining and learning theory.Besides these results, we revealed the deep underlying relationship between the submodularity and the economic equilibrium analysis by showing the equivalence of the M^?-concavity of the relevant set function and the gross substitutes condition in the matching (or equilibrium) model with indivisible commodities.
期刊论文(140)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
Arata,K.: "Locating sources to meet flow demands in undirected networks"SWAT2000,LNCS. 1851. 300-313 (2000)
Arata,K.:“定位源以满足无向网络中的流量需求”SWAT2000,LNCS。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
Makino, K.: "Inner-core and outer-core functions of partially defined Boolean functions"Discrete Applied Mathematics. 96-97. 443-460 (1999)
Makino, K.:“部分定义的布尔函数的内核和外核函数”离散应用数学。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
Fujishige, S.: "A lexicographic algebraic theorem and its applications"Linear Algebra and its Applications. 279. 75-91 (1998)
Fujishige, S.:“字典代数定理及其应用”线性代数及其应用。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
Eiter, T.: "Bidual Horn functions and extensions"Discrete Applied Mathematics. 96-97. 55-88 (1999)
Eiter, T.:“双喇叭函数和扩展”离散应用数学。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
Boros, E.: "Finding essential attributes in binary data"Springer Lecture Notes in Computer Science(Proceedings of IDEAL2000(Leung,K.Sak.et al.eds.)). 1983. 133-138 (2000)
Boros, E.:“在二进制数据中查找基本属性”Springer 计算机科学讲义(IDEAL2000 论文集(Leung,K.Sak.et al.eds.))。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
共 130 条
Developments of the Fundamental Theory of Discrete Optimization andFast Algorithms Based on Submodular Structures
-
批准号:20310088
-
项目类别:Grant-in-Aid for Scientific Research (B)
-
资助金额:$12.56万
-
财政年份:2008
-
负责人:FUJISHIGE Satoru
-
依托单位:
Analysis of Large-scale Discrete Optimization Problems and Development of Efficient Algorithms Based on Submodularity Structures
-
批准号:16310111
-
项目类别:Grant-in-Aid for Scientific Research (B)
-
资助金额:$10.44万
-
财政年份:2004
-
负责人:FUJISHIGE Satoru
-
依托单位:
Fundamental Research on Fast Algorithms for Large-Scale Discrete Optimization Problems Based on Submodularity Structures
-
批准号:13480113
-
项目类别:Grant-in-Aid for Scientific Research (B)
-
资助金额:$4.61万
-
财政年份:2001
-
负责人:FUJISHIGE Satoru
-
依托单位:
Basic Studies on Submodular Structure of Large-scale Combinatorial Systems
-
批准号:10680429
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.11万
-
财政年份:1998
-
负责人:FUJISHIGE Satoru
-
依托单位:
Fundamental Studies on Large-Scale combinatorial Systems Based on Submodular Analysis
-
批准号:04832006
-
项目类别:Grant-in-Aid for General Scientific Research (C)
-
资助金额:$1.28万
-
财政年份:1992
-
负责人:FUJISHIGE Satoru
-
依托单位:
Analysis of Combinatorial Optimization Problems with Submodular Structures and Design of Efficient Algorithms
-
批准号:01540168
-
项目类别:Grant-in-Aid for General Scientific Research (C)
-
资助金额:$0.64万
-
财政年份:1989
-
负责人:FUJISHIGE Satoru
-
依托单位:
海外基金