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.