Questions tagged [competitive-ratio]
The competitive-ratio tag has no usage guidance.
6
questions
5
votes
0
answers
91
views
+150
Prove: Self-organizing list that uses Move-to-Front is 2-Competitive
Preparing for my finals in my "advances algorithms" course. Usually there is a question to prove one of the theorems that was given over the course. I'm currently trying to write a full ...
- 209
0
votes
0
answers
17
views
difference between using cost vs expectation in competitive ratio
The standard definition defines the ratio as the "cost" for the worst-case input for online algorithm divided by the cost of an offline algorithm that knew the entire input sequence in ...
- 310
1
vote
0
answers
17
views
Deterministic Algorithm for searching for object $d$ units down one road in a $k$ road intersection
Suppose we are at the centre of a $k$ road intersection (i.e, there are $k$ different roads radiating out from where we are standing, infinitely). Suppose along one of these roads is a treasure.
This ...
2
votes
0
answers
235
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 ...
- 1,016
2
votes
1
answer
365
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 ...
- 351
3
votes
1
answer
110
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 ...
- 53