Questions tagged [competitive-ratio]
The competitive-ratio tag has no usage guidance.
4
questions
0
votes
0answers
44 views
Scheduling jobs online on 3 identical machines - a lower bound of 5/3
Consider the Online Scheduling Problem with $3$ identical machines. Jobs, with arbitrary size arrive online one after another and need to be scheduled immediately on one of the $3$ machines without ...
1
vote
0answers
161 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
292 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
94 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 ...
