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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiway cuts (extended abstract). In: Proceedings of 24th ACM Symposium on Theory of Computing (STOC’92), pp. 241–251 (1992)
Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, A.: Sparsification—a technique for speeding up dynamic graph algorithms. J. ACM 44, 669–696 (1997)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979)
Goldschmidt, O., Hochbaum, D.S.: Polynomial algorithm for the k-cut problem. In: Proceedings of 29th Annual IEEE Symposium on Foundations of Computer Science (FOCS’88), pp. 444–451 (1988)
Gu, W., Jia, X.: On a traffic control problem. In: Proceedings of 8th International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN’05), pp. 510–515 (2005)
Italiano, G.F.: Fully dynamic connectivity: upper and lower bounds. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms, pp. 335–337. Springer, Berlin (2008)
Khuller, S., Bhatia, R., Pless, R.: On local search and placement of meters in networks. SIAM J. Comput. 32(2), 470–487 (2003)
Saran, H., Vazirani, V.V.: Finding k-cuts within twice the optimal. SIAM J. Comput. 24(1), 101–108 (1995)
Tsin, Y.H.: A simple 3-edge-connected component algorithm. Theory Comput. Syst. 40, 125–142 (2007)
Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research of F. Chin supported in parts by grant (HKU 7113/07E).
Research of M. Chrobak and L. Yan supported by NSF Grant CCF-0729071.
Rights and permissions
About this article
Cite this article
Chin, F., Chrobak, M. & Yan, L. Algorithms for Placing Monitors in a Flow Network. Algorithmica 68, 1–15 (2014). https://doi.org/10.1007/s00453-012-9665-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-012-9665-z