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.