0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Please make your question self-contained, so we don't have to click on another page to understand what you are asking. Thank you! $\endgroup$
    – D.W.
    Sep 17 at 5:48
  • $\begingroup$ Sure, thanks for the suggestion. I will add comprehensive problem definition by answering my own question below :). $\endgroup$
    – EddieG
    Sep 17 at 6:00
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Sep 17 at 6:10
  • $\begingroup$ @D.W., sure, done as suggested. $\endgroup$
    – EddieG
    Sep 17 at 6:25

1 Answer 1

0
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ But I wonder whether there is a better bound than $n$ $\endgroup$
    – EddieG
    Sep 18 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.