A polynomial algorithm for minimizing discrete convic functions in fixed dimension

DOI10.1016/J.DAM.2019.10.006MaRDI QIDQ2192061zbMATH OpenOpenAlexFDO

Authors S. I. Veselov, Dmitriy V. Gribanov, N. Yu Zolotykh, A. Y. Chirkov

Publication date 29 June 2020

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

Full work available at URL https://arxiv.org/abs/2011.00598

zbMATH Keywords

integer latticequasiconvex functioncomparison oracleconvic functiondiscrete convic function

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Integer programming (90C10)

Abstract: Recently classes of conic and discrete conic functions were introduced. In this paper we use the term convic instead conic. The class of convic functions properly includes the classes of convex functions, strictly quasiconvex functions and the class of quasiconvex polynomials. On the other hand, the class of convic functions is properly included in the class of quasiconvex functions. The discrete convic function is a discrete analogue of the convic function. Recently the lower bound $3^{n-1}log(2ho-1)$ for the number of calls to the comparison oracle needed to find the minimum of the discrete convic function defined on integer points of some $n$-dimensional ball with radius $ho$ was obtained. But the problem of the existence of a polynomial (in $logho$ for fixed $n$) algorithm for minimizing such functions has remained open. In this paper, we answer positively the question of the existence of such an algorithm. Namely, we propose an algorithm for minimizing discrete convic functions that uses $2^{O(n^{2}logn)}logho$ calls to the comparison oracle and has $2^{O(n^{2}logn)}mboxpoly(logho)$ bit complexity.

Recommendations

• On the complexity of quasiconvex integer minimization problem
• Integer conic function minimization based on the comparison oracle
• \(\varepsilon\)-approximation minimization of convex functions in fixed dimension
• Minimization of even conic functions on the two-dimensional integral lattice
• Integer convex minimization by mixed integer linear optimization

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• A hierarchy of polynomial time lattice basis reduction algorithms
• A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity \(2^{O(n\log n)}\)
• A polynomial oracle-time algorithm for convex integer minimization
• Centerpoints: a link between optimization and convex geometry
• Complexity of integer quasiconvex polynomial optimization
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• Factoring polynomials with rational coefficients
• Geometric algorithms and combinatorial optimization.
• Integer Polynomial Optimization in Fixed Dimension
• Integer conic function minimization based on the comparison oracle
• Integer convex minimization by mixed integer linear optimization
• Integer optimization on convex semialgebraic sets
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• Minimizing a symmetric quasiconvex function on a two-dimensional lattice
• On the complexity of quasiconvex integer minimization problem
• Quasiconvex functions can be approximated by quasiconvex polynomials

Cited in

(11)

• Enumeration and unimodular equivalence of empty delta-modular simplices
• Minimization of even conic functions on the two-dimensional integral lattice
• Critical properties of bipartite permutation graphs
• A polynomial oracle-time algorithm for convex integer minimization
• Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems
• scientific article; zbMATH DE number 5874901 (Why is no real title available?)
• On lattice point counting in \(\varDelta\)-modular polyhedra
• On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems
• Minimizing a symmetric quasiconvex function on a two-dimensional lattice
• Integer conic function minimization based on the comparison oracle
• On the complexity of quasiconvex integer minimization problem

This page was built for publication: A polynomial algorithm for minimizing discrete convic functions in fixed dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2192061)