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.