Practical Competitive Analysis (Computer Science)

点击翻译按钮获取中文摘要

An algorithm is said to be online if it receives input in a sequence of requests, and must service each request as it arrives without any knowledge of the future. Many fundamental problems in computer science are inherently online. A commonly used method of analyzing online algorithms is competitive analysis, where the performance of the online algorithm is compared to the performance of the optimal clairvoyant algorithm. There are several practical problems with the usual style of competitive analysis, including the use of worst care adversary, the lack of attention to implementation efficiency, and the lack of empirical evidence concerning the performance of competitive algorithms. The goal of this project is to help bridge the gap between theory and practice in this rapidly growing area by developing efficient, adaptive algorithms for fundamental systems problems. These algorithms should perform well against a statistical adversary, and will be empirically evaluated. Interactive activities include: participation in the mentoring and outreach programs of Women in Engineering; development of and experimentation with software for teaching math to girls, via collaboration with Professor Steve Tanimoto's research group at the University of Washington (UW) and with Professor Maria Klawe's E- GEMS project at the University of British Columbia; and teaching an undergraduate course and seminars in computer science and undertaking joint research with other members of the computer science faculty at UW.