Picking where to put a few sensors so that they reconstruct a whole physical field, such as a temperature map, a flow, or pressure in a water network, is a well-studied problem. The standard tool is the greedy algorithm. It adds one sensor at a time, always the one that most improves an information score. For scores with diminishing returns (submodular scores) it is guaranteed to reach at least 63% of the best possible value. Real deployments add a requirement this guarantee ignores: the sensors must form a connected communication network, so every measurement can hop to a base station. Under that requirement greedy can fail badly. A "bridge" location that adds little information may be the only way to reach a valuable region, and greedy never picks it. Existing guarantees for connected selection either get worse as the budget grows or assume idealized disk-shaped sensing in the plane.
This note argues that bridge blindness depends on how the field's spatial correlation compares with the communication range. It is not an unavoidable feature of connected selection. In a smooth field, a relay node also measures something correlated with its valuable neighbor, so its gain is not zero. We propose a connected greedy that grows the network by short paths of at most $h$ nodes. It comes with a guarantee controlled by one quantity that can be measured on the actual greedy run: how much gain per node the best short path achieves, relative to the remaining gap to the optimum. The result is an a posteriori certificate on every instance. We also aim for an a priori prediction, in terms of kernel lengthscale versus hop distance, of when this simple method is near-optimal and when heavier Steiner-tree machinery is needed.
Core Claim
Let $G$ be the communication graph on candidate locations. Let $f$ be a monotone submodular information score, for example Gaussian-process mutual information or the log-determinant of a reduced-order posterior. Let $k$ be the total node budget, with relays counted. The algorithm keeps a connected set $S$. At each step it adds the path $P$ of at most $h$ new nodes, attached to $S$, that maximizes gain per node, $[f(S\cup P)-f(S)]/|P|$. We define the step-wise path ratio
$$\beta_h(S) \;=\; \frac{\max_{P}\,[f(S\cup P)-f(S)]/|P|}{\,[f(S^*)-f(S)]/k\,},$$
where $S^*$ is the best connected set of size $k$. If $\beta_h(S)\ge\beta$ along the whole run, the usual argument that the remaining gap shrinks at each step carries over. The residual contracts by at least $\exp(-\beta|P|/k)$ per path. At most $h$ budget is wasted when the final path is truncated. Together these give
$$f(S_{\text{final}}) \;\ge\; \left(1-e^{-\beta (k-h)/k}\right) f(S^*).$$
This bound says nothing new on its own. The substance lies in two further claims. First, $\beta_h$ can be lower-bounded on any run without knowing $S^*$. The value $f(S)$ plus the top-$k$ single-node marginal gains is an upper bound on $f(S^*)$, because it drops the connectivity requirement. The resulting certificate is conservative but valid on every instance. Second, for Gaussian-process fields, we conjecture and aim to prove that $\beta_h$ is bounded below by a function of the kernel correlation at distance $h$ hops. If so, the regime where simple neighbor-expansion greedy is safe is predicted by the ratio of correlation length to hop length. This quantity plays the role that sensing-to-communication radius ratio $C=R_s/R_c$ plays in the geometric analysis of Approximation Algorithms for the Connected Sensor Cover Problem, but it applies to general graphs and information objectives rather than disk coverage.
Relation to Prior Work
Three lines of work motivate and constrain the design.
The first is connected submodular region search. Optimal Region Search with Submodular Maximization selects a connected road-network region under an edge-cost budget. Its greedy carries a ratio of $1/O(\sqrt{\Delta/b_{\min}})$, which decays with the budget. Its fast heuristic expands only to immediate neighbors, the $h=1$ case, and the paper itself names this heuristic as the one vulnerable to the bridge trap. We keep the simplicity of neighbor expansion. What we add is a lookahead of $h$ hops and an instance-level certificate that says when the trap is actually present.
The second is geometric connected coverage. Approximation Algorithms for the Connected Sensor Cover Problem achieves $1/(102C^2)$ for budgeted connected coverage. It does so with profit reassignment, cell partitioning, and quota Steiner trees, all tied to Euclidean disks and unweighted sensors. FPT Approximations for Connected Maximum Coverage proves that connected coverage is W[1]-hard and hard to approximate in general. It then obtains approximation schemes on $K_{a,d}$-free coverage graphs, with runtimes of order $2^{O(k^2d/\varepsilon)}$. This hardness result constrains us: no parameter-free constant factor is possible for general objectives on general graphs. For that reason we aim for a guarantee parameterized by a measurable, data-dependent quantity rather than a universal constant.
The third is information-driven placement for physical fields. Near-optimal Observation Selection using Submodular Functions establishes Gaussian-process mutual information as a submodular objective. It uses pSPIEL to trade informativeness against routing cost, and it computes online bounds during execution. We reuse its lazy evaluation and its idea of an online bound. We differ in treating relays as budgeted nodes and in explaining when a far simpler greedy suffices. Pivoted-QR methods take yet another approach. Examples are PySensors, its 2.0 extensions with no-go zones (PySensors 2.0), and cost-weighted pivoting from Clark et al.. These choose points for reconstruction quality alone and cannot enforce connectivity. Clark et al. also warn that reduced bases from the singular value decomposition overfit on slowly decaying spectra. We therefore evaluate reconstruction error on held-out snapshots, not only the information score.
Research Program
The program has three parts.
The theoretical part proves the path-greedy bound. It then handles the unknown location of the optimum by running from a set of candidate roots, either all of them or a sampled subset chosen with a covering argument. The main target is the Gaussian-process lower bound on $\beta_h$. The intuition is that a relay adjacent to a high-variance region reduces that region's posterior variance roughly in proportion to the squared kernel correlation. That should lower-bound the relay's gain relative to the node it leads to. We will also construct adversarial fields where correlation is shorter than one hop. In those fields $\beta_h$ collapses, so the bound must be tight in form.
The algorithmic part implements path greedy efficiently. Paths of at most $h$ nodes are enumerated with a bounded breadth-first search from the frontier. Stale path gains are skipped using the lazy upper bounds that submodularity gives. Log-determinant gains are updated with rank-one Cholesky updates.
The empirical part measures the certified $\beta_h$ alongside the true ratio. The true ratio is available where exact optima can be computed.
Baselines
The naive reference points bracket the problem. From below, we sample random connected sets of size $k$ by growing breadth-first search trees from random roots. From above, we run unconstrained lazy greedy and PySensors QR pivoting (de Silva et al.) with connectivity ignored. These unconstrained runs are infeasible deployments, but they bound what connectivity costs.
The strongest practical competitor is two-stage placement. It first selects informative points by greedy or QR, then connects them with an approximate Steiner tree whose relays count against the budget. Informative points are pruned until the tree fits. This is the natural engineering answer and the one a reviewer will expect. It gets the same objective code, the same candidate graph, and a Steiner routine with an equal compute allowance.
The strongest published competitors are AppORS/IAppORS from Chen et al., adapted to node budgets, and pSPIEL from Krause and Guestrin. On the pure coverage variant we also run the budgeted algorithm of Huang et al.. The file reports only worst-case guarantees for these methods: $1/(102C^2)$ for Huang et al. and $1/O(\sqrt{\Delta/b_{\min}})$ for Chen et al. No reported empirical result was found on Lacuna for any of them on field-reconstruction benchmarks, so all numbers will come from our own runs under matched wall-clock budgets. On small instances ($n\lesssim 200$), exact optima come from a mixed-integer program that adds cut-based connectivity constraints lazily, in the spirit of the subtour-elimination analyses of Hojny et al..
The key ablation varies $h$ over 1, 2, 3, and 5, with $h=1$ being Chen et al.'s Heu2. This isolates the lookahead. A second ablation compares the certificate against the true ratio from the exact solver, which isolates how tight the certificate is.
Beating the baselines means the following. Path greedy should match two-stage placement and pSPIEL within 2% of objective value when correlation length is large, at lower cost. When correlation is short it should either dominate them or correctly certify its own weakness. Across all regimes, the certified $\beta_h$ should rank instances by true optimality gap, with Spearman correlation above 0.8.
Why not just…?
Why not just place sensors greedily and then add relays? This is a real threat when relays are nearly free. The ordering "choose, then connect" spends budget on relays after the informative points are fixed. When those points are scattered, the Steiner tree can consume most of the budget and pruning follows. Our sweep over correlation length and budget measures exactly where two-stage wins. If it wins everywhere, the certificate still has value as a diagnostic, and we would narrow the claim accordingly.
Why not just solve it exactly with integer programming? The number of connectivity cuts grows exponentially, as analyzed by Hojny et al. and Ravanbakhsh et al.. Log-determinant objectives are also nonlinear. We use the exact solver as ground truth on small graphs and report where it stops scaling.
Why not just use pSPIEL or the geometric constant-factor algorithm? These methods address the right problem but carry heavy machinery. The geometric algorithm is restricted to disks in $\mathbb{R}^2$ and carries a constant of 102. Our question is whether that machinery buys anything on smooth physical fields. The head-to-head comparison at matched compute answers it directly.
Proposed Experiments
The first testbed is synthetic Gaussian-process fields on grids with unit-disk communication graphs. We sweep the ratio of lengthscale to hop distance from 0.3 to 5, with budgets $k$ from 10 to 60. This is where the predicted crossover should appear. The second is sea-surface-temperature data from the regime studied by Clark et al., using posterior log-determinant on reduced bases together with held-out reconstruction error. The third is water distribution networks in the setting of Perelman et al., where communication follows the pipe graph. The fourth is road networks with points-of-interest scores following Chen et al..
The metrics are objective value relative to the exact optimum or the unconstrained upper bound, reconstruction RMSE, runtime, and certified versus true $\beta_h$.
The decisive check is the synthetic sweep. The idea stands if the lengthscale-to-hop ratio at which $h=1$ greedy falls behind two-stage placement matches the ratio at which certified $\beta_h$ drops, and the proven Gaussian-process bound predicts that point to within a small factor. If $\beta_h$ stays uninformative there, the idea fails.
References
- Approximation Algorithms for the Connected Sensor Cover Problem.
- Optimal Region Search with Submodular Maximization
- FPT Approximations for Connected Maximum Coverage
- Near-optimal Observation Selection using Submodular Functions
- PySensors: A Python package for sparse sensor placement
- PySensors 2.0: A Python Package for Sparse Sensor Placement
- Greedy Sensor Placement With Cost Constraints
- Mixed-integer programming techniques for the connected max-k-cut problem
- Augmentative Message Passing for Traveling Salesman Problem and Graph Partitioning
- Sensor placement for fault location identification in water networks: A minimum test cover approach