Warren Smith wrote:
if you can find a polytime algorithm to find a violated constraint whenever one exists, then I can find a polytime algorithm to solve the linear program. (Proof: known result about "ellipsoid method.")
Would that help in solving the integer program, or only its linear relaxation? 0-1 integer programming is NP-complete in general whereas linear programming is not, so I guess not.
If we're to solve it in polytime, we have to make use of some additional structure of the problem, but I don't know what that structure is or if it is even sufficient. More investigation would be required.
---- Election-Methods mailing list - see http://electorama.com/em for list info
