Mathematical Programming, volume 151, issue 2, pages 433-457
An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex
2
Centrum Wiskunde and Informatica (CWI), Amsterdam, The Netherlands
|
Publication type: Journal Article
Publication date: 2014-10-15
Journal:
Mathematical Programming
Q1
Q2
SJR: 1.982
CiteScore: 5.7
Impact factor: 2.2
ISSN: 00255610, 14364646
General Mathematics
Software
Abstract
The problem of minimizing a polynomial over the standard simplex is one of the basic NP-hard nonlinear optimization problems—it contains the maximum clique problem in graphs as a special case. It is known that the problem allows a polynomial-time approximation scheme (PTAS) for polynomials of fixed degree, which is based on polynomial evaluations at the points of a sequence of regular grids. In this paper, we provide an alternative proof of the PTAS property. The proof relies on the properties of Bernstein approximation on the simplex. We also refine a known error bound for the scheme for polynomials of degree three. The main contribution of the paper is to provide new insight into the PTAS by establishing precise links with Bernstein approximation and the multinomial distribution.
Found
Found
Top-30
Journals
|
1
2
|
|
|
SIAM Journal on Optimization
2 publications, 15.38%
|
|
|
Optimization Letters
2 publications, 15.38%
|
|
|
Mathematics
1 publication, 7.69%
|
|
|
Mathematical Programming
1 publication, 7.69%
|
|
|
Journal of the Operations Research Society of China
1 publication, 7.69%
|
|
|
Journal of Computer and System Sciences
1 publication, 7.69%
|
|
|
Optimization Methods and Software
1 publication, 7.69%
|
|
|
Lecture Notes in Computer Science
1 publication, 7.69%
|
|
|
1
2
|
Publishers
|
1
2
3
4
5
|
|
|
Springer Nature
5 publications, 38.46%
|
|
|
Institute of Electrical and Electronics Engineers (IEEE)
3 publications, 23.08%
|
|
|
Society for Industrial and Applied Mathematics (SIAM)
2 publications, 15.38%
|
|
|
MDPI
1 publication, 7.69%
|
|
|
Elsevier
1 publication, 7.69%
|
|
|
Taylor & Francis
1 publication, 7.69%
|
|
|
1
2
3
4
5
|
- We do not take into account publications without a DOI.
- Statistics recalculated only for publications connected to researchers, organizations and labs registered on the platform.
- Statistics recalculated weekly.
Are you a researcher?
Create a profile to get free access to personal recommendations for colleagues and new articles.
Metrics
Cite this
GOST |
RIS |
BibTex |
MLA
Cite this
GOST
Copy
de Klerk E. et al. An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex // Mathematical Programming. 2014. Vol. 151. No. 2. pp. 433-457.
GOST all authors (up to 50)
Copy
de Klerk E., Laurent M., Sun Z. An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex // Mathematical Programming. 2014. Vol. 151. No. 2. pp. 433-457.
Cite this
RIS
Copy
TY - JOUR
DO - 10.1007/s10107-014-0825-6
UR - https://doi.org/10.1007/s10107-014-0825-6
TI - An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex
T2 - Mathematical Programming
AU - de Klerk, Etienne
AU - Laurent, Monique
AU - Sun, Zhao
PY - 2014
DA - 2014/10/15
PB - Springer Nature
SP - 433-457
IS - 2
VL - 151
SN - 0025-5610
SN - 1436-4646
ER -
Cite this
BibTex (up to 50 authors)
Copy
@article{2014_de Klerk,
author = {Etienne de Klerk and Monique Laurent and Zhao Sun},
title = {An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex},
journal = {Mathematical Programming},
year = {2014},
volume = {151},
publisher = {Springer Nature},
month = {oct},
url = {https://doi.org/10.1007/s10107-014-0825-6},
number = {2},
pages = {433--457},
doi = {10.1007/s10107-014-0825-6}
}
Cite this
MLA
Copy
de Klerk, Etienne, et al. “An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex.” Mathematical Programming, vol. 151, no. 2, Oct. 2014, pp. 433-457. https://doi.org/10.1007/s10107-014-0825-6.