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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.