A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity \(2^{O(n\log n)}\)
From MaRDI portal
Publication:1941539
DOI10.1016/J.DISOPT.2012.11.003zbMath1287.90034arXiv1006.4661OpenAlexW1555903671MaRDI QIDQ1941539
Matthias Köppe, Robert Hildebrand
Publication date: 13 March 2013
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1006.4661
Related Items (18)
A general scheme for solving a large set of scheduling problems with rejection in FPT time ⋮ Enumerating Integer Points in Polytopes with Bounded Subdeterminants ⋮ On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming ⋮ Minimizing a Symmetric Quasiconvex Function on a Two-Dimensional Lattice ⋮ Minimization of even conic functions on the two-dimensional integral lattice ⋮ Integer programming in parameterized complexity: five miniatures ⋮ A polynomial algorithm for minimizing discrete convic functions in fixed dimension ⋮ On the complexity of quasiconvex integer minimization problem ⋮ Complexity of optimizing over the integers ⋮ A randomized sieving algorithm for approximate integer programming ⋮ Zero-convex functions, perturbation resilience, and subgradient projections for feasibility-seeking methods ⋮ Integer Programming in Parameterized Complexity: Three Miniatures. ⋮ Norm bounds and underestimators for unconstrained polynomial integer minimization ⋮ Centerpoints: A Link between Optimization and Convex Geometry ⋮ On the rational polytopes with Chvátal rank 1 ⋮ Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting ⋮ FPT-algorithm for computing the width of a simplex given by a convex hull ⋮ Scheduling meets \(n\)-fold integer programming
This page was built for publication: A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity \(2^{O(n\log n)}\)