From Online Computation and Competitive Analysis By Allan Borodin, Ran El-Yaniv, to prove that an online algorithm $\text{ALG}$ is $c$-competitive for a minimization problem (i.e., there exists a constant $\alpha$ such that $\text{ALG}(I)\leq c\cdot \text{OPT}(I) +\alpha,$), it is sufficient to find a potential function $\Phi$ satisfying the following conditions with respect to any possible event sequence:

  • If only the adversary $\text{OPT}$ moves (i.e., is active) during event $e_i$ and pays $x$ for this move, then $\Delta\Phi=\Phi_i-\Phi_{i-1}\leqslant cx$; that is, $\Phi$ increases by at most $cx$.
  • If only $\text{ALG}$ moves during event $e_i$ and pays $x$ for this move, then $\Delta\Phi=\Phi_i-\Phi_{i-1}\leqslant -x$; that is, $\Phi$ decreases by at least $x$.
  • There exists a constant $b$ independent of the request sequence such that for all $i$, $\Phi_i\geqslant b$.

How this changes if the problem is a maximization problem instead of a minimization one? In other words, we would like to prove that there exists a constant $\beta$ such that $\text{OPT}(I)\leq c\cdot \text{ALG}(I)+\beta,$

I guess that the first bullet becomes "gains $x$ for this move, then $\Phi$ decreases by at least $x$" and the second bullet becomes "and gains $x$ for this move, then $\Phi$ increases by at most $cx$" but I am not sure. How to modify the above definition in order to deal with maximization problems?

  • $\begingroup$ Is there any definition of $c$? $\endgroup$ – user46712 May 9 '18 at 4:34
  • $\begingroup$ $c$ could be anything as long as it does not depend on the request sequence. For example, in job scheduling problems where we have $m$ machines and $n$ jobs arrive online, $c$ can be a function of $m$, a constant, but can't be a function of $n$. $\endgroup$ – zdm May 9 '18 at 10:46

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.