[EM] A computationally feasible method (algorithmic redistricting)

[Kristofer Munsterhjelm]

Juho wrote:
> The traditional algorithm complexity research covers usually only 
> finding perfect/optimal result. I'm particularly interested in how the 
> value of the result increases as a function of time. It is possible that 
> even if it would take 100 years to guarantee that one has found the best 
> solution, it is possible that five minutes would be enough to find a 99% 
> good solution with 99% probability.
> 
> Decrypting ciphered text does not work this way (the results could still 
> be worth 0 after 10 years with good probability). But solving e.g. 
> CPO-STV may well behave more this way (probably one can find an 80% good 
> solution in one minute). Good performance in value/time means that 
> general optimization works (and the method can be considered feasible in 
> practice despite of being theoretically infeasible).

In computer science, you have something called polynomial time 
approximation schemes (or PTASes). If a problem has a PTAS, then it's 
possible to get within a factor e (epsilon) of being optimal, in 
polynomial time, where the solution time for a fixed e is polynomial 
(but need not be polynomial with respect to e). An approximation scheme 
that runs in time n^(1 + 1/e) is a PTAS, although it's not polynomial 
with respect to e.

The equivalent group for probabilistic algorithms is called "polynomial 
time randomized approximation schemes", and give a result within e of 
optimal in polynomial time /with high probability/.