The decomposition method is currently one of the major methods for
solving the convex quadratic optimization problems being associated
with Support Vector Machines (SVM-optimization). A key issue
in this approach is the policy for working set selection. We would
like to find policies that realize (as good as possible) three goals
simultaneously: ``(fast) convergence to an optimal solution'',
``efficient procedures for working set selection'', and ``high degree
of generality'' (including typical variants of SVM-optimization as
special cases). In this paper, we study a general policy for working
set selection that has been proposed (2004) and further analyzed (2005)
by List and Simon. It is known that it efficiently approaches
feasible solutions of minimum cost for any convex quadratic optimization
problem. Here, we investigate its computational complexity when it is used
for SVM-optimization. It turns out that, for variable size of the working
set, the general policy poses an NP-hard working set selection problem.
But a slight variation of it (sharing the convergence properties with
the original policy) can be solved in polynomial time. For working sets
of fixed size 2, the situation is even better. In this case, the general
policy coincides with the ``rate certifying pair approach'' (introduced
by Hush and Scovel). We show that maximum rate certifying pairs can be
found in linear time, which leads to a quite efficient decomposition
method with a polynomial convergence rate for SVM-optimization.
