On minimum k-modal partitions of permutations

Partitioning a permutation into a minimum number of monotone subsequences is NPNP-hard. We extend this complexity result to minimum partitioning into k  -modal subsequences; here unimodal is the special case k=1k=1. Based on a network flow interpretation we formulate both, the monotone and the k  -modal version, as mixed integer programs. This is the first proposal to obtain provably optimal partitions of permutations. LP rounding gives a 2-approximation for minimum monotone partitions and a (k+1)(k+1)-approximation for minimum (upper) k-modal partitions. For the online problem, in which the permutation becomes known to an algorithm sequentially, we derive a logarithmic lower bound on the competitive ratio for minimum monotone partitions, and we analyze two (bin packing) online algorithms. These immediately apply to online cocoloring of permutation graphs.