Loading...
Please wait, while we are loading the content...
Similar Documents
Short note on complexity and approximability of unimodal partitions of permutations (2004)
| Content Provider | CiteSeerX |
|---|---|
| Author | Stefano, Gabriele Di Zimmermann, Uwe T. |
| Abstract | We extend results of Wagner [8] and Fomin, Kratsch, and Novelle [6] on monotone partitions of permutations. We show that partitioning a sequence of distinct integers into unimodal subsequences is NP-complete and that a minimum unimodal partition is 3.42-approximable in polynomial time. 1 |
| File Format | |
| Publisher Date | 2004-01-01 |
| Access Restriction | Open |
| Subject Keyword | Unimodal Partition Short Note Unimodal Subsequence Monotone Partition Polynomial Time Distinct Integer Minimum Unimodal Partition |
| Content Type | Text |
