FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension

被引：8

作者：

De Loera, Jesus A. ^{[2
]}

Hemmecke, Raymond ^{[1
]}

Koeppe, Matthias ^{[1
]}

Weismantel, Robert ^{[1
]}

机构：

[1] Otto VonGuericke Univ Magdegurg, FMA IMO, D-39106 Magdeburg, Germany

[2] Univ Calif Davis, Dept Math, Davis, CA 95616 USA

来源：

MATHEMATICAL PROGRAMMING | 2008年 / 115卷 / 02期

基金：

美国国家科学基金会;

关键词：

mixed-integer nonlinear programming; integer programming in fixed dimension; computational complexity; approximation algorithms; FPTAS;

D O I：

10.1007/s10107-007-0175-8

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We show the existence of a fully polynomial-time approximation scheme (FPTAS) for the problem of maximizing a non-negative polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed. Moreover, using a weaker notion of approximation, we show the existence of a fully polynomial-time approximation scheme for the problem of maximizing or minimizing an arbitrary polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed.

引用

页码：273 / 290

页数：18

共 50 条

[1] FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
Jesús A. De Loera
Raymond Hemmecke
Matthias Köppe
Robert Weismantel
Mathematical Programming, 2008, 115 : 273 - 290
[2] FPTAS for mixed-integer polynomial optimization with a fixed number of variables
De Loera, J. A.
Hemmecke, R.
Koeppe, M.
Weismantel, R.
PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, : 743 - +
[3] A Framework for Globally Optimizing Mixed-Integer Signomial Programs
Ruth Misener
Christodoulos A. Floudas
Journal of Optimization Theory and Applications, 2014, 161 : 905 - 932
[4] A Framework for Globally Optimizing Mixed-Integer Signomial Programs
Misener, Ruth
Floudas, Christodoulos A.
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2014, 161 (03) : 905 - 932
[5] Optimizing nuclear power plant refueling with mixed-integer programming
Fourcade, F
Johnson, E
Bara, M
CorteyDumont, P
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1997, 97 (02) : 269 - 280
[6] OAMIP: Optimizing ANN Architectures Using Mixed-Integer Programming
ElAraby, Mostafa
Wolf, Guy
Carvalho, Margarida
INTEGRATION OF CONSTRAINT PROGRAMMING, ARTIFICIAL INTELLIGENCE, AND OPERATIONS RESEARCH, CPAIOR 2023, 2023, 13884 : 219 - 237
[7] Optimizing Dynamic Evacuation Using Mixed-Integer Linear Programming
Obaid, Hamoud Bin
Trafalis, Theodore B.
Abushaega, Mastoor M.
Altherwi, Abdulhadi
Hamzi, Ahmed
MATHEMATICS, 2025, 13 (01)
[8] FIXED POINTS OF POLYNOMIALS OVER DIVISION RINGS
Chapman, Adam
Vishkautsan, Solomon
BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 2021, 104 (02) : 256 - 262
[9] A mixed-integer programming formulation for optimizing the double row layout problem
Amaral, Andre R. S.
OPTIMIZATION METHODS & SOFTWARE, 2024, 39 (06): : 1428 - 1444
[10] Optimizing automotive inbound logistics: A mixed-integer linear programming approach
Baller, Reinhard
Fontaine, Pirmin
Minner, Stefan
Lai, Zhen
TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW, 2022, 163

← 1 2 3 4 5 →