[EM] A monotonic proportional multiwinner method

Kristofer Munsterhjelm 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 mailing list