Complexity Results for Some Global Optimization Problems

被引：0

作者：

M. Locatelli

机构：

[1] Università di Torino,Dip. Informatica

来源：

Journal of Optimization Theory and Applications | 2009年 / 140卷

关键词：

Global optimization; Complexity; Approximation problems; Separable functions;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We discuss the complexity of a class of highly structured global optimization problems, namely the maximization of separable functions, with each one-dimensional component convex and nondecreasing, over polytopes defined by a 0-1 constraint matrix with at most two variables involved in each constraint. In particular, we prove some inapproximability and approximability results.

引用

页码：93 / 102

页数：9

共 24 条

[1]

Bodlaender H.L.(1990)Computational complexity of norm maximization Combinatorica 10 203-225

[2]

Gritzmann P.(1996)NP-hardness of linear multiplicative programming and related problems J. Glob. Optim. 9 113-119

[3]

Klee V.(1991)Quadratic programming with one negative eigenvalue is NP-hard J. Glob. Optim. 1 15-22

[4]

van Leeuwen J.(1974)Computationally related problems SIAM J. Comput. 3 267-279

[5]

Matsui T.(1995)The complexity of approximating a nonlinear program Math. Program. 69 429-441

[6]

Pardalos P.(2002)Solving standard quadratic optimization problems via linear, semidefinite, and copositive programming J. Glob. Optim. 24 163-185

[7]

Vavasis S.A.(2002)Geometric optimization problems likely not contained in APX Discrete Comput. Geom. 28 201-209

[8]

Sahni S.(2006)A PTAS for the minimization of polynomials of fixed degree over the simplex Theor. Comput. Sci. 361 210-225

[9]

Bellare M.(1992)Approximation algorithms for indefinite quadratic programming Math. Program. 57 279-311

[10]

Rogaway P.(1999)Approximating quadratic programming with bound and quadratic constraints Math. Program. 84 219-226

← 1 2 3 →