Minimizing the total cost of network measurements in a distributed manner
Baruch Awerbuch, Rohit Khandekar · 2007
We consider the Active Min-Cost Measurement problem to minimize the cost incurred by measuring network link delays. Although the problem has a polynomial representation, its covering LP formulation, for which most of the previous distributed algorithms apply, has an exponential number of variables, one for each path.