# Minimizing Interference-to-Signal Ratios in Multi-Cell Telecommunication Networks
## 2 The Total Interference Minimization Problem  
The formulation of the _total interference minimization problem_ that we use in this paper was proposed and studied by [PERSON] and [PERSON] in their influential paper Dai and Bai (2018). We give our description of their formulation in the following paragraphs. There is a collection \(B:=\{b_{i}:i\in I\}\) of distinct base stations and there is a collection \(U:=\{u_{j}:j\in J\}\) of distinct users, where \(b=|B|\) and \(u=|U|\), and the base stations and the users are indexed by the sets of the first \(b\) and \(u\) natural numbers, respectively. As we mentioned earlier, the users can be mobile phones, but can also be devices of the IoT. Therefore, their numbers altogether can be rather large compared to the number of base stations. (However, in future 6G networks, the ratio of these numbers may change considerably. We do not consider this case here.) The model depicts the network with a bipartite graph: one class contains the BSs, while the other class consists of the users. Let \(G=(V;E):=(B\cup U;E)\) where \(E\) consists of ordered pairs of form \((b_{i},u_{j})\). We use the shorthand \((i,j)\) as well. We define a weight function \(w:B\times U\rightarrow\mathbb{R}^{+}_{0}\), where each \(w_{i,j}\) is a positive real number if and only if \((i,j)\) is an edge in \(G\), otherwise we set \(w_{i,j}=0\). The weight of an edge of the bipartite graph represents the signal strength between its endpoints (one BS and one user). Let \(M\) be a positive integer, and let \([M]\) be the set of the integers from \(1\) to \(M\). Let \(\mathcal{I}=(I_{1},\ldots,I_{M})\) and \(\mathcal{J}=(I_{1},\ldots,J_{M})\) be partitions of \(I\) and \(J\), respectively. Finally, let \(\mathcal{P}\) be the set of partition pairs: \(\mathcal{P}:=\{P_{\ell}=(I_{\ell},I_{\ell}):\ell\in[M]\}\). Let us define the following quantities: for each integer \(\ell\in[M]\), let  
\[w(P_{\ell}):=\sum_{i\in I_{\ell},j\in I_{\ell}}w_{i,j}\quad\text{and}\quad \tilde{w}(P_{\ell}):=\sum_{i\in I_{\ell},j\in I\setminus I_{\ell}}w_{i,j}+ \sum_{i\in\Gamma\setminus I_{\ell},j\in I_{\ell}}w_{i,j}. \tag{1}\]  
In graph theoretical terms, the first quantity is the _weight_ of the partition class, while the second one is the _cut value_ of the partition class. **Definition 1** (IF-cluster system). : _A partition \(\mathcal{P}\) is an IF-cluster system (or IF-cluster for short; IF abbreviates interference), if_  
1. _there is no partition class_ \(P_{\ell}\) _such that_ \(I_{\ell}=\emptyset\)_, and_
2. _for any user, there is a base station in its cluster to which it is joined by an edge in_ \(G\)_._  
_The total interference (see [PERSON] and [PERSON] (2018)) of a given \(\mathcal{P}\) IF-cluster system is defined as_  
\[\mathtt{tinf}(\mathcal{P})=\sum_{\ell\in[M]}\ast\frac{\tilde{w}(P_{\ell})}{w (P_{\ell})}, \tag{2}\]  
_where the star superscript denotes that if a partition class \(I_{k}\) is empty, then the index \(\ell\) skips \(k\), so that the formula in (2) is well-defined._  
Condition (ii) above covers the requirement that all users must be served in a solution. The omission of a partition class in the sum (2) is due to the technical ability that some base stations that do not serve any users can be switched off temporarily. **Engineering complexity. ** Typically, in clustering problems, the smaller the number of clusters, the more \"efficient\" the best available solution is with the given number of clusters. In our problem, this is indeed the case: [PERSON] and [PERSON] showed (see [PERSON] and [PERSON] (2018), Theorem 1) that the optimum value of the total interference monotone increases as the number of clusters increases. It follows that if the number of clusters is not restricted, then the best solution is to consider one giant cluster containing every base station and user. However, the engineering necessity of managing the coordination between base stations of a large cluster is usually quite prohibitive and depends heavily on the boundary conditions.