Polynomial-Time Methods to Solve Unimodular Quadratic Programs With Performance Guarantees
Shankarachary Ragi, Edwin K. P. Chong, Hans Detlef Mittelmann · IEEE Transactions on Aerospace and Electronic Systems · 2018
We develop polynomial-time heuristic methods to solve unimodular quadratic program (UQP) approximately, which is a known non-deterministic polynomial-time hard (NP-hard) problem. Several problems in active sensing and wireless communication applications boil down to UQPs. First, we derive a performance bound for a known UQP approximation method called dominant eigenvector matching heuristic. Next, we present two new polynomial-time heuristic methods inspired from the greedy strategy, and we provide performance guarantees for these methods with respect to the optimal objective.