[EM] A monotonic proportional multiwinner method
km-elmet at broadpark.no
Fri Mar 12 10:42:16 PST 2010
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.
More information about the Election-Methods