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$ Oct 9, 2017 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, 2017 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, 2017 at 1:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.