CCF-BSF: AF: Small: New Randomized Approaches in Approximation Algorithms

在现代世界，许多行业每天都通过解决大规模离散优化问题来做出关键决策，包括送货卡车的路线、飞机的计划设计和库存供应的物流决定。不幸的是，许多这样的问题在计算上很难精确地解决。近似算法的领域已经发展成为一种通用理论，用于开发和分析可以有效计算并给出近最优解的解决方案。该领域最成功的方法之一是：(1)使用易于求解的连续数学表征来表述手头的问题；(2)采用舍入法，将连续表征解转化为原问题的离散可行解。本项目旨在基于概率工具开发一种新的通用的、广泛适用的舍入方法。该项目的成功将有助于获得许多基本离散优化问题的新的和改进的求解方法。这个NSF-BSF合作项目的pi组成了一个和谐的团队，因为两个pi在算法研究方面有互补的能力。这将有助于实现该项目的主要目标之一，即扩大和维持美国和以色列在pi之间的科学合作。这个研究项目的另一个重要目标是包括学生，本科生和研究生，作为全面积极的参与者。将特别重视来自代表性不足群体的学生。pi计划通过将这项研究的结果整合到各个层次的跨学科课程活动中，包括计算机科学、应用数学和运筹学，来协助知识的传播。该项目旨在丰富近似算法领域的算法工具包，并表明基于离散布朗运动的新方法适用于广泛的np困难问题。特别强调了被认为是基本的优化问题，包括旅行商问题，最大切割和最大可满足性。任何对基本问题解决方案的新见解，比如上面提到的那些，可能会有更广泛的影响，因为这些问题构成了理论和实践中出现的许多离散优化问题的基本构建块。因此，本项目也旨在研究新开发的技术对这些问题的适用性。

In the modern world, many industries make every day crucial decisions by solving large scale discrete optimization problems including routing of delivery trucks, designing schedule of airplanes, and deciding on the logistics of inventory supplies. Unfortunately, many of these problems are computationally hard to solve exactly. The area of approximation algorithms has grown as a general theory to develop and analyze solutions that can be efficiently computed as well as give near-optimal solutions. One of the most successful approaches in this area has been to: (1) formulate the problem at hand using an easily solvable continuous mathematical characterization; and (2) applying a rounding method that converts the solution to the continuous characterization into a discrete feasible solution to the original problem. This project aims to develop a new generic and broadly applicable rounding method based on probabilistic tools. The success of the project will help obtain new and improved solution methods to many fundamental discrete optimization problems. The PIs of this collaborative NSF-BSF project compose a harmonious team as both PIs have complementary proficiencies in algorithmic research. This will contribute to achieving one of the primary goals of this project, which is to extend and maintain the US-Israeli scientific collaboration between the PIs. Another paramount goal of this research project is to include students, both undergraduate and graduate, as full active participants. A special emphasis will be given to students coming from under-represented groups. The PIs plan to assist the dissemination of knowledge by integrating results from this research into inter-disciplinary curriculum activities at all levels, spanning computer science, applied mathematics and operations research. The project aims to enrich the algorithmic toolkit in the area of approximation algorithms and show that a new approach based on discretized Brownian motion is applicable to a wide range of NP-hard problems. A special emphasis is given on optimization problems that are considered fundamental including traveling salesman problem, maximum cut and maximum satisfiability. Any new insight into the solution of fundamental problems, such as the ones mentioned above, is likely to have much wider implications as these problems form basic building blocks for numerous discrete optimization problems occurring in both theory and practice. Thus, this project also aims to study the applicability of the newly developed technique to such problems.