0
$\begingroup$

A question arising from a scheduling problem: I have a finite set $X$ with elements $x_i$ and some preorder $\leq$.
I have pairs $p_j$ of $x_i$ (i.e. $p_j$ = $(x_k, x_l)$) with the property that $x_k \leq x_l$.
I say that for two pairs $p, p'$ : $p \leq p'$ when for all $x \in p, x' \in p': x\leq x'$. I call two pairs $p = (x_1, x_2), p' = (x'_1, x'_2)$ unrelated if for no $x \in p$, $x' \in p'$ holds: $x \leq x'$ or $x' \leq x$.

Question: Does there always exists a total order $\leq'$ of $X$ which is compatible with $\leq$, with the property that $p \leq' p'$ or $p' \leq' p$, for all unrelated pairs $p, p'$?

To give an example:

$X = \{1,2,3,4,5\}$ , $p_1 = (1,2), p_2 = (3,5)$ and a partial order (preorder) $1 \leq 2, 3 \leq 5$. E.g. by topological sorting I can obtain a total order ($ 1 \leq 2 \leq 3 \leq 4 \leq 5$) which satisfies $p_1 \leq p_2$. However, tsort can also give me the total order ($1 \leq 3 \leq 2 \leq 4 \leq 5$), which does not satisfy $p_1 \leq p_2$ or $p2 \leq p1$ (here, $\leq$ refers to the corresponding total orders).

The relation to a specific scheduling problem is that I have undetermined times $x_i$ at which I acquire or release a resource. To avoid deadlocks, the pairs of (acquisition, release) must not overlap.

(In the actual problem, some time $x_i$ can occur in multiple such pairs, but that's another problem not considered here).

UPDATE

I think I found at least some idea, yet not sure if it is correct: The graph below shows the general structure of such a preorder (which we now treat as a directed acyclic graph): Given two such pairs $(x, x')$ and $(y, y')$, there is a path from $x$ to $x'$ (and from $y$ to $y'$). There may be nodes in-between, and edges connecting to that path. However, by our assumption that the pairs are unrelated, none of the incoming or outgoing edges in the section $x \to x'$ can reach $y$ or $y'$. We can now start constructing a topological sort. Without loss of generality, we reach $x$ as the first node of all pairs which we consider (which is not necessarily unique, but that does not matter). Because there are no edges between $x$ and $x'$ which connect from/to another point $y$ from another pair, we can continue our topological sort until we reach $x'$. Then, the pair $(x, x')$ is "compact" in our final order, that is, will have a $\leq'$ relation to all other pairs (because no point of any other reservation is between $x$ and $x'$, by construction of the total order $\leq'$). We can repeat this procedure every time we reach the first point of such a pair.

Is there any flaw in this argument?

Typical graph structure

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! This sounds to me like a question about math rather than about computer science. Is there a reason I'm missing why it is best answered by a computer scientist rather than a mathematician, or why it is of particular interest to computer scientists? $\endgroup$ – D.W. Feb 4 at 17:06
  • $\begingroup$ Thanks for the welcome :) I was thinking of putting this to cstheory.stackexchange.com (maybe I'll migrate it if I figure out how). The reason why I thought this would be interesting is that it is related to scheduling: p and p' are reservations (with x1, x2 start / end of a reservation) for some resources, and if p < p' or p' < p there is no conflict (deadlock). The "preorder" comes from different resources. I just abstracted all this scheduling stuff away. $\endgroup$ – Moritz Feb 4 at 18:01
  • $\begingroup$ Cool, can you edit to add that motivation? Don't add "EDIT" - we have revision history, so just make it read well for someone who encounters this for the first time. Thanks for your response! $\endgroup$ – D.W. Feb 4 at 18:07
1
$\begingroup$

I think you mean partial order, as if you only have a preorder then there might not even exist any total order that is compatible with it.


Your argument seems to be missing something about how you construct your topological sort, as it implies that any topological sort works, which you disproved yourself. In your example $x,y,x',y'$ could be a topological sort.

Here is an other attempt at a proof:


Let $\leq$ denote a partial order on $X$. I claim there exists a total order $\leq'$ compatible with $\leq$ such that the following never occurs: $a\leq'\alpha\leq'b$ where $a \leq b$, and $\alpha$ is incomparable to both $a$ and $b$. (Note that when I say comparable/incomparable I always mean with respect to $\leq$)

To see this choose a compatible total order $\leq'$ with the least amount of such "bad" pairs $(a\leq b)$. Suppose that this amount is non-zero and let $(a\leq b)$ be such a pair with smallest $a$ (with respect to $\leq'$). Let $\alpha_1 \leq' \alpha_2 \leq'\ldots\leq'\alpha_k$ denote all elements between $a$ and $b$ which are incomparable to both $a$ and $b$.

Now create a new total order $\leq^*$ from $\leq'$ by moving all $\alpha_i$'s right in front of $a$ to get $\alpha_1 \leq^* \alpha_2 \leq^*\ldots\leq^*\alpha_k\leq^*a$, the rest remaining unchanged. Notice that this is still compatible with $\leq$, as the only thing that could have gone wrong is that there was some $a\leq c \leq \alpha_i$ but this is impossible as $a$ and $\alpha_i$ are incomparable.

Notice also that, because all elements between $a$ and $b$ (with respect to $\leq^*$) are now comparable to $b$, we have created no "bad" pair $(\alpha_i\leq x)$ with $a\leq^* x \leq^* b$, otherwise we would have $\alpha_i\leq x \leq b$ meaning that $\alpha_i$ and $b$ are comparable. And we have created no "bad" pair $(x\leq a)$, otherwise $(x\leq b)$ would have been a bad pair to start with, contradicting our choice of $a$. Any other type of "bad" pair we created must have already existed previously.

Because $(a,b)$ is no longer a bad pair, $\leq^*$ has strictly less bad pairs than $\leq'$, which is impossible by definition of $\leq'$. Thus, $\leq'$ had no bad pairs to start with.

It is easy to show from here that $\leq'$ meets your requirements.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Seems 100% sound to me $\endgroup$ – Moritz Feb 5 at 6:38
0
$\begingroup$

It seems you consider intervals totally contained in others or disjoint only. Intervals can overlap partially, e.g. $[1, 3), [2, 4)$.

Scheduling in the general case (any value function for tasks, where you look for the maximum sum of values) is hard (the corresponding decision problem is NP-complete). There is copious literature on algorithms to solve this, typically using dynamic prigramming. The special case where the value is the same for each task can be solved by a greedy algorithm: program the task that ends earliest, eliminate tasks conflicting with it, and repeat.

| cite | improve this answer | |
$\endgroup$

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.