Algorithms in Parametric Optimization

参数计算处理输入是一个或多个参数的函数的问题。本研究将分析参数组合优化中的各种问题。这些问题可以被描述为搜索问题或构建问题。搜索问题涉及找到满足某些条件的参数值。构造问题涉及确定在规定范围内改变参数时所得到的所有最优解的集合。三个具体的研究领域是：有界树宽图上的参数最优子图问题；Lagranian松弛问题的有效组合算法实现构造和搜索算法，特别是与最小生成树相关的问题。一个共同的主题是算法模拟的概念，这是一种起源于最小比率优化领域的技术。这项工作将这个想法与其他算法，几何和图形理论工具相结合。

Parametric computing deals with problems where the input is a function of one or more parameters. This research will analyze various questions in parametric combinatorial optimization. These questions can be described as either search or construction problems. Search problems involve finding the parameter values for which certain conditions hold. Construction problems deal with determining the set of all the optimum solutions that are obtained when varying the parameters within a prescribed range. Three specific areas of research are: Parametric optimum subgraph problems on graphs of bounded treewidth; Efficient combinatorial algorithms for Lagranian relaxation problems; Implementation of construction and search algorithms, especially for problems related to minimum spanning trees. A common theme is the notion of algorithm simulation, a technique that originated in the field of minimum-ratio optimization. This work combines this idea with other algorithmic, geometrical, and graph-theoretical tools.