3
$\begingroup$

Let $T={1,…,n}$ be a set of tasks. Each task $i$ has associated a non negative processing time $p_i$ and a deadline $d_i$. A feasible schedule of the tasks consists of a permutation of $n$ elements $\pi$, such that $\sum_{i=1}^k p_{\pi(i)} \le d_{\pi(i)}$ for all $k=1,\ldots,n$.

Does there exist a pseudo-polynomial time algorithm for computing the total number of feasible schedules?

A pseudo-polynomial time algorithm is an algorithm whose running time is bounded by a polynomial on the size of the input, given that the input is written in unary notation (2 = II, 3 = III). (e.g., the size of a number n in unary notation is $O(n)$, and not $O(\log(n)))$.

$\endgroup$

closed as not a real question by Suresh Venkat Oct 12 '10 at 5:32

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ please use latex in the future. See meta.cstheory.stackexchange.com/questions/225/… $\endgroup$ – Suresh Venkat Sep 10 '10 at 17:57
  • $\begingroup$ I feel dumb, but is it easy to find one feasible solution? I am asking this because if this is already strongly NP-complete, there is no chance that counting has a pseudo-polynomial-time algorithm unless P=NP. $\endgroup$ – Tsuyoshi Ito Sep 12 '10 at 19:07
  • 2
    $\begingroup$ Yes, one has just to order the tasks by their deadlines $d_i$ in increasing order. If such schedule doesn't work, no feasible schedule exists. $\endgroup$ – Pablo Sep 12 '10 at 19:45
  • 2
    $\begingroup$ Hi Pablo. This question is identical (see Tsuyoshi's post below) to a post on MO from Jul 29 by Gerardo. What's more interesting is that your email address appears to suggest that you are the author of the paper in which this problem is stated as being open. Are you aware of this earlier post, and are you indeed Gerardo Berbeglia ? $\endgroup$ – Suresh Venkat Sep 13 '10 at 22:49
  • $\begingroup$ closing, until the OP clarifies. $\endgroup$ – Suresh Venkat Oct 12 '10 at 5:31
5
$\begingroup$

Edit: It seems that the questioner knew that this was an open problem: https://mathoverflow.net/questions/33796/existence-of-a-pseudo-polynomial-time-algorithm-for-a-counting-problem. For what it is worth, it took me some time to find the paper, and I think that the time was wasted.


This question is stated as an open problem in [Ber09], where the same problem except that the numbers in the input are written in binary is shown to be #P-complete by a reduction from the counting version of the Subset Sum problem.

References

[Ber09] Gerardo Berbeglia. The counting complexity of a simple scheduling problem. Operations Research Letters, 37(5):365–367, Sept. 2009. http://dx.doi.org/10.1016/j.orl.2009.05.004

$\endgroup$
  • 1
    $\begingroup$ I think this is a problem. I'd like to hear what the OP has to say. $\endgroup$ – Suresh Venkat Sep 13 '10 at 22:23
1
$\begingroup$

A good reference for scheduling problems, including issues of complexity is:

Handbook of Scheduling, J. Y-T. Leung (ed), Chapman & Hall/CRC, 2004.

$\endgroup$