As we all know, in offline problems it is common practice to calculate the integrality gap to get some bound on the approximation ratio of the integral solution.

Now this gap ($IG:=\frac{OPT_{frac}}{OPT_{int}}$) relies on the fact that we can compute the fractional optimum by just solving the relaxed linear program of the problem.

In Online Algorithms there is no LP which can be relaxed and solved. Well there technically is but we can't solve it like we do in the offline setting, since online algorithms must make decisions irrevocably and without knowing what to come.

So maybe we are lucky and we can approximate a fractional solution online (by a factor of $\alpha$) and round this solution with the loss of the $IG$ (also online) to get some integral solution for our problem.

My question is, how we can adapt the knowledge of our offline setting to the online setting.

As a matter of fact, can we just conclude that if we have a online $\alpha$-approximation for the fractional online problem, that we could (at most) have some $\frac{\alpha}{IG}$-approximation by rounding.

Thanks in advance


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.