Max-Min Greedy Interference Alignment on Linear Deterministic K-User Interference Channels

We explore an algorithmic approximation of achievable lower bounds for the generalized degrees of freedom on finite-field linear deterministic K-user interference channels. With a heuristic greedy algorithm, derived from results on the maximum independent set problem in graph theory, the max-min generalized degrees of freedom for desired links are approached. The idea of interference alignment is implicitly contained in the algorithm. It is applied to deterministic interference channels with entirely symmetric cross-channel gains, and compared to the generalized degrees of freedom of a currently known coding scheme. The greedy heuristic also generalizes to deterministic interference channels with asymmetric channel gains.