论文标题
分段线性有价值的约束满意度问题与固定数量的变量
Piecewise Linear Valued Constraint Satisfaction Problems with Fixed Number of Variables
论文作者
论文摘要
许多组合优化问题可以建模为有价值的约束满意度问题。在本文中，我们提出了一种多项式时间算法，该算法解决了固定数量变量和分段线性成本函数的有价值的约束满意度问题。我们的算法找到了分段线性函数的最小值，并决定它是否是适当的最小值。
Many combinatorial optimisation problems can be modelled as valued constraint satisfaction problems. In this paper, we present a polynomial-time algorithm solving the valued constraint satisfaction problem for a fixed number of variables and for piecewise linear cost functions. Our algorithm finds the infimum of a piecewise linear function and decides whether it is a proper minimum.
