Questions tagged [competitive-ratio]
The competitive-ratio tag has no usage guidance.
3
questions
2
votes
0answers
105 views
How to define the potential function method for an online maximization problem?
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 ...
2
votes
1answer
207 views
Competitive ratio of the ski rental problem
Reading about the Ski Rental Problem in Wikipedia, I got confused on the "when" is the buying of the skis occur. I could think of 2 possible ways, but each of them would have a different competitive ...
3
votes
1answer
68 views
Lower bound on competitive ratio of $m$-machine scheduling
Given a sequence of positive reals $a_1, a_2, \dots, a_n$ and an integer $m$, for each $j$ assign $a_j$ to a machine $i$, $1< i < m$, so as to minimize the maximum, over $i$, of the sum of all ...
