Optimal Path Discovery Problem with Homogeneous Knowledge

Consider the following problem: given a complete graph G = (V, E), two nodes s and t in V, and a positive hidden value f(e) for each edge e ∈ E, discover an s − t-path P that minimizes the value F(P), for some objective function F. The issue is that the edge values f(⋅) are hidden, hence, to discover an optimal path, it is required to uncover the value of some edges. The goal then is to discover an optimal path by means of uncovering the least possible amount of edge values. This problem, named the Optimal Path Discovery (OPD) problem, is an extension of the well known Shortest Path Discovery problem in which f(e) represents the length of e, and F(P) computes the length of P. In this paper, we study the OPD problem when the only previous information known about the f(⋅) values is that they fall in the interval (0,∞) for all e ∈ E. We first study the number of uncovered edges as a measure to evaluate algorithms. We see that this measure does not differentiate correctly algorithms according to their performance. Therefore, we introduce the query ratio, the ratio between the number of uncovered edges and the least number of edge values required to solve the problem. We prove a 1 + 4/n − 8/n² lower bound on the query ratio and we present an algorithm whose query ratio, when it finds the optimal path, is upper bounded by 2 − 1/(n − 1), where n = |V |. Finally, we implement different algorithms and evaluate their query ratio experimentally.