A Case Study for Progressive Algorithms - An Investigation into Progressive Extraction of Intermediate Solutions for The Weighted Interval Scheduling Problem
Ladda ner
Typ
Examensarbete för masterexamen
Program
Publicerad
2020
Författare
Ringmark, Johannes
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
Weighted Interval Scheduling , Progressive Algorithms , Convergence Analysis , Worst-Case Analysis