# Existence of a pseudo-polynomial time algorithm for a counting problem.

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)) <= d_(pi(i)) for all k=1,...n.

Does there exists 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)).

This is an open question from an article published in 2009 at Operations Research Letters.

• Usually asking open problems is not really considered appropriate for MO; see the FAQ. That said, you might ask something like "what is the current state of knowledge about this problem?" Jul 29, 2010 at 14:57
• Should the RHS read $d_{\pi(k)}$ instead of $d_{\pi(i)}$? I also agree with Daniel, it seems inappropriate to ask an open question (especially such a recent one) on MO. Aug 27, 2010 at 13:00
• At the time I write this comment, the question has been edited and now makes no sense whatsoever Sep 13, 2010 at 15:40
• I've rolled the question back to it's previous version, which at least made sense. I don't know anything about this question, but it seems perfectly reasonable to ask whether any progress has been made on it. Sep 13, 2010 at 15:51
• Actually, David, could you further roll it back to the version by Gerry, which had the same content but had grammar corrected and used LaTeX?
– JBL
Sep 13, 2010 at 17:51