Career: Combinational Approximation Algorithms

该补助金支持算法设计和分析的研究，并改善PI部门的教育基础设施。 研究主要集中在以下几个方面：（一）快速近似算法的棘手（NP难）的问题;（二）快速近似算法的非常大的问题，需要近线性时间的解决方案;（三）竞争分析的在线缓存问题。 研究风格强调以下几点：（i）理解、统一和简化大类算法的一般技术;（ii）比标准的最坏情况或平均情况模型更现实的理论度量;（iii）对新算法的实证研究，以证明其有效性。 教育计划包括以下内容。 (i)为核心的高年级本科生开发一门培训课程，他们将在入门课程中领导每周的小型讨论部分。 (This将同时改善入门课程，并为学生成为教育工作者提供培训基地。 (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.