Complexity of integer quasiconvex polynomial optimization

DOI10.1016/j.jco.2005.04.004zbMath1146.90482MaRDI QIDQ2387421

Sebastian Heinz

Publication date: 2 September 2005

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2005.04.004

zbMATH Keywords

Lenstra's algorithm; Integer optimization; Quasiconvex polynomial

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C10: Integer programming

90C60: Abstract computational complexity for mathematical programming problems

Related Items

Minimizing a Symmetric Quasiconvex Function on a Two-Dimensional Lattice, Enumerating Integer Points in Polytopes with Bounded Subdeterminants, Minimization of even conic functions on the two-dimensional integral lattice, Integer Programming in Parameterized Complexity: Three Miniatures., Centerpoints: A Link between Optimization and Convex Geometry, Complexity of optimizing over the integers, A randomized sieving algorithm for approximate integer programming, Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes, Scheduling and fixed-parameter tractability, Single-machine scheduling with workload-dependent tool change durations and equal processing time jobs to minimize total completion time, Integer convex minimization by mixed integer linear optimization, A general scheme for solving a large set of scheduling problems with rejection in FPT time, A polynomial algorithm for minimizing discrete convic functions in fixed dimension, FPT-algorithm for computing the width of a simplex given by a convex hull, On the complexity of quasiconvex integer minimization problem, Integer programming in parameterized complexity: five miniatures, On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming

Cites Work

• Factoring polynomials with rational coefficients
• Geometric algorithms and combinatorial optimization.
• Integer optimization on convex semialgebraic sets
• Integer Programming with a Fixed Number of Variables
• There Cannot be any Algorithm for Integer Programming with Quadratic Constraints
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item