AF: Small: Geometry of Polynomials and Algorithm Design

AF：小：多项式几何与算法设计

• 批准号: 1812919
• 负责人: Amin Saberi
• 金额: $ 50万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-06-01 至 2023-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1812919&HistoricalAwards=false
• 关键词: AF; Small; Geometry; Polynomials; Algorithm

This project builds on sophisticated geometric and algebraic techniques to develop new algorithms for classic problems in algorithms design. One example of such problems is the Traveling Salesman Problem (TSP) which involves finding the shortest tour between a large number of destinations and has applications in logistics, planning, and vehicle routing. TSP is also used in chip manufacturing and as a subroutine in Genome sequencing. Another application of interest is online matching which is used by search engines or large online publishers for allocating advertisement space. In addition to the potential for impacting large industries like ride-sharing and online advertising, the proposed project aims to develop analytical tools that are generally applicable and can lead to the design of new algorithms for other applications. The project also includes an education and outreach component which incorporates design and broad dissemination of course materials on the subject. The project focuses on two types of questions: first, it studies the geometry of the roots of polynomials with an algorithmic lens, and aims to develop polynomial-time algorithms where the current theory only gives proof-of-existence. Second, it expands the scope and applicability of this theory by proposing new problems in combinatorics (like counting certain combinatorial objects) or discrete optimization (like the traveling salesman problem). In particular, the project includes the study of: (i) counting problems through the lens of polynomials and the study algorithms for counting and sampling problems by encoding problem instances using polynomials, (ii) the traveling salesman problem and the study of a new conjecture that can potentially lead to algorithms with better approximation ratio for this problem, (iii) online stochastic optimization where a new approach using Fourier analysis to approximate the optimum solution for this problem is proposed, and (iv) polynomial-time algorithms for finding roots of certain families of polynomials that can lead to faster construction of low-degree, high-connectivity graphs known as Ramanujan graphs.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.

该项目基于复杂的几何和代数技术，为算法设计中的经典问题开发新算法。这样的问题的一个例子是旅行推销员问题（TSP），它涉及到寻找大量目的地之间的最短行程，并在物流，规划和车辆路线的应用。TSP也用于芯片制造和基因组测序的子程序。另一个感兴趣的应用是在线匹配，其被搜索引擎或大型在线发布商用于分配广告空间。除了有可能影响拼车和在线广告等大型行业外，该项目还旨在开发普遍适用的分析工具，并为其他应用设计新的算法。该项目还包括一个教育和外联部分，其中包括设计和广泛传播关于这一主题的课程材料。该项目侧重于两类问题：第一，它研究了几何的根多项式的算法透镜，并旨在开发多项式时间算法，目前的理论只给出存在的证明。其次，它通过提出组合数学（如计算某些组合对象）或离散优化（如旅行推销员问题）中的新问题来扩展该理论的范围和适用性。具体而言，该项目包括研究：（i）通过多项式的透镜的计数问题和通过使用多项式对问题实例进行编码来研究用于计数和采样问题的算法，（ii）旅行商问题和对新猜想的研究，该新猜想可能导致对于该问题具有更好的近似比的算法，（iii）在线随机优化，其中提出了使用傅立叶分析来近似该问题的最优解的新方法，以及（iv）用于找到某些多项式族的根的多项式时间算法，其可以导致更快地构造低次多项式，该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Decentralized Matching in a Probabilistic Environment

概率环境中的分散匹配

• DOI: 10.1145/3465456.3467652
• 发表时间: 2021
• 期刊: EC 2021
• 作者: Jeloudar, Mobin Y.;Lo, Irene;Pollner, Tristan;Saberi, Amin
• 通讯作者: Saberi, Amin

Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities

• DOI: 10.1145/3465456.3467613
• 发表时间: 2021-02
• 期刊: Proceedings of the 22nd ACM Conference on Economics and Computation
• 作者: C. Papadimitriou;Tristan Pollner;A. Saberi;David Wajc

Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models

• DOI: 10.1145/3391403.3399513
• 发表时间: 2020-02
• 期刊: Proceedings of the 21st ACM Conference on Economics and Computation
• 作者: Tomer Ezra;M. Feldman;N. Gravin;Zhihao Gavin Tang