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

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

doi:10.1109/TAES.2018.2881366

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

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

Mathematical and Statistical Sciences, School of (SoMSS)

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

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 language	English (US)
Article number	8534389
Pages (from-to)	2118-2127
Number of pages	10
Journal	IEEE Transactions on Aerospace and Electronic Systems
Volume	55
Issue number	5
DOIs	https://doi.org/10.1109/TAES.2018.2881366
State	Published - Oct 2019

Keywords

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

Access to Document

10.1109/TAES.2018.2881366

Cite this

@article{1a411b96ebcf4e6ca103462f0cb32948,

title = "Polynomial-time methods to solve unimodular quadratic programs with performance guarantees",

abstract = "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.",

keywords = "Greedy methods, Performance guarantees, Polynomial-time Methods, String submodularity, Unimodular codes, Unimodular quadratic programming (UQP)",

author = "Shankarachary Ragi and Chong, {Edwin K.P.} and Mittelmann, {Hans D.}",

note = "Publisher Copyright: {\textcopyright} 1965-2011 IEEE.",

year = "2019",

month = oct,

doi = "10.1109/TAES.2018.2881366",

language = "English (US)",

volume = "55",

pages = "2118--2127",

journal = "IEEE Transactions on Aerospace and Electronic Systems",

issn = "0018-9251",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "5",

}

TY - JOUR

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

AU - Ragi, Shankarachary

AU - Chong, Edwin K.P.

AU - Mittelmann, Hans D.

PY - 2019/10

Y1 - 2019/10

N2 - 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.

AB - 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.

KW - Greedy methods

KW - Performance guarantees

KW - Polynomial-time Methods

KW - String submodularity

KW - Unimodular codes

KW - Unimodular quadratic programming (UQP)

UR - http://www.scopus.com/inward/record.url?scp=85056587897&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85056587897&partnerID=8YFLogxK

U2 - 10.1109/TAES.2018.2881366

DO - 10.1109/TAES.2018.2881366

M3 - Article

AN - SCOPUS:85056587897

SN - 0018-9251

VL - 55

SP - 2118

EP - 2127

JO - IEEE Transactions on Aerospace and Electronic Systems

JF - IEEE Transactions on Aerospace and Electronic Systems

IS - 5

M1 - 8534389

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this