On local search and placement of meters in networks

Samir Khuller*, Randeep Bhatia, Robert Pless

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

3 Scopus citations


This work is motivated by the problem of placing pressure meters in fluid networks. The problem is formally defined in graph-theoretic terms as follows. Given a graph, find a cotree (complement of a tree) incident upon the minimum number of vertices. We show that this problem is NP-hard and MAX SNP-hard. We design an algorithm with an approximation factor of 2+ε for this problem. This approximation bound comes from the analysis of a local search heuristic, a common practical optimization technique that does not often allow formal worst case analysis. The algorithm is made very efficient by finding restrictive definitions of the local neighborhoods to be searched. We also exhibit a PTAS for this problem when the input is restricted to planar graphs. Although we are motivated by water distribution networks, the algorithms apply to any system that can be formulated as a network, in which Kirchoff's laws are valid and a bijective relation exists between the flow variable and the effort variable, like circuits and electrical networks.

Original languageEnglish (US)
Number of pages10
StatePublished - Jan 1 2000
Event11th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 9 2000Jan 11 2000


Other11th Annual ACM-SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA

ASJC Scopus subject areas

  • Chemical Health and Safety
  • Software
  • Safety, Risk, Reliability and Quality
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On local search and placement of meters in networks'. Together they form a unique fingerprint.

Cite this