Information-Based Complexity and Efficient Algorithms for Multivariate Problems
多元问题的基于信息的复杂性和高效算法
基本信息
- 批准号:0511994
- 负责人:
- 金额:$ 3.26万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2005
- 资助国家:美国
- 起止时间:2005-09-15 至 2006-08-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
ABSTRACT0511994Grzegorz WasilkowskiU of KentuckyThere are many important computational problems dealing with functions of very many (e.g., hundreds or thousands) variables. The classical algorithms work well when the number d of variables is small; however, they fail even for a modest number d since their costs increase exponentially with d. This is why the research will concentrate on tractability of multivariate problems. This will include identifying important problems that are tractable and deriving efficient algorithms for such problems. For problems that are not tractable in the most commonly used worst-case setting, average-case and randomized settings will be used to study their complexity. This will allow to avoid the worst-case intractability by the expense of weaker (random or probabilistic) assurances of the errors. In such cases, efficient randomized algorithms will be proposed, i.e., algorithms that, with a large probability, yield very accurate solutions at small (polynomial in d) cost. Recent observations by a number of researchers indicate that some important problems (e.g., in mathematical finance, physics, statistics, experimental design, etc.) have the so called small effective dimension. This is why a significant effort will be devoted to the complexity study of such problems and to constructions of polynomial-time algorithms. In summary, the research will enhance the understanding of the complexity of multivariate problems and their tractability. It will result in identifying new assumptions/properties that are both relevant to the problems in practice and yield efficient algorithms. Although not supported by this Grant, students will participate in the research.
有许多重要的计算问题处理非常多的函数(例如,数百或数千个)变量。 当变量的数量d很小时,经典算法工作得很好;然而,即使对于适度的数量d,它们也会失败,因为它们的成本随d呈指数增长。这就是为什么研究将集中在多变量问题的易处理性。这将包括确定重要的问题是易处理的,并得出有效的算法,这样的问题。对于在最常用的最差情况下不容易处理的问题,将使用平均情况和随机设置来研究其复杂性。这将允许避免最坏情况下的棘手性,其代价是错误的较弱(随机或概率)保证。在这种情况下,将提出有效的随机化算法,即,这些算法以很大的概率以很小的代价(d中的多项式)产生非常精确的解。许多研究人员最近的观察表明,一些重要问题(例如,数学金融学、物理学、统计学、实验设计等)具有所谓的小有效尺寸。这就是为什么一个显着的努力将致力于复杂性研究这些问题和建设的多项式时间算法。 总之,本研究将增进对多元问题复杂性及其易处理性的了解。它将导致识别与实践中的问题相关的新假设/属性,并产生有效的算法。虽然没有得到这项补助金的支持,学生将参与研究。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Grzegorz Wasilkowski其他文献
Grzegorz Wasilkowski的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Grzegorz Wasilkowski', 18)}}的其他基金
Efficient Algorithms for Multivariate Problems
多元问题的高效算法
- 批准号:
0609703 - 财政年份:2006
- 资助金额:
$ 3.26万 - 项目类别:
Standard Grant
Information-Based Complexity of Multivariate Problems
多元问题的基于信息的复杂性
- 批准号:
0095709 - 财政年份:2001
- 资助金额:
$ 3.26万 - 项目类别:
Standard Grant
Information-Based Complexity of Multivariate Problems
多元问题的基于信息的复杂性
- 批准号:
9729971 - 财政年份:1998
- 资助金额:
$ 3.26万 - 项目类别:
Standard Grant
相似国自然基金
Data-driven Recommendation System Construction of an Online Medical Platform Based on the Fusion of Information
- 批准号:
- 批准年份:2024
- 资助金额:万元
- 项目类别:外国青年学者研究基金项目
Exploring the Intrinsic Mechanisms of CEO Turnover and Market Reaction: An Explanation Based on Information Asymmetry
- 批准号:W2433169
- 批准年份:2024
- 资助金额:万元
- 项目类别:外国学者研究基金项目
Incentive and governance schenism study of corporate green washing behavior in China: Based on an integiated view of econfiguration of environmental authority and decoupling logic
- 批准号:
- 批准年份:2024
- 资助金额:万元
- 项目类别:外国学者研究基金项目
A study on prototype flexible multifunctional graphene foam-based sensing grid (柔性多功能石墨烯泡沫传感网格原型研究)
- 批准号:
- 批准年份:2020
- 资助金额:20 万元
- 项目类别:
基于tag-based单细胞转录组测序解析造血干细胞发育的可变剪接
- 批准号:81900115
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
应用Agent-Based-Model研究围术期单剂量地塞米松对手术切口愈合的影响及机制
- 批准号:81771933
- 批准年份:2017
- 资助金额:50.0 万元
- 项目类别:面上项目
Reality-based Interaction用户界面模型和评估方法研究
- 批准号:61170182
- 批准年份:2011
- 资助金额:57.0 万元
- 项目类别:面上项目
Multistage,haplotype and functional tests-based FCAR 基因和IgA肾病相关关系研究
- 批准号:30771013
- 批准年份:2007
- 资助金额:30.0 万元
- 项目类别:面上项目
差异蛋白质组技术结合Array-based CGH 寻找骨肉瘤分子标志物
- 批准号:30470665
- 批准年份:2004
- 资助金额:8.0 万元
- 项目类别:面上项目
GaN-based稀磁半导体材料与自旋电子共振隧穿器件的研究
- 批准号:60376005
- 批准年份:2003
- 资助金额:20.0 万元
- 项目类别:面上项目
相似海外基金
Information-Based Complexity Analysis and Optimal Methods for Saddle-Point Structured Optimization
基于信息的鞍点结构优化的复杂性分析和优化方法
- 批准号:
2053493 - 财政年份:2021
- 资助金额:
$ 3.26万 - 项目类别:
Continuing Grant
Complexity of High-Dimensional Statistical Models: An Information-Based Approach
高维统计模型的复杂性:基于信息的方法
- 批准号:
2015285 - 财政年份:2020
- 资助金额:
$ 3.26万 - 项目类别:
Continuing Grant
Digital Security by Design – Developing complexity based, un-crackable, high-efficiency mass information and data security products
设计数字安全 — 开发基于复杂性、不可破解、高效的海量信息和数据安全产品
- 批准号:
55355 - 财政年份:2020
- 资助金额:
$ 3.26万 - 项目类别:
Study
Information-Based Complexity Analysis for Large-Scale Nonlinear Optimization
大规模非线性优化的基于信息的复杂性分析
- 批准号:
1913006 - 财政年份:2019
- 资助金额:
$ 3.26万 - 项目类别:
Standard Grant
Information-Based Complexity of Multivariate Problems
多元问题的基于信息的复杂性
- 批准号:
0095709 - 财政年份:2001
- 资助金额:
$ 3.26万 - 项目类别:
Standard Grant
Theory and Applications of Information-Based Complexity
基于信息的复杂性理论与应用
- 批准号:
0097348 - 财政年份:2001
- 资助金额:
$ 3.26万 - 项目类别:
Standard Grant
Theory and Applications of Information-Based Complexity
基于信息的复杂性理论与应用
- 批准号:
9731858 - 财政年份:1998
- 资助金额:
$ 3.26万 - 项目类别:
Standard Grant
Information-Based Complexity of Multivariate Problems
多元问题的基于信息的复杂性
- 批准号:
9729971 - 财政年份:1998
- 资助金额:
$ 3.26万 - 项目类别:
Standard Grant
Average Case and Probabilistic Setting of Information-Based Complexity
基于信息的复杂性的平均情况和概率设置
- 批准号:
9420543 - 财政年份:1995
- 资助金额:
$ 3.26万 - 项目类别:
Continuing Grant
Mathematical Sciences: Complexity and Information Based Criteria for Model Selection
数学科学:模型选择的复杂性和基于信息的标准
- 批准号:
9210131 - 财政年份:1992
- 资助金额:
$ 3.26万 - 项目类别:
Standard Grant