New answers tagged

0 votes

Weighted interval scheduling on K-identical machines --- approximation factor

Under the setting of the presented problem definition, if we sort the intervals by profit first instead of profit-to-duration first, I found an obvious approximation factor $n$ for this the other ...
EddieG's user avatar
  • 11
0 votes

Weighted interval scheduling with m-machines ---greedy solution with approximation factor

Unfortunately, the approximation guarantee of the algorithm is unbounded. For example, Consider a single machine and only two intervals: interval $I_1$ with profit $1$ and length $1$; and interval $...
Inuyasha Yagami's user avatar

Top 50 recent answers are included