Questions tagged [competitive-ratio]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers

How to find competitive ratio of any online algorithm?

I am starting to learn online algorithms but am still stuck in determining the competitive ratio. I cannot understand how to find it. All the research papers are so difficult to understand. Please ...
Michaylor Riya's user avatar
5 votes
0 answers

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 ...
vesii's user avatar
  • 223
1 vote
0 answers

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 ...
WretchedCreature's user avatar
2 votes
0 answers

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 ...
zdm's user avatar
  • 1,046
2 votes
1 answer

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 ...
shaqed's user avatar
  • 351
3 votes
1 answer

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 ...
nataman's user avatar
  • 53