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

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? :)

• Please make your question self-contained, so we don't have to click on another page to understand what you are asking. Thank you!
– D.W.
Sep 17 at 5:48
• Sure, thanks for the suggestion. I will add comprehensive problem definition by answering my own question below :). Sep 17 at 6:00
• Please don't put the problem definition in the answer. Instead, it would be better to edit the question so it states a self-contained, answerable question. We are looking to build up a library of knowledge that will be useful for others, in the form of questions and answers, so we have certain expectations about the format.
– D.W.
Sep 17 at 6:10
• @D.W., sure, done as suggested. Sep 17 at 6:25

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).
• But I wonder whether there is a better bound than $n$ Sep 18 at 1:22