Career: Combinational Approximation Algorithms

这笔赠款支持在算法的设计和分析方面的研究，以及改善PI部门的教育基础设施。研究主要集中在以下几个方面：(I)难解(NP-Hard)问题的快速逼近算法；(Ii)需要近线性时间解的大型问题的快速逼近算法；(Iii)在线缓存问题的竞争分析。研究风格强调如下：(I)理解、统一和简化大类算法的一般技术；(Ii)比标准最坏情况或平均情况模型更现实的理论测量；(Iii)对新算法的实证研究，以证明其有效性。教育计划由以下几部分组成。(I)为高级本科生核心群体开发一个培训课程，他们将在入门课程中领导每周的小讨论部分。(这将同时改进入门课程，并为学生成为教育工作者提供培训场所。)(Ii)与外部评估员合作，广泛评估专业和未来专业的经验。两个主要目标是确定上述讨论部分的影响(包括对这些部分的学生和领导这些部分的学生的影响)，以及找出该系留住女本科生比例较低的原因。

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.