Polynomial-time methods to solve unimodular quadratic programs with performance guarantees

Shankarachary Ragi, Edwin K.P. Chong, Hans D. Mittelmann

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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.

Original languageEnglish (US)
Article number8534389
Pages (from-to)2118-2127
Number of pages10
JournalIEEE Transactions on Aerospace and Electronic Systems
Issue number5
StatePublished - Oct 2019


  • Greedy methods
  • Performance guarantees
  • Polynomial-time Methods
  • String submodularity
  • Unimodular codes
  • Unimodular quadratic programming (UQP)

ASJC Scopus subject areas

  • Aerospace Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'Polynomial-time methods to solve unimodular quadratic programs with performance guarantees'. Together they form a unique fingerprint.

Cite this