Paper  abstract   bibtex   

@article{BBN+xx,
  author =	 {{Bentert}, Matthias and {van Bevern}, René 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.},
  sourcecode =	 {https://gitlab.com/rvb/mpsc},
  year =	 {accepted for publication, 2020},
  url =		 {https://arxiv.org/abs/1706.03177v3},
  date =	 {2020-10-08}
}