Is algorithm which schedules tasks to machine and then for every time point in the makespan of machine does an operation considered pseudo-polynomial or quasi-polynomial? (if machine execute tasks from time 0 to 100 then it goes over every time point 0,1,2...100 separately and executes O(1) action) I would guess pseudo-polynomial as it is very similar to Dynamic programming but I'm not sure and I don't know how to validate it.
2
-
$\begingroup$ an algorithm can only be pseudo polynomial with respect to its input. So what is the input? If the input contains information for every time step it would be linear (cause the amount of steps taken is a multiple of the information given) but if the input just contains the number of steps, it would be pseudo polynomial because you execute $2^n$ for an input of size $n$ (if input number is given in binary) $\endgroup$– plshelpCommented Oct 24, 2020 at 1:50
-
$\begingroup$ @plshelp I am not entirely following the explanation. In the problem, tasks and machines are the inputs and every task has its execution time. The execution time is arbitrary though so the problem can have 1 machine 3 tasks and schedule of zillion time units when it comes to it, so there is no direct link to task number. But the instance is described in some file where time is mentioned so bigger the time execution for task, the bigger is instance defining it. Is this what you meant? Thank you $\endgroup$– eXPRESSCommented Oct 25, 2020 at 8:14
Add a comment
|