On a class of functions attaining their maximum at the vertices of a polyhedron

DOI10.1016/0166-218X(88)90093-5zbMath0663.90068MaRDI QIDQ1115347

Fabio Tardella

Publication date: 1989

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

polynomial time solvability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Combinatorial optimization (90C27) Polytopes and polyhedra (52Bxx)

Related Items

Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, GLOMIQO: global mixed-integer quadratic optimizer, An edge-concave underestimator for the global optimization of twice-differentiable nonconvex problems, Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations, Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2, Global dynamic optimization using edge-concave underestimator, A framework for globally optimizing mixed-integer signomial programs, A generalization of the classical \(\alpha \)BB convex underestimation via diagonal and nondiagonal quadratic terms, The fundamental theorem of linear programming: extensions and applications, Existence and sum decomposition of vertex polyhedral convex envelopes, ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations

Cites Work

• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
• Unimodular functions
• The ellipsoid method and its consequences in combinatorial optimization
• Concave Minimization Via Collapsing Polytopes
• Product form parametric representation of the solutions to a quadratic boolean equation
• An Algorithm for Global Minimization of Linearly Constrained Concave Quadratic Functions
• Convergent Algorithms for Minimizing a Concave Function
• Global Maximization of a Convex Function with Linear Inequality Constraints
• An analysis of approximations for maximizing submodular set functions—I
• Unnamed Item
• Unnamed Item
• Unnamed Item