Algorithms for combinatorial optimization

这个项目的目的是为组合优化问题找到有效的算法。这些问题在理论和应用环境中都有出现。这类问题中最著名的是旅行商问题，但许多组合优化问题是通过美丽的理论和共同的思想联系在一起的。组合优化问题的特点是有一个离散的搜索空间。但挑战是这个空间太大，无法完全枚举，即使用非常快的计算机，因此需要智能算法和启发式算法。我们的目标是发现和分析这类算法。本建议集中在四个特定的组合问题上。它们是：1.寻找彩色线性规划可行性问题的算法。研究单调布尔函数的生成算法，并将其应用于新陈代谢网络的理解。用分布的方法分析定义在群上的组合目标函数。在图的谱上证明Grone-Merris猜想。除了它们的直接应用外，这些优秀问题的进展将有助于阐明优化中的关键问题。

The aim of this project is to find efficient algorithms for combinatorial optimization problems.   These problems arise in both theoretical and applied settings.  The most famous problem of this type is the Travelling Salesman Problem, but many combinatorial optimization problems are linked through beautiful theory and common ideas.  Combinatorial optimization problems are characterized by having a discrete search space.  The challenge is that this space is nevertheless too large to enumerate completely, even with very fast computers, so intelligent algorithms and heuristics are required.  Our aim is to find and analyze such algorithms.This proposal focuses on four particular combinatorial questions.  They are:1. Finding algorithms for the colourful linear programming feasibility problem.2. Studying algorithms for generating monotone boolean functions and applying these algorithms to understanding metabolic networks.3. Using a distributional approach to analyze combinatorial objective functions defined on groups.4. Proving the Grone-Merris conjecture on the spectrum of graphs.Besides their immediate application, progress on these nice problems will help to illuminate key issues in optimization.