Discrete algorithmics with applications to combinatorial optimization

计算机科学家研究的许多问题都可以用某种离散的、而不是连续的结构来建模。例如，图形是一种数学对象，它可以通过首先画一些点，然后在几对点之间画线来在一张纸上绘制。图中唯一相关的信息是哪些点对由一条线连接。许多类型的问题可以用图来建模，包括通信问题(例如，通过电话网络来电)、运输问题(例如，传送车辆的路由)、位置问题(例如，在人类基因组序列中找到基因的位置)。在许多这样的问题中，有一些方面需要优化。例如，对于运输工具，旅行时间应该最小化；对于基因定位，匹配的基因位点的数量应该是最大的。需要高效地找到最优解的算法。了解这些问题的基本离散结构通常会导致高效的算法。一旦了解了这些特性，就可以设计出高效的优化算法。这一建议涉及某些优化问题可以非常有效地解决的图，以及与这些优化问题相关的算法。

Many problems studied by computer scientists can be modelled by some discrete, as opposed to continuous, structure. For example, a graph is a mathematical object that can be drawn on a piece of paper by first drawing some dots and then drawing lines between some pairs of dots. The only relevant information in a graph is which dot pairs are joined by a line. Many kinds of problems can be modelled with graphs, including communication problems (e.g. routing calls through a phone network), transportation problems (e.g. routing delivery vehicles), location problems (e.g. finding the location of a gene in the human genome sequence). In many of these problems some aspect requires optimization. For example, with delivery vehicles travel time should be minimized; with gene location the number of matched gene sites should be maximized. Algorithms which find optimized solutions efficiently are desired. Understanding the underlying discrete structure of these problems often leads to efficient algorithms. Once these properties are understood, efficient optimization algorithms can be designed. This proposal concerns certain kinds of graphs for which some optimization problems can be solved very efficiently, and the algorithms associated with those optimization problems.