论文标题
优化多肌功能
Optimizing Polymatroid Functions
论文作者
论文摘要
我们考虑一类优化问题，这些问题涉及确定特定类中功能可以达到差异约束的最大值。我们表明，基于二元性和预测的特定线性编程技术可用于重新定性一些结构性结果，这些结构结果以前使用更多的临时方法建立。然后，我们证明该技术可用于获得某种简单差异约束的多项式时间算法。最后，我们给出了下限结果，表明这些结果的某些可能扩展可能是不可行的。
We consider a class of optimization problems that involve determining the maximum value that a function in a particular class can attain subject to a collection of difference constraints. We show that a particular linear programming technique, based on duality and projections, can be used to rederive some structural results that were previously established using more ad hoc methods. We then show that this technique can be used to obtain a polynomial-time algorithm for a certain type of simple difference constraints. Finally we give lower bound results that show that certain possible extensions of these results are probably not feasible.
