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

AF：小：不确定环境和图分区的近似算法

• 批准号: 1319811
• 负责人: Anupam Gupta
• 金额: $ 39.99万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319811&HistoricalAwards=false
• 关键词: AF; Small; Approximation; Algorithms; Uncertain

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.

该项目侧重于近似和在线算法的一般领域的研究和教学活动。许多优化问题是棘手的，因此很自然地近似最优而不是计算精确解。有了这种见解，在过去的二十年里，近似算法已经有了巨大的发展，一些基本问题的近似性已经得到了很好的理解。除了对优化问题的计算复杂性的这种增强的理解之外，还提出了一组不断增加的技术和工具来解决新旧问题。鉴于这种情况，自然要采取双管齐下的研究计划：在继续解决一些长期存在的感兴趣的开放问题的同时，研究者将同时扩展新技术的范围，并且还研究试图捕获在实践中出现的丰富多样性的优化问题的更具表现力的模型和问题抽象。沿着这些路线，本研究的一个主要主题是研究如何在存在部分信息和不确定性的情况下解决优化问题，这是在实践中经常考虑的：仅基于各种事件在未来发生的概率，并且受到资源（时间/金钱）的约束，系统必须做出决策。在计算思维的精神，这项研究的目的是形式化的一些问题，以便有效的解决方案，可以找到更现实的模型比传统的最坏情况下的模型。这些问题的研究进展将推进国家的最先进的不确定性下的决策，一个领域躺在计算机科学，运筹学和决策理论的交叉点。这项研究也将有助于培养研究生和本科生。