onsider the following online problem here are two taxis on a line that initially start at the origin. At positive integer time t, a request point ht on the line arrive:s In response, cach taxi can move to a different location on the line, or stay put at its current point. The path traveled by at least one of the two taxis much cross ht. Thoe C . T objective is to minimize the total movement of the taxis (a) As a warmup show that if there is a c-competitive algorithm A for this problem then there is a c-competitive algorithm B that only moves one taxi in response to cach request, and that one taxi moves directly from its position to the request. (b) Give an adversarial strategy to show that the competitive ratio of every deter- ministic algorithm is at least 2 Hint: Come up with a request sequence that makes it hard to decide if one of the taxis should imove (c) Consider the following algorithm A. If both taxis are to the left of ht, then a rightmost taxi moves to ht. If both taxis are to the right of ht, then a leftmost taxi moves to ht. If ht is between the two taxis, then both taxis move toward ht at the same rate until one of the taxis reaches ht, at which point both taxis stop moving. Show that this algorithm is 2-competitive using the following potential function: ? = twice the distance between the leftmost taxi for A and the leftmost taxi for optimal plus twice the distance between the rightmost taxi for ? and the rightmost taxi for optimal plus the distance between the leftmost and the rightmost taxis for A. So you need to show that for each request, the cost to + the change in the potential ? is at most 2 times the cost to optimal onsider the following online problem here are two taxis on a line that initially start at the origin. At positive integer time t, a request point ht on the line arrive:s In response, cach taxi can move to a different location on the line, or stay put at its current point. The path traveled by at least one of the two taxis much cross ht. Thoe C . T objective is to minimize the total movement of the taxis (a) As a warmup show that if there is a c-competitive algorithm A for this problem then there is a c-competitive algorithm B that only moves one taxi in response to cach request, and that one taxi moves directly from its position to the request. (b) Give an adversarial strategy to show that the competitive ratio of every deter- ministic algorithm is at least 2 Hint: Come up with a request sequence that makes it hard to decide if one of the taxis should imove (c) Consider the following algorithm A. If both taxis are to the left of ht, then a rightmost taxi moves to ht. If both taxis are to the right of ht, then a leftmost taxi moves to ht. If ht is between the two taxis, then both taxis move toward ht at the same rate until one of the taxis reaches ht, at which point both taxis stop moving. Show that this algorithm is 2-competitive using the following potential function: ? = twice the distance between the leftmost taxi for A and the leftmost taxi for optimal plus twice the distance between the rightmost taxi for ? and the rightmost taxi for optimal plus the distance between the leftmost and the rightmost taxis for A. So you need to show that for each request, the cost to + the change in the potential ? is at most 2 times the cost to optimal