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?
