Given a permutation $\sigma\in S_n$ and a positive integer $k$, find the largest integer $0\le m\le n$ such that there exist a subset $I\subseteq [n], |I|=m$, satisfying that the restriction of $\sigma$ on $I$ has inversion number bounded by $k$. (Here the restriction of a permutation is defined in the very natural way that you can imagine.)

I wonder if the above problem was studied before? Any ideas/previous results on algorithm/approximation algorithm/hardness result are appreciated.

  • $\begingroup$ When k=0 this is just finding a longest increasing subsequence which is easy. In general I'm less sure. $\endgroup$ – Artimis Fowl Oct 9 '17 at 23:28
  • $\begingroup$ @Artimis Fowl Yes you are right! The case k=0 can be solved via dynamic programming. Actually this also gives a trivial k-additive approximation algorithm to the general problem, but I do not know of any better approximation. $\endgroup$ – Zihan Tan Oct 10 '17 at 3:33
  • $\begingroup$ Actually this problem is equivalent to finding the sparsest t-subset in permutation graph. To the best of my knowledge, there is no known non-trivial approximation algorithm to it yet. $\endgroup$ – Zihan Tan Oct 11 '17 at 1:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.