AF: Small: Frameworks for Design and Analysis of Heuristics

我们需要计算机解决的许多任务的核心是一系列重要但困难的优化问题。这些问题可能很难以最佳方式解决，因此通常通过两种不同的方法来解决。 第一个是构造具有可证明的最坏情况近似保证的算法。 这种方法具有可证明保证的优点，但缺点是这些保证可能相当差。第二种方法是开发自然算法，并在基准问题上测试它们。这种方法的优点是产生的技术，可以很好地工作在实际环境中类似的基准，但缺点是，良好的性能所需的条件往往没有得到很好的理解。本项目旨在弥合这些方法之间的差距：为非最坏情况担保的分析开发新的理论基础，以及为正式合理的担保设计开发新的工具。 第一个是问题公式中隐含假设的分析。通常，优化问题中使用的目标函数是算法无法直接测量的目标的代理，因此实例已经需要具有这两者相关的属性。 这种关系通常没有明确说明，但可以潜在地提供算法可以使用的可用结构。 第二是分析自然条件对投入的影响，因为它们是如何构成的。 例如，如果给予算法的实例的某些部分是噪声测量的结果，则算法可以灵活地得到它们的精确值。 第三是开发快速方法来测试实例的“好”性，然后可以使用该方法为该实例选择合适的算法。最后，最后一个方向是算法的开发，这些算法在稳定和不稳定的实例上的性能之间提供平滑的过渡，并应用于隐私保护数据分析。

At the core of many of the tasks we need computers to solve lie a collection of important, though difficult, optimization problems. These problems can be hard to solve optimally, and as a result they have typically been attacked through two distinct approaches. The first is to construct algorithms with provable worst-case approximation guarantees. This approach has the advantage of provable guarantees but the disadvantage that these guarantees can be fairly poor. The second approach is to develop natural heuristics and to test them on benchmark problems. This approach has the advantage of producing techniques that can work well in practical settings similar to the benchmarks, but the disadvantage that the conditions needed for good performance are often not well understood. This project aims to bridge the gap between these approaches: to develop new theoretical foundations for the analysis of non-worst-case guarantees, as well as new tools for the design of formally-justified heuristics.Specifically, this project will pursue four main directions. The first is the analysis of implicit assumptions in problem formulations. Often the objective function used in an optimization problem is a proxy for a goal that cannot be directly measured by the algorithm, and thus the instance already needs to have the property that these two are related. This relation is often not explicitly stated and yet can potentially provide usable structure an algorithm can use. The second is analysis of natural conditions on inputs due to how they are constructed. For example, if certain parts of the instance given to the algorithm are the result of noisy measurements, then the algorithm can be flexible to their exact values. The third is development of fast methods to test the "niceness" of an instance, which can then be used in the selection of an appropriate algorithm for that instance. Finally, the last direction is the development of algorithms that provide a smooth transition between their performance on stable and unstable instances with applications to privacy-preserving data analysis.