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/.
----
Election-Methods mailing list - see http://electorama.com/em for list info
