Algorithms for Placing Monitors in a Flow Network

Algorithms for Placing Monitors in a Flow Network

0.00 Avg rating0 Votes
Article ID: iaor2014325
Volume: 68
Issue: 1
Start Page Number: 1
End Page Number: 15
Publication Date: Jan 2014
Journal: Algorithmica
Authors: , ,
Keywords: networks: flow, heuristics
Abstract:

In the Flow Edge‐Monitor Problem, we are given an undirected graph G=(V,E), an integer k>0 and some unknown circulation ψ on G. We want to find a set of k edges in G, so that if we place k monitors on those edges to measure the flow along them, the total number of edges for which the flow can be uniquely determined is maximized. In this paper, we first show that the Flow Edge‐Monitor Problem is NP‐hard. Then we study an algorithm called σGreedy that, in each step, places monitors on σ edges for which the number of edges where the flow is determined is maximized. We show that the approximation ratio of 1‐Greedy is 3 and that the approximation ratio of 2‐Greedy is 2.

Reviews

Required fields are marked *. Your email address will not be published.