Given a set of numbers a = {a1, a2, ..., an}, the solution of an inverse sorting problem is another set of numbers x = {x1, x2, ..., xn}, which satisfy
min C(x-a)
s.t. x1 ≤ x2 ≤ ... xn
where C(x-a) can be thought of as (weighted) cost function, that is the cost to replace a with x. Applications of inverse sorting problems can be found in statistics, operations research, and image processing. This paper shows that for the following cost function with bound constraintsthe inverse sorting problem is solvable in O(n2) time. The paper seeks to solve the more general partial inverse sorting problem, where the inverse problem is formulated over J, a subset of I = {1, 2, ..., n}. In particular, it is shown that for three simple classes of cost functions, the partial inverse sorting problem can be solved by a combination of a sorting and an inverse sorting problem.It is known that inverse sorting problems are solvable in polynomial time. However, partial inverse sorting problems are generally of nondeterministic polynomial time (NP) complexity. Yet, the paper has confirmed that some partial inverse sorting problems can indeed be of only polynomial complexity.
