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.