CAREER: Randomization in Graph Optimization Problems

职业：图优化问题中的随机化

• 批准号: 9624239
• 负责人: David Karger
• 金额: $ 20万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-06-01 至 2000-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9624239&HistoricalAwards=false
• 关键词: CAREER; Randomization; Graph; Optimization; Problems

This project focuses on the uses of randomization, with particular emphasis on graph algorithms. In particular, the problems to be ``tackled''(but not necessarily exactly solved) by the PI's randomized graphical optimization techniques include: (1) The maximum flow and minimum cut problems can be solved exactly, with the major objective being the design of faster, simpler and more practical algorithms for arriving at a correct answer; (2) Graph coloring and bisection, analysis of network reliability, and construction of low-cost high-connectivity networks, are extremely hard to solve exactly, with the major objective being to find efficient algorithms that give answers as close as possible to the elusive optimum. Implementation and testing of the algorithmic solutions is an integrated component of this project. The Integrated Educational Plan of this CAREER Grant includes the teaching, improvement and development of theoretical computer science courses, including: (1) Undergraduate algorithms course; (2) Undergraduate discrete mathematics course; (3) Graduate randomized algorithms course; (4) Undergraduate information retrieval and text databases.

这个项目的重点是随机化的使用，特别强调图形算法。 特别是要"解决“的问题，（1）最大流和最小割问题可以精确求解，主要目标是设计出更快、更简单和更实用的算法来得到正确的答案;（2）图的着色和二分法、网络可靠性的分析以及低成本高连通性网络的构建都很难精确地解决，主要目标是找到有效的算法，使答案尽可能接近难以捉摸的最优解。 算法解决方案的实施和测试是该项目的一个组成部分。 本CAREER Grant的综合教育计划包括理论计算机科学课程的教学，改进和开发，包括：（1）本科算法课程;（2）本科离散数学课程;（3）研究生随机算法课程;（4）本科信息检索和文本数据库。