# Minimizing Interference-to-Signal Ratios in Multi-Cell Telecommunication Networks
###### Abstract  
In contemporary wireless communication networks, base stations are organized into coordinated clusters (called _cells_) to jointly serve the users. However, such fixed systems are plagued by the so-called cell-edge problem: near the boundaries, the interference between neighboring clusters can result in very poor interference-to-signal power ratios. To achieve a high-quality service, it is an important objective to minimize the sum of these ratios over the cells. The most common approach to solving this minimization problem is arguably the spectral clustering method. In this paper, we propose a new clustering approach, which is deterministic and computationally much less demanding than current methods. Simulating on synthetic instances indicates that our methods typically provide higher quality solutions than earlier methods. n : 05C70; 05C85; 05C90; 68W25; 94C15 +
Footnote †: journal: _Algorithms_  
0000-0001-999-4000-0001-9999-4000-0001-9999-4000-001-9999-4000-001-9999-4000-001-9999-  
the objects into pairwise disjoint classes while optimizing some \"measure\" of the resulting set of classes. Myriads of theoretical and practical problems belong to the clustering framework. They come from classical combinatorial optimization problems to printed circuit board designs, from VLSI CAD applications to distributing tasks among processors for supercomputing processes, and from pattern recognition to computer vision problems and image retrieval. The computational complexity of these problems varies from easy to very hard. For example, the minimum number of edges whose deletion places two predefined vertices into separate components in a simple graph (_minimum cut problem_[4]) can be computed in polynomial time. The situation changes dramatically if we want to separate three predefined vertices (_the multiway cut problem_). In the general case, this generalization of the problem was shown to be NP-hard [5], while the problem becomes fixed parameter tractable if the input is restricted to planar graphs [5; 6]. Probably, the very first engineering problem of a clustering nature was the following: we want to place a complicated electronic design on printed circuit boards, where each board can contain at most \(k\) components and where the electronic connections among the boards are expensive compared to connections inside a board ([7], see also [8]). It can be seen that in such a real-world problem, an upper bound on the possible size of the clusters is given too. While the notion of NP-completeness was being developed at the time, the authors correctly placed the problem into the NP-hard class. The majority of the clustering problems are NP-hard, so there is no chance to solve them exactly. Sometimes there are known performance guarantees on the solution; for example, in [5], there is a polynomial time algorithm with a \(2(1-1/k)\) approximation ratio for the multiway-cut problem, while in [9], a polynomial time \((1.5-1/k)\) approximation algorithm was developed for the same problem. The interference minimization problem in wireless networks is a known NP-hard problem, and so far a constant factor approximation algorithm has not been found. In the literature, there are several approaches to solve this problem, see [1; 10; 11; 12; 13; 14]. Because of the intractability of the problem, all of these approaches are heuristic in nature. In practice, these methods still do not satisfactorily solve the cell-edge problem [2]. Essentially, all of these method use one of the general clustering methods: the _kernel k-means_ or the _spectral clustering_ method. The former method was developed in [15; 16]. However, as was proved in [17], the two approaches are essentially equivalent with each other (for a survey on these methods, see [18]). Consequently, we compare our algorithm to the spectral clustering method (as it is used in [3]). This approach attacks this clustering problem as an undivided one, partitioning the base stations and users simultaneously.