ICFP 2016 (series) / Research Papers /
Queueing and Glueing for Optimal Partitioning (Functional Pearl)
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.
Mon 19 SepDisplayed time zone: Osaka, Sapporo, Tokyo change
Mon 19 Sep
Displayed time zone: Osaka, Sapporo, Tokyo change
17:00 - 18:15 | |||
17:00 25mTalk | Compact Bit Encoding Schemes for Simply-Typed Lambda-Terms Research Papers Kotaro Takeda University of Tokyo, Japan, Naoki Kobayashi University of Tokyo, Japan, Kazuya Yaguchi Tohoku University, Japan, Ayumi Shinohara Tohoku University, Japan DOI | ||
17:25 25mTalk | Queueing and Glueing for Optimal Partitioning (Functional Pearl) Research Papers Shin-Cheng Mu Academia Sinica, Taiwan, Yu-Hsi Chiang National Taiwan University, Taiwan, Yu-Han Lyu Dartmouth College, USA DOI | ||
17:50 25mTalk | All Sorts of Permutations (Functional Pearl) Research Papers Jan Christiansen Flensburg University of Applied Sciences, Germany, Nikita Danilenko University of Kiel, Germany, Sandra Dylus University of Kiel, Germany DOI | ||