patternMinor
Separating numbers with a minimal difference
Viewed 0 times
withnumbersdifferenceminimalseparating
Problem
Given is a positive integer integer $n$, and integers $a_1,b_1,\dots,a_n,b_n$ with $ a_i\leq b_i$ for each $i$. What is the complexity of deciding whether there exist integers $c_1,\dots,c_n$ such that $a_i\leq c_i\leq b_i$ for all $i$ and $|c_i-c_j|\geq 2$ for all $i,j$?
What can be observed is that a greedy algorithm, wherein we assume that $a_1\leq\dots\leq a_n$ and choose $c_i$ according to this order, does not necessarily work. For example, we may have $a_1=1, b_1=4, a_2=b_2=2$. Putting $c_1=1$ does not work (it leaves no room for $c_2$), but what works is putting $c_1=4$ and $c_2=2$. Is the problem perhaps NP-hard?
What can be observed is that a greedy algorithm, wherein we assume that $a_1\leq\dots\leq a_n$ and choose $c_i$ according to this order, does not necessarily work. For example, we may have $a_1=1, b_1=4, a_2=b_2=2$. Putting $c_1=1$ does not work (it leaves no room for $c_2$), but what works is putting $c_1=4$ and $c_2=2$. Is the problem perhaps NP-hard?
Solution
As shown in the previous answer, this problem can be modeled as a scheduling problem with release and due dates. However, Schrage's heuristic works only for the case $p_j=1$ (all processing times are $1$) or when release and due dates agree (i.e. there is an order such that $r_1\leq\cdots\leq r_n$ and $d_1\leq\cdots\leq d_n$).
For the case $p_j=p$ polynomial algorithms have been found by Simons (1978), Carlier (1981), and Garey et al. (1981), running in time $O(n^2\log n)$, $O(n^2\log n)$, and $O(n\log n)$, respectively.
The algorithm of Garey et al. schedules unit-time tasks, but allows arbitrary release and due dates. The above problem can be reduced to this setting by dividing all dates and processing times by $p$. The main idea of the algorithm is to find a set of forbidden regions where no task is allowed to start. They show that Schrage's heuristic when respecting forbidden regions finds a feasible schedule of minimal makespan. When constructing the forbidden regions their algorithm may also detect infeasibility.
To see how the algorithm works, first look at a simpler problem: schedule $n$ unit-time tasks between a release date $r$ and a deadline $d$ respecting forbidden regions $F=\bigcup_i (a_i,b_i)$, where each region $(a_i,b_i)$ is an open interval. (Note here we're not concerned with release and due dates of individual tasks.)
This problem can be solved by Backscheduling: define a sentinel starting time $s_{n+1}=d$, and for $i=n,n-1,\ldots,1$ set starting time $s_i$ to the latest time not later than $s_{i+1}-1$ that is not forbidden.
Write $B(r,d,n,F)$ for an application of Backscheduling for the above inputs, and define the return value as $s_1$, the latest possible starting date for scheduling the $n$ tasks. Now, if $B(r,d,n,F)
A straightforward implementation as above would take time $O(n^4)$. Garey et al. show (besides correctness) that by updating the times obtained by Backscheduling, joining overlapping forbidden regions, and making "forbidden" queries $O(1)$ time can be brought down to $O(n^2)$, and by using even better datastructures to $O(n\log n)$.
For the case $p_j=p$ polynomial algorithms have been found by Simons (1978), Carlier (1981), and Garey et al. (1981), running in time $O(n^2\log n)$, $O(n^2\log n)$, and $O(n\log n)$, respectively.
The algorithm of Garey et al. schedules unit-time tasks, but allows arbitrary release and due dates. The above problem can be reduced to this setting by dividing all dates and processing times by $p$. The main idea of the algorithm is to find a set of forbidden regions where no task is allowed to start. They show that Schrage's heuristic when respecting forbidden regions finds a feasible schedule of minimal makespan. When constructing the forbidden regions their algorithm may also detect infeasibility.
To see how the algorithm works, first look at a simpler problem: schedule $n$ unit-time tasks between a release date $r$ and a deadline $d$ respecting forbidden regions $F=\bigcup_i (a_i,b_i)$, where each region $(a_i,b_i)$ is an open interval. (Note here we're not concerned with release and due dates of individual tasks.)
This problem can be solved by Backscheduling: define a sentinel starting time $s_{n+1}=d$, and for $i=n,n-1,\ldots,1$ set starting time $s_i$ to the latest time not later than $s_{i+1}-1$ that is not forbidden.
Write $B(r,d,n,F)$ for an application of Backscheduling for the above inputs, and define the return value as $s_1$, the latest possible starting date for scheduling the $n$ tasks. Now, if $B(r,d,n,F)
- for tasks $i=n,n-1,\ldots,1$:
- $c=\min \{ B(r_i,d_j,n(r_i,d_j),F) \mid \forall j: d_j\geq d_i\}$
- if $c
- else if $r_i\leq c
A straightforward implementation as above would take time $O(n^4)$. Garey et al. show (besides correctness) that by updating the times obtained by Backscheduling, joining overlapping forbidden regions, and making "forbidden" queries $O(1)$ time can be brought down to $O(n^2)$, and by using even better datastructures to $O(n\log n)$.
Context
StackExchange Computer Science Q#111256, answer score: 5
Revisions (0)
No revisions yet.