几乎所有的组合优化问题都有很natural的integer programming(IP)版本... 这样一个常见的想法就是能否把整数优化问题很简单的转换为linear programming(LP...哈...老婆...)... 这个常见的转换叫做LP relaxation. 然后解决这个LP问题就可以就可以得到一个非整数解, 最后思考得到的这个解和IP的解差距有多大. 这个叫做一个问题的一个LP-relaxation integrality gap. 常常一个gap代表了一个approximation algorithm.
一个LP就是minimize cx, under the constraint Ax <= b. 这里A是matrix, b,c都是vectors. x是要求的.
有的LP relaxation的integrality gap = 1. 这类型的LP保证了找到一个最优顶点解就能保证解掉IP啊! (后面我们说的最优解都是顶点上的最优解...)
Read full article from 弄算法的人学点组合优化会很happy的...
No comments:
Post a Comment