Parameterized algorithms for power-efficiently connecting wireless sensor networks: Theory and experiments. Bentert, M., van Bevern, R., Nichterlein, A., Niedermeier, R., & Smirnov, P. V. INFORMS Journal on Computing, 2021. In press
Parameterized algorithms for power-efficiently connecting wireless sensor networks: Theory and experiments [link]Code  Parameterized algorithms for power-efficiently connecting wireless sensor networks: Theory and experiments [link]Slides  Parameterized algorithms for power-efficiently connecting wireless sensor networks: Theory and experiments [link]Preprint  doi  abstract   bibtex   
We study an NP-hard problem motivated by energy-efficiently maintaining the connectivity of a symmetric wireless sensor communication network: Given an edge-weighted n-vertex graph, find a connected spanning subgraph of minimum cost, where the cost is determined by letting each vertex pay the most expensive edge incident to it in the subgraph. On the negative side, we show that o(logn)-approximating the difference d between the optimal solution cost and a natural lower bound is NP-hard and that, under the Exponential Time Hypothesis, there are no exact algorithms running in 2^o(n) time or in f(d)⋅n^O(1) time for any computable function f. On the positive side, we provide an algorithm that reconnects O(logn) connected components with minimum additional cost in polynomial time. These algorithms are motivated by application scenarios of monitoring areas or where an existing sensor network may fall apart into several connected components due to sensor faults. In experiments, the algorithm solves instances with four such connected components and about 8 000 vertices in five minutes, outperforming CPLEX with known ILP formulations for the problem.
@article{BBN+xx,
  author =	 {{Bentert}, Matthias and René van Bevern and
                  {Nichterlein}, André and {Niedermeier}, Rolf and
                  Smirnov, Pavel V.},
  title =	 {Parameterized algorithms for power-efficiently
                  connecting wireless sensor networks: Theory and
                  experiments},
  journal =	 {INFORMS Journal on Computing},
  abstract =	 {We study an NP-hard problem motivated by
                  energy-efficiently maintaining the connectivity of a
                  symmetric wireless sensor communication network:
                  Given an edge-weighted n-vertex graph, find a
                  connected spanning subgraph of minimum cost, where
                  the cost is determined by letting each vertex pay
                  the most expensive edge incident to it in the
                  subgraph. On the negative side, we show that
                  o(logn)-approximating the difference d between the
                  optimal solution cost and a natural lower bound is
                  NP-hard and that, under the Exponential Time
                  Hypothesis, there are no exact algorithms running in
                  2^o(n) time or in f(d)⋅n^O(1) time for any
                  computable function f. On the positive side, we
                  provide an algorithm that reconnects O(logn)
                  connected components with minimum additional cost in
                  polynomial time. These algorithms are motivated by
                  application scenarios of monitoring areas or where
                  an existing sensor network may fall apart into
                  several connected components due to sensor
                  faults. In experiments, the algorithm solves
                  instances with four such connected components and
                  about 8 000 vertices in five minutes, outperforming
                  CPLEX with known ILP formulations for the problem.},
  url_Code =	 {https://gitlab.com/rvb/mpsc},
  url_Slides =
                  {https://www.researchgate.net/publication/328262005_The_min-power_symmetric_connectivity_problem_with_few_obligatory_network_components},
  year =	 {2021},
  note =	 {In press},
  doi =		 {10.1287/ijoc.2020.1045},
  url_Preprint = {https://arxiv.org/abs/1706.03177},
  date =	 {2020-10-08},
  keywords =	 {connected spanning subgraphs, monitoring areas,
                  reconnecting sensor networks, parameterized
                  complexity analysis, approximation hardness,
                  parameterization above lower bounds, color-coding,
                  experimental comparison},
}

Downloads: 0