# Minimizing the Installation Cost of Ground Stations in Satellite Networks: Complexity, Dynamic Programming and Approximation Algorithm

arXiv: https://arxiv.org/abs/2005.07498 · HTML: https://mlsanity.com/paper/2005.07498/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2020.

## Built on by (most cited first, 1 of 1)

- [Optimal Ground Station Selection for Low-Earth Orbiting Satellites](https://mlsanity.com/paper/2410.16282/) (2024)

## Abstract (arXiv)

In this letter, we study the optimum selection of ground stations (GSs) in RF/optical satellite networks (SatNets) in order to minimize the overall installation cost under an outage probability requirement, assuming independent weather conditions between sites. First, we show that the optimization problem can be formulated as a binary-linear-programming problem, and then we give a formal proof of its NP-hardness. Furthermore, we design a dynamic-programming algorithm of pseudo-polynomial complexity with global optimization guarantee as well as an efficient (polynomial-time) approximation algorithm with provable performance guarantee on the distance of the achieved objective value from the global optimum. Finally, the performance of the proposed algorithms is verified through numerical simulations.