I have been interested in this kind of "sorting with constraint" problem:

Given $n$ items $\{S_1 ,S_2 ,...S_n\}$ with corresponding weight $w_i ,i=1,2,...,n$, we want to sort these $n$ items (i.e. for $p_1 ,p_2 ,...,p_n$, we have a sequence that $S_i$ is at the $p_i$th position) with those constraints and goal below:

  1. Constraint1: for some $<i,j>$, there must have $p_i<p_j$
  2. Constraint2: for some $<i,k>$ that have constraint1, there could have some $j$ that cannot be $p_i<p_j<p_k$
  3. Goal: maximize $\sum_{1}^{n}p_iw_i$ (or some other loss function that we can call it "sort")

We can assume that there are $O(n)$ constraint1 and constrain2.

Here is my curiosity about whether there has been any research on this kind of problem, especially about:

  1. Obviously this problem is an $NP$ problem. Is it $NP-hard$ (which we can also be inferred that it is $NP-complete$)?
  2. If this is an $NP-complete$ problem, is there any approximation algorithm? In what ratio will this approximation algorithm performs?
  3. Consider a special condition: for $\{S_1 ,S_2 ,...S_n\}$, only O(1) items of them have non-zero weight. What will the complexity of this question--and the corresponding algorithm to solve it--be?

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.