Career: Combinational Approximation Algorithms

职业：组合逼近算法

• 批准号: 9720664
• 负责人: Neal Young
• 金额: $ 20.64万
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-07-01 至 2001-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9720664&HistoricalAwards=false
• 关键词: Career; Combinational; Approximation; Algorithms

The grant supports research in the design and analysis of algorithms and improving the education infrastructure at the PI's department. The research focuses primarily on the following areas: (i) fast approximation algorithms for intractable (NP-hard) problems; (ii) fast approximation algorithms for very large problems requiring nearly linear- time solutions; (iii) competitive analysis of on-line caching problems. The style of research emphasizes the following: (i) general techniques for understanding, unifying, and simplifying large classes of algorithms; (ii) theoretical measures that are more realistic than either the standard worst-case or average-case models; (iii) empirical studies of new algorithms demonstrating their effectiveness. The education plan consists of the following. (i) Developing a training course for a core group of advanced undergraduates who will them lead small weekly discussion sections in the introductory courses. (This will simultaneously improve the introductory courses and provide a training ground for students to become educators.) (ii) Working with an outside evaluator to extensively evaluate the experience of majors and prospective majors. Two primary goals are to determine the effects of the aforementioned discussion sections (both on the students in the sections and those leading them), and to identify reasons for the low rate of retention of women undergraduates by the department.

该赠款支持算法设计和分析方面的研究以及改善 PI 部门的教育基础设施。 该研究主要集中在以下领域：（i）棘手（NP-hard）问题的快速逼近算法； (ii) 需要近线性时间解的非常大问题的快速逼近算法； (iii) 在线缓存问题的竞争分析。 研究风格强调以下内容：（i）理解、统一和简化大类算法的一般技术； (ii) 比标准最坏情况或平均情况模型更现实的理论测量； (iii) 新算法的实证研究证明其有效性。 The education plan consists of the following. (i) 为一组核心高年级本科生开发培训课程，由他们主持入门课程中的每周小型讨论部分。 （这将同时改进入门课程，并为学生成为教育工作者提供训练基地。）（ii）与外部评估员合作，广泛评估专业和未来专业的经验。 两个主要目标是确定上述讨论部分的影响（对这些部分的学生和领导者的影响），并找出该系女本科生保留率低的原因。