AF: Small: Algorithms March on through Continuous and Combinatorial Methods

AF：小：算法通过连续和组合方法前进

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

This project will continue the exploration of the combination of continuous and combinatorial methods for algorithm design. Continuous methods are similar to high school calculus, where the notion of the derivative of a function is used to find exact, optimal solutions to problems such as the shortest way to swim across a moving creek. An example of a combinatorial method is multiplication, where one follows a simple step-by-step method (algorithm) to compute a product. In optimization, both techniques have been used to compute the optimal solutions for many problems. One such example is airline scheduling, which combines aspects of staff scheduling, route planning, and even profit maximization. Recently, a breakthrough in optimization has combined these approaches at a lower level. Combinatorial problems (e.g., scheduling staff) are translated to continuous ones (e.g., multi-variable real number function optimization). Combinatorial structure is re-imposed, based on understanding of the original problem, to speed up calculus-based methods. This has led to remarkable breakthroughs in producing theoretically fast algorithms for basic problems such as the solution of linear systems. Such algorithms are applicable, for example, in climate modelling, weather predictions, and oil exploration. The technique is also making exciting inroads into the area of linear programming, which is used, for example, in the previously mentioned application of airline scheduling.In this project, the idea of "pre-conditioning" a function is studied to allow for continuous ("calculus-based") optimization techniques to run faster. One example is producing an interpolation of a function on a line. The value of the function is specified at particular points, and one wishes to produce the "smoothest" interpolation on the many points on the line. This can be viewed as a multi-variable problem where the value of each point is a variable, but one loses the structure of the line. Re-incorporating this structure into the multi-variable optimization techniques produces very fast algorithms. This simple intuition has been applied to more complicated situations, ranging to very general problems in convex optimization, and is yielding fruit. This project will attempt to further understand and extend the applicability of these techniques.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.

该项目将继续探索算法设计的连续和组合方法的组合。连续方法类似于高中微积分，其中函数的导数的概念用于找到精确的，最佳的解决方案，以解决诸如在移动小溪中游泳的最短方法。组合方法的一个示例是乘法，其中一个遵循简单的逐步方法（算法）来计算产品。在优化中，这两种技术均已用于计算许多问题的最佳解决方案。这样的例子是航空公司计划，该计划结合了员工计划，路线规划甚至最大化的各个方面。最近，优化的突破已将这些方法与较低级别结合在一起。组合问题（例如，调度人员）被转化为连续问题（例如，多变量的实际数量函数优化）。基于对原始问题的理解，重新启动了组合结构，以加快基于微积分的方法。这导致了为基本问题（例如线性系统解决方案）产生理论上快速算法的显着突破。这种算法适用于例如气候建模，天气预测和石油勘探。该技术还引起了线性编程领域的激动人心的侵害，例如，在该项目的航空公司调度的应用中，使用了该函数的概念，研究了“预先调节”一个函数的想法，以允许连续（基于calculus'）优化技术运行更快。一个示例是在线上产生函数的插值。该函数的值在特定点指定，并且希望在线上的许多点上产生“最平稳”的插值。这可以看作是一个多变量的问题，其中每个点的值是一个变量，但是一个人失去了线的结构。将这种结构重新组合到多变量优化技术中会产生非常快速的算法。这种简单的直觉已应用于更复杂的情况，范围为凸优化的非常普遍的问题，并且正在产生水果。该项目将试图进一步理解和扩展这些技术的适用性。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的评论标准来评估值得支持的。

项目成果

A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits

有限状态马尔可夫链的Hoeffding不等式及其在马尔可夫强盗中的应用

• DOI: 10.1109/isit44484.2020.9173931
• 发表时间: 2020
• 期刊: 2020 IEEE International Symposium on Information Theory (ISIT
• 作者: Moulos, Vrettos

Universal Algorithms for Clustering

通用聚类算法

• 发表时间: 2021
• 期刊: Leibniz international proceedings in informatics
• 作者: Bruce Maggs, Arun Ganesh

High-Dimensional Expanders from Expanders

来自 Expanders 的高维扩展器

• DOI: 10.4230/lipics.itcs.2020.12
• 发表时间: 2020
• 期刊: Leibniz international proceedings in informatics
• 作者: Liu, Siqui;Mohanty, Sidhanth;Yang, Elizabeth
• 通讯作者: Yang, Elizabeth

Privately Answering Counting Queries with Generalized Gaussian Mechanisms

使用广义高斯机制私下回答计数查询

• DOI: 10.4230/lipics.forc.2021.1
• 发表时间: 2021
• 期刊: Leibniz international proceedings in informatics
• 作者: Ganesh, Arun;Zhao, Jiazheng
• 通讯作者: Zhao, Jiazheng

Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems

将平面图嵌入到低树宽图中，并应用于度量问题的高效近似方案

• DOI: 10.1137/1.9781611975482.66
• 发表时间: 2019
• 期刊: Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete Algorithms
• 作者: Eli Fox-Epstein, Eli Klein