Partitioning a permutation into a minimum number of monotone subsequences is NP-hard. We extend this complexity result to minimum partitioning into k-modal subsequences; here unimodal is the special case k = 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)- 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.

On minimum k-modal partition of permutations

DI STEFANO, GABRIELE;
2008-01-01

Abstract

Partitioning a permutation into a minimum number of monotone subsequences is NP-hard. We extend this complexity result to minimum partitioning into k-modal subsequences; here unimodal is the special case k = 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)- 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/21565
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? ND
social impact