A PTAS for a class of binary non-linear programs with low-rank functions

Trung Thanh Nguyen; Khaled Elbassioni

doi:10.1016/j.orl.2021.06.017

A PTAS for a class of binary non-linear programs with low-rank functions

Trung Thanh Nguyen, Khaled Elbassioni

Electrical Engineering

Phenikaa University

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

1 Scopus citations

Abstract

Binary non-linear programs belong to the class of combinatorial problems which are computationally hard even to approximate. This paper aims to explore some conditions on the problem structure, under which the resulting problem can be well approximated. Particularly, we consider a setting when both objective function and constraint are low-rank functions, which depend only on a few linear combinations of the input variables, and provide polynomial time approximation schemes. Our result generalizes and unifies some existing results in the literature.

Original language	British English
Pages (from-to)	633-638
Number of pages	6
Journal	Operations Research Letters
Volume	49
Issue number	5
DOIs	https://doi.org/10.1016/j.orl.2021.06.017
State	Published - Sep 2021

Keywords

Binary non-linear program
Convex program
Low-rank function
Polynomial-time approximation scheme

Access to Document

10.1016/j.orl.2021.06.017

Cite this

@article{a6753a0397c5421f85143d2c3bbdfa1e,

title = "A PTAS for a class of binary non-linear programs with low-rank functions",

abstract = "Binary non-linear programs belong to the class of combinatorial problems which are computationally hard even to approximate. This paper aims to explore some conditions on the problem structure, under which the resulting problem can be well approximated. Particularly, we consider a setting when both objective function and constraint are low-rank functions, which depend only on a few linear combinations of the input variables, and provide polynomial time approximation schemes. Our result generalizes and unifies some existing results in the literature.",

keywords = "Binary non-linear program, Convex program, Low-rank function, Polynomial-time approximation scheme",

author = "Nguyen, {Trung Thanh} and Khaled Elbassioni",

note = "Funding Information: We thank the reviewer for all the helpful suggestions and comments that helped us substantially improve the manuscript. The work of the first author was supported by the Vietnam National Foundation for Science and Technology Development , Grant 102.01-2020.21 . Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2021",

month = sep,

doi = "10.1016/j.orl.2021.06.017",

language = "British English",

volume = "49",

pages = "633--638",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - A PTAS for a class of binary non-linear programs with low-rank functions

AU - Nguyen, Trung Thanh

AU - Elbassioni, Khaled

N1 - Funding Information: We thank the reviewer for all the helpful suggestions and comments that helped us substantially improve the manuscript. The work of the first author was supported by the Vietnam National Foundation for Science and Technology Development , Grant 102.01-2020.21 . Publisher Copyright: © 2021 Elsevier B.V.

PY - 2021/9

Y1 - 2021/9

N2 - Binary non-linear programs belong to the class of combinatorial problems which are computationally hard even to approximate. This paper aims to explore some conditions on the problem structure, under which the resulting problem can be well approximated. Particularly, we consider a setting when both objective function and constraint are low-rank functions, which depend only on a few linear combinations of the input variables, and provide polynomial time approximation schemes. Our result generalizes and unifies some existing results in the literature.

AB - Binary non-linear programs belong to the class of combinatorial problems which are computationally hard even to approximate. This paper aims to explore some conditions on the problem structure, under which the resulting problem can be well approximated. Particularly, we consider a setting when both objective function and constraint are low-rank functions, which depend only on a few linear combinations of the input variables, and provide polynomial time approximation schemes. Our result generalizes and unifies some existing results in the literature.

KW - Binary non-linear program

KW - Convex program

KW - Low-rank function

KW - Polynomial-time approximation scheme

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

U2 - 10.1016/j.orl.2021.06.017

DO - 10.1016/j.orl.2021.06.017

M3 - Article

AN - SCOPUS:85109783561

SN - 0167-6377

VL - 49

SP - 633

EP - 638

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

A PTAS for a class of binary non-linear programs with low-rank functions

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this