Suppose that we are given a sequences of $2N$ 'entities' (not numbers) with some total ordering defined among these entities. An example could be

$$\langle a\rangle=1<4<8<2<3<\cdots<2N \tag{GIVEN TO US}$$

However, we are not happy with this ordering because we want some other order relations to hold true namely:

1.) The set of entities $1$ to $N$ should satisfy a GIVEN ORDERING. An example could be:

$\langle c1\rangle=1<3<2<8<\cdots<N$.

2.) The set of entities $N+1$ to $2N$ should satisfy the ordering $\langle c2 \rangle $ obtained by adding $N$ to each entry in $\langle c1\rangle$.

$$\langle c2\rangle = \langle c1\rangle +N=N+1<N+3<N+2<N+8<\cdots<2N.$$

Statement of the problem: Construct a new sequence $<b>$, a total ordering on entities $1$ to $2N$ that must satisfy both $<c1>$ and $<c2>$ and be as "close" as possible to $<a>$. Note that the original sequence $<a>$ as given does not satisfy $<c1>$ and $<c2>$. Essentially approximate $<a>$ so that both of the given order constraints hold.

In theory, one could enumerate all possible sequences and pick the best one. I am instead looking for an efficient (could be sub optimal but maybe 'not so bad') way to do this problem. Any ideas on where to even start? Is there a branch of mathematics or theoretical computer science that deals with a problem of this sort and which will help me. I understand I haven't defined the notion of 'closeness'. One metric could be the number of disagreements which we need to minimize.


It seems to me that the problem is posed in a somewhat too general fashion. It is not difficult to prove that there are ways to define "satisfactory ordering" and "closeness" for which the problem of deciding if there exists a satisfactory ordering that is $\epsilon-$close to the original sequence is NP-complete. In fact, you can make even the approximation problem (if $\bar\epsilon$ is the actual minimum, you are allowed to err if posed the question with $\epsilon$ in the range $\bar\epsilon/K, \bar\epsilon K$ for any $K>0$) NP-complete!

Maybe you could give us a bit more structure to work with?

  • $\begingroup$ That is quite interesting. My background is not Algorithms or computer science though I have had some introductory exposition to theory of complexity and the idea of reductions to show NP completeness. For one, could you give an example of where the approximation problem is in fact NP-complete? Do you mean there are specific orderings and specific constraints where the problem becomes NP - complete? Let us say there is no structure in the sequences at all, would the task of finding an $\epsilon$-close sequence be NP complete? $\endgroup$ – Vinayak Suresh Jun 22 '18 at 17:58
  • $\begingroup$ Essentially, if there was no structure, I would be interested to be able to prove your claims. It would be great if you could provide such a proof or a push to the right direction by which I could try to prove it myself. $\endgroup$ – Vinayak Suresh Jun 22 '18 at 18:24
  • $\begingroup$ @VinayakSuresh The key idea is to be relatively loose on the ordering constraints (except to disqualify your initial sequence), but very picky and sneaky about the "closeness". Every way you can choose your $c_1$ and $c_2$ can be interpreted as a sequence of $\Omega(N)$ bits, that you can then read a T/F assignment to the set of boolean variables in a 3-CNF formula; define "closeness" as "how many clauses are satisfied" and you have the MAX-3SAT problem. $\endgroup$ – Anonymous Jun 22 '18 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.