Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems

DOI10.1007/s11590-023-02017-5MaRDI QIDQ6181364

No author found.

Publication date: 22 January 2024

Published in: Optimization Letters (Search for Journal in Brave)

zbMATH Keywords

integer programmingdynamic programmingconvolutionshortest vector problemclosest vector problempiece-wise linearnonlinear knapsackseparable objective

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smooth strongly convex interpolation and exact worst-case performance of first-order methods
• Sampling methods for shortest vectors, closest vectors and successive minima
• Algorithms to construct Minkowski reduced and Hermite reduced lattice bases
• FPT-algorithms for some problems related to integer programming
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Dynamic programming revisited: Improving knapsack algorithms
• Smallest \(k\)-enclosing rectangle revisited
• An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem
• A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
• Clustered Integer 3SUM via Additive Combinatorics
• Solving the Shortest Vector Problem in 2 ⁿ Time Using Discrete Gaussian Sampling
• Algorithms for the Shortest and Closest Lattice Vector Problems
• Some Sieving Algorithms for Lattice Problems
• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• Sieve algorithms for the shortest vector problem are practical
• Finding the Closest Lattice Point by Iterative Slicing
• Ottimizzazione Combinatoria
• Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
• Minkowski's Convex Body Theorem and Integer Programming
• On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications
• Faster All-Pairs Shortest Paths via Circuit Complexity
• Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
• Better Approximations for Tree Sparsity in Nearly-Linear Time
• On Problems Equivalent to (min,+)-Convolution
• A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• On Integer Programming and Convolution.
• A sieve algorithm for the shortest lattice vector problem
• Fast algorithms for knapsack via convolution and prediction
• Fast Lattice Point Enumeration with Minimal Overhead
• Covering cubes and the closest vector problem
• Necklaces, Convolutions, and X + Y
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• Faster min-plus product for monotone instances

This page was built for publication: Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems