A Case Study for Progressive Algorithms - An Investigation into Progressive Extraction of Intermediate Solutions for The Weighted Interval Scheduling Problem

Abstract

Asserted convergence characteristics shared by all serial algorithms have traditionally not been as prominent a measure of quality as time complexity has been. In instances relying on the exploration of large datasets, a convergence bound on interactively guided exploration approaches could act complementary to traditional time complexity, and constitute a alternative starting point for algorithm design. In an attempt to further explore the plausibility of this conjecture, a theoretical framework (Alewijnse, 2014) for convergence analysis through decomposition into consecutive intermediate computations is adopted, and its resulting intermediate solutions are used as a mean of empirical algorithm convergence analysis and categorization. Different scenarios related to the weighted interval scheduling problem are explored in this light, which is chosen primarily based on its documented compatibility with dynamic programming approaches. The result is presented as asymptotic upper bound functions on the convergence along with conjectures on upper bound hardness with respect to two different error functions, one adapted for stochastically and one for deterministically rooted algorithms.