New answers tagged approximation
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 ...
- 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 $...
- 5,266
Top 50 recent answers are included