Using a competitive ratio measure

Assignment Help Basic Computer Science

Reference no: EM13706088

Imagine you are standing next to a long fence, extending as far as you can see in both directions. You want to cross the fence and you know that somewhere it has a hole you can go through. But, you don't know whether the hole is to your right or left, or how far away it is. You want a strategy for finding the hole that does well using a competitive ratio measure.

Let's model this problem as follows: you are initially located at the origin on the real line. The hole is at some (positive or negative) integer coordinate n. You can move left or right at cost equal to the distance moved, and the game continues until you reach n. You then look at the ratio of your cost to |n| (n is the optimal off-line cost since it is the distance you would have travelled if you had known where the hole was). Design a deterministic algorithm whose competitive ratio is at most 9.

Reference no: EM13706088

Questions Cloud

Why are cigarettes and alcohol the most heavily taxed : Why are cigarettes and alcohol the most heavily taxed items in the US? Now, if the government increases the price of these items by 10%, how does this affect the stores that sell them?

Describe the logistics system : Describe the steps in making sure that flights take off on time for an airline. Describe the different steps that must occur for an on-time plane departure.

What is use of the mac and ip for vlan 1 in a cisco switch : Implement the network topology using Packet Tracer - How many MAC does the 24 port Cisco switch used in the Packet Tracer - How many MAC does the 24 port Cisco switch used in the Packet Tracer has and what is the use of the MAC and IP for VLAN 1 in ..

The solution is some real number : Let P be a problem. For any instance x ∈ P, the solution is some real number f(x). Let A be a randomized algorithm for P, such that it gives a solution A(x) that lies in [1/2f(x), 2f(x)] with probability 2/3.

Using a competitive ratio measure : Imagine you are standing next to a long fence, extending as far as you can see in both directions. You want to cross the fence and you know that somewhere it has a hole you can go through. But, you don't know whether the hole is to your right or..

Design a file system checker for our file system : Design a file system checker for our file system. You should call it csefsck. It will have to do the following: The DeviceID is correct All times are in the past, nothing in the future Validate that the free block list is accurate this includ..

Suppose you want to manage a relatively small project : Suppose you want to manage a relatively small project, but you have no access to project management software of any kind. How could you use a spreadsheet program or a database program to manage the project? Share your ideas in 750 words.

Advantages and disadvantages to a firm of financial hedging : What are the advantages and disadvantages to a firm of financial hedging of its operating exposure compared to operational hedges (such as relocating its manu-facturing site)?

Control recommendation strategies in computer security : Control recommendation strategies in computer security environment. This must be an APA style report with in text citation for example (Stallings, 2012) and I need the reference in APA style at the end.

User Account

All Pages