1
$\begingroup$

I wonder if the following variant of the pinwheel scheduling is NP-Hard. Given a set of n radars S = {s$_1$, s$_2$... s$_n$} and a set of m areas A = {a$_1$, a$_2$, ... a$_m$}. Each radar s $\in$ S can cover a subset of A denoted by A(s) and in each time-unit, a radar can scan one area in A(s). The problem is, find a schedule for all radars to minimize a number t, such that for every t time-units, each area in A is scanned for at least once?

P.S. The original pinwheel scheduling problem: Given a radar s and a set of m areas A = {a$_1$, a$_2$, ... a$_m$}, s $\in$ S can cover all areas in A and in each time-unit, s can scan one area in A. Now given a hard constraint on the time between repetitions for each area a $\in$ A, denoted by R(a). The problem is, is there exists a schedule for s such that for each area a $\in$ A, a is scanned for at least once every R(a) time-units? This problem has been proved to be NP-Hard.

$\endgroup$
1
  • $\begingroup$ Sorry for the confusion, they are not the same. But the problem can be solved polynomially. Thank you very much! $\endgroup$
    – zqq
    Sep 5, 2021 at 8:52

1 Answer 1

1
$\begingroup$

The problem can be reduced to the maximum matching problem in polynomial time. Therefore, the problem is polynomial-time solvable.

Let $t$ be the same repeat time for each area $a_i$ in $A$. Note that in a feasible solution each area must get scanned at least once in the first $t$ time units; otherwise, there would be an area that will be scanned after $t$ time units - an infeasible solution. If a feasible schedule exists for the first $t$ time units, then we can repeat the same schedule for the further $t$ time units and so on.

Now, the new problem is: Is there any schedule for $n$ radars such that in initial $t$ time units, each area is scanned at least once. In other words, is there any schedule that uses $n$ radars at most $t$ times and covers all areas in $A$?

To solve the problem, create a bipartite graph $G = (U,V,E)$, where $U$ is the left partition such that each vertex corresponds to an area in $A$. The partition $V$ contains $n\cdot t$ vertices such that there are $t$ copies for every radar $s_i \in S$. For each such copy of $s_i$, there is an edge to area $a_j$ if $s_i$ covers $a_j$, i.e., $a_j \in A(s_i)$.

If the graph $G$ has a maximum matching of size $m$, then each area gets covered at least once. And, we only used any radar at most $t$ times, once per each time unit in $(1,\dotsc,t)$. Therefore, a feasible schedule exists. If the maximum matching size is $<$ $m$, then a feasible schedule does not exist.

$\endgroup$
5
  • $\begingroup$ The graph G = (U,V,E) has (m+nt) vertices. Thus, the time complexity of finding a maximum matching on G is O(|V|*|E|) and (m+nt) = |V|. As t is an input number, is this algorithm actually pseudo-polynomial? I know that if t >= mn, a feasible schedule always exists. So that t < mn. But what if there is no restriction for t? $\endgroup$
    – zqq
    Sep 5, 2021 at 13:11
  • $\begingroup$ @ybk That is an interesting point. In fact, when $t≥m$, a feasible solution always exists, and you do not need to solve the matching problem. You simply schedule one task in one time unit, and repeat that further in the same way. On the other hand, when $t<m$, the above matching algorithm becomes polynomial time, i.e., $O((mn)^3)$. Overall, the algorithm is polynomial time and not pseudo polynomial. $\endgroup$ Sep 5, 2021 at 18:54
  • $\begingroup$ Given a t, find whether a feasible schedule exists is polynomial. But the problem is to find the minimum t, this is a minimization problem. Except for trying every t from 1 until there exists a feasible solution, is there exists a faster solution to this minimization problem? $\endgroup$
    – zqq
    Sep 7, 2021 at 12:32
  • $\begingroup$ @ybk Binary search between 1 to m. Then, the multiplicative factor is just $\log m$ to the above algorithm. $\endgroup$ Sep 7, 2021 at 12:38
  • $\begingroup$ That is it. Thank you very much. $\endgroup$
    – zqq
    Sep 7, 2021 at 13:28

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.