课题基金 / 基金详情

AF: Small: Approximation Algorithms for Uncertain Environments and Graph Partitioning

AF: Small: Approximation Algorithms for Uncertain Environments and Graph Partitioning
AF:小:不确定环境和图分区的近似算法
批准号:
1319811
负责人:
Anupam Gupta
金额:
$39.99万
依托单位:
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2013
资助国家:
美国
项目状态:
已结题
起止时间:
2013-09-01 至 2017-08-31

项目摘要

项目成果

Anupam Gupta的其他基金

相似基金

相关文献

中文摘要
翻译
该项目侧重于近似和在线算法一般领域的研究和教学活动。许多优化问题都是难以处理的,所以很自然地要逼近最优解,而不是计算精确解。有了这样的认识,在过去的二十年里,近似算法有了巨大的发展,一些基本问题的近似性得到了很好的理解。除了提高对优化问题的计算复杂性的理解之外,还提出了一套不断增加的技术和工具来解决新旧问题。在这种情况下,采取双管齐下的研究计划是很自然的:在继续解决一些长期存在的开放性问题的同时,研究者将同时扩展新技术的范围,并研究更具表现力的模型和问题抽象,试图捕捉实践中出现的丰富多样的优化问题。沿着这些思路,本研究的一个主要主题是研究如何在部分信息存在的情况下解决优化问题,因此不确定性。这是在实践中经常考虑的事情:系统必须根据未来发生的各种事件的概率,并受限于资源(时间/金钱),做出决策。本着计算思维的精神,本研究旨在将这些问题形式化,以便找到比传统的最坏情况模型更现实的模型的有效解决方案。这些问题的研究进展将推动不确定性下决策的发展,这是一个计算机科学、运筹学和决策理论交叉的领域。这项研究也将有助于培养研究生和本科生。
英文摘要
This project focuses on research and teaching activities in the general area of approximation and online algorithms. Many optimization problems are intractable, so it is natural to approximate the optimum instead of computing an exact solution. With this insight, the past two decades have seen tremendous activity in approximation algorithms, to the point where the approximability of some basic problems is well-understood. In addition to this enhanced understanding of the computational complexity of optimization problems, an ever-increasing set of techniques and tools to attack problems old and new have been proposed. Given this situation, it is natural to take a two-pronged plan of research: while continuing to resolve some of the long-standing open problems of interest, the investigator will concurrently extend the scope of the new techniques, and also investigate more expressive models and problem abstractions that attempt to capture the rich diversity of optimization problems that arise in practice.Along these lines, a major theme of this research is to investigate how to solve optimization problems in the presence of partial information, and hence uncertainty. This is something often considered in practice: based only on probabilities of various events happening in the future, and subject to constraints on resources (time/money), a system must make decisions. In the spirit of computational thinking, this research is aimed at formalizing some of these problems so that efficient solutions can be found for more realistic models than the traditional worst-case model. Research progress on these questions will advance the state-of-the-art in decision-making under uncertainty, an area lying at the intersection of computer science, operations research, and decision theory. This research will also be instrumental in training of graduate and undergraduate students.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
  • 批准号:
    2422926
  • 项目类别:
    Continuing Grant
  • 资助金额:
    $60.0万
  • 财政年份:
    2024
  • 负责人:
    Anupam Gupta
  • 依托单位:
NSF: STOC 2024 Conference Student Travel Support
  • 批准号:
    2421504
  • 项目类别:
    Standard Grant
  • 资助金额:
    $1.5万
  • 财政年份:
    2024
  • 负责人:
    Anupam Gupta
  • 依托单位:
AF: Small: Towards New Relaxations for Online Algorithms
  • 批准号:
    2224718
  • 项目类别:
    Standard Grant
  • 资助金额:
    $60.0万
  • 财政年份:
    2022
  • 负责人:
    Anupam Gupta
  • 依托单位:
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
  • 批准号:
    1955785
  • 项目类别:
    Continuing Grant
  • 资助金额:
    $60.0万
  • 财政年份:
    2020
  • 负责人:
    Anupam Gupta
  • 依托单位:
国内基金
海外基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    --
  • 批准年份:
    2024
  • 负责人:
  • 依托单位:
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    10.0万元
  • 批准年份:
    2022
  • 负责人:
    张祥忠
  • 依托单位:
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 项目类别:
    面上项目
  • 资助金额:
    58.0万元
  • 批准年份:
    2019
  • 负责人:
    高学文
  • 依托单位: