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?



Your Answer

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