Questions tagged [competitive-ratio]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 53