3
$\begingroup$

I am reading the following paper which presents a $(1-\epsilon)$-competitive online algorithm for the MaxMin (similar to the makespan) problem, defined as follows:

a set of requests are arriving in an online manner, wherein each request must be allocated to some provider before the next request is viewed. Each provider has a value for these requests, and our objective is to maximize the minimal value of requests assigned to any provider (subject to budgeting constraints).

In proving their result (Theorem 3 specifically) they make the assumption that the optimal offline solution to the problem is something like $\Omega(\log n / \varepsilon)$. Is this a standard result that I can find elsewhere, as no reasoning or proof is provided for this fact? Is this a necessary condition for the IID input setting? The proof of the competitive ratio is easy to follow but these assumptions are entirely unintuitive.

I assume that this result stems from some bin-packing result? Are there references that demonstrate these lower bounds in the IID, random order, or adversarial instances?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.