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

Question

This is a follow-up for Weighted interval scheduling with m-machines ---greedy solution with approximation factor.

As suggested by @D.W., I will present the problem more comprehensively.

$\textbf{Problem Definition}$:
Given $n$ intervals and $K$ identical machines, each with a duration $t_{(\cdot)}$, fixed start time, fixed end time and a profit $p_{(\cdot)}$ (meaning that has to be processed by this time range, and the preprocessing time or its duration is its end time minus its start time). I would like to schedule these $n$ intervals on $K$ identical machines, so that their profit sum is maximized.

There are a few practical constraint besides the general form of the problem above:
$\cdot$ $t_{(\cdot)} \geq 1, t_{(\cdot)} \in N^{+},$
$\cdot$ $p_{(\cdot)} \geq 1, p_{(\cdot)} \in N^{+},$
$\cdot$ $n \leq KT$ ($T$ is the max end time for any given interval, such that $t_{(\cdot)} \leq T$).

$\textbf{My Greedy Solution}$:

1. sort the interval by profit-to-duration $\frac{p_{(\cdot)}}{t_{(\cdot)}}$ in decreasing order.
2. Select intervals in that order. For any given considered interval, if there is still an available machine left, select it; Otherwise, skip it. The selection is done when all intervals are considered.

$\textbf{My Question in This Post}$:
I would like to know the approximation factor by my greedy solution, something like $ALG_{Greedy} \geq \frac{OPT}{\alpha}$. Based on the previous discussion Weighted interval scheduling with m-machines ---greedy solution with approximation factor, I think the approximation factor $\alpha$ should be $T$. But I would like to derive a formal and comprehensive proof for it. If the approximation factor $\alpha$ is not $T$, I would like to know its correct approximation factor (parameterizing allowed) and the corresponding proof :).

---

Or is there any other efficient (approximation) algorithm with approximation guarantees? :)

Answer 1

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 greedy-like solution (number of intervals).