Algorithms for combinatorial optimization

点击翻译按钮获取中文摘要

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.