We introduce two new ideas: relative scalability and separable RMBM algorithms. A relatively scalable model allows any algorithm designed for an instance of arbitrary size N to be run on an instance of size N_0 (representing an available machine) with a factor O((N / N_0) f(N_0) ) increase in time; f(N_0) is independent of the simulated model size N. Relative scalability captures the ability of a given model to efficiently adapt to different model (or problem) sizes. The notion of separable RMBM algorithms places restrictions on the manner in which an RMBM may operate.
In this paper we prove that every separable RMBM algorithm is relatively scalable, thereby extending the use of many existing RMBM algorithms. We also show that unrestricted (non-separable) RMBM algorithms can also be scaled with a slightly higher overhead.