Queueing and glueing for optimal partitioning

Shin-Cheng Mu, Yu-Hsi Chiang, and Yu-Han Lyu. In the 21st ACM SIGPLAN International Conference on Functional Programming (ICFP 2016), Eijiro Sumii, editor, pages 158-167. ACM Press, Sep. 2016.
[Paper | Code]

The queueing-glueing algorithm is the nickname we give to an algorithmic pattern that provides amortised linear time solutions to a number of optimal list partition problems that have a peculiar property: at various moments we know that two of three candidate solutions could be optimal. The algorithm works by keeping a queue of lists, glueing them from one end, while chopping from the other end, hence the name. We give a formal derivation of the algorithm, and demonstrate it with several non-trivial examples.

Code accompanying this paper is available on GitHub:

Leave a Comment

Your email address will not be published. Required fields are marked *