Yiftach Ravid

FOCS Conference 1991 Conference Paper

Competitive Algorithms for Layered Graph Traversal

• Amos Fiat
• Dean P. Foster
• Howard J. Karloff
• Yuval Rabani
• Yiftach Ravid
• Sundar Vishwanathan

A layered graph is a connected, weighted graph whose vertices are partitioned into sets L/sub 0/=(s), L/sub 1/, L/sub 2/, .. ., and whose edges run between consecutive layers. Its width is max( mod L/sub i/ mod ). In the online layered graph traversal problem, a searcher starts at s in a layered graph of unknown width and tries to reach a target vertex t; however, the vertices in layer i and the edges between layers i-1 and i are only revealed when the searcher reaches layer i-1. The authors give upper and lower bounds on the competitive ratio of layered graph traversal algorithms. They give a deterministic online algorithm that is O(9w)-competitive on width-w graphs and prove that for no w can a deterministic online algorithm have a competitive ratio better than 2w/sup -2/ on width-w graphs. They prove that for all w, w/2 is a lower bound on the competitive ratio of any randomized online layered graph traversal algorithm. For traversing layered graphs consisting of w disjoint paths tied together at a common source, they give a randomized online algorithm with a competitive ratio of O(log w) and prove that this is optimal up to a constant factor. >

STOC Conference 1991 Conference Paper

Lower Bounds for Randomized k-Server and Motion Planning Algorithms

• Howard J. Karloff
• Yuval Rabani
• Yiftach Ravid

FOCS Conference 1990 Conference Paper

Competitive k-Server Algorithms (Extended Abstract)

• Amos Fiat
• Yuval Rabani
• Yiftach Ravid

Deterministic competitive k-server algorithms are given for all k and all metric spaces. This settles the k-server conjecture of M. S. Manasse et al. (1988) up to the competitive ratio. The best previous result for general metric spaces was a three-server randomized competitive algorithm and a nonconstructive proof that a deterministic three-server competitive algorithm exists. The competitive ratio the present authors can prove is exponential in the number of servers. Thus, the question of the minimal competitive ratio for arbitrary metric spaces is still open. The methods set forth here also give competitive algorithms for a natural generalization of the k-server problem, called the k-taxicab problem. >