AF: Small: Algorithms for Matching, Markets, and Matching-Markets

AF：小：匹配、市场和匹配市场的算法

• 批准号: 1815901
• 负责人: Vijay Vazirani
• 金额: $ 50万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-06-01 至 2021-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1815901&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; Matching; Markets

This project will develop new foundations for three fundamental problem areas. All three problem areas, matching, markets, and matching markets have deep and rich algorithmic theories. All three have found numerous applications; for instance, applications of matching markets go all the way from assigning interns to hospitals, to assigning query keywords to advertisers in the multi-billion dollar online ads markets of search engine companies. The investigator has made foundational contributions to all three problem areas in the past, and has identified several new problems for this project. At the same time the investigator, who recently moved to the University of California, Irvine, has the mandate of helping propel its Theory Group to the next level. Towards this end, he will be recruiting a postdoc and high quality graduate students to increase the level and quality of research activity and will help revamp graduate and undergrad theory courses.On matching, the investigator recently solved a thirty-plus-year-old open problem by giving a fast parallel (NC) algorithm for finding a perfect matching in planar graphs, and has identified a number of important follow-up problems. Following up on his work giving complementary pivot equilibrium algorithms for several market models, he plans to analyze the smoothed complexity of this algorithm. Recent work of the investigator on the stable matching problem has yielded new structural results about relationships between the lattices of stable matchings of two "nearby" instances. This should help in developing efficient algorithms for finding solutions that are robust to errors introduced in the input.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该项目将为三个基本问题领域建立新的基础。 所有这三个问题领域，匹配，市场和匹配市场都有深刻而丰富的算法理论。这三种方法都有大量的应用;例如，匹配市场的应用从为医院分配实习生，到为搜索引擎公司数十亿美元的在线广告市场中的广告商分配查询关键字。调查员在过去对所有三个问题领域做出了基础性贡献，并为该项目确定了几个新问题。与此同时，这位最近搬到了加州大学欧文分校的调查员的任务是帮助推动其理论小组更上一层楼。为此，他将招募一名博士后和高素质的研究生，以提高研究活动的水平和质量，并将帮助改进研究生和本科生的理论课程。在匹配方面，研究人员最近解决了一个三十多年的开放问题，给出了一个快速并行（NC）算法，用于在平面图中找到完美匹配，并确定了一些重要的后续问题。继他的工作给出了几个市场模型的补充枢轴均衡算法，他计划分析该算法的平滑复杂性。最近的研究工作的稳定匹配问题已经产生了新的结构性结果之间的关系格的稳定匹配的两个“附近”的情况。这应该有助于开发有效的算法，以找到对输入中引入的错误具有鲁棒性的解决方案。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。