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

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
Citation
Arkitekt (konstruktör)
Geografisk plats
Byggnad (typ)
Byggår
Modelltyp
Skala
Teknik / material
Index