Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
From MaRDI portal
Publication:6181364
DOI10.1007/s11590-023-02017-5MaRDI QIDQ6181364
No author found.
Publication date: 22 January 2024
Published in: Optimization Letters (Search for Journal in Brave)
integer programmingdynamic programmingconvolutionshortest vector problemclosest vector problempiece-wise linearnonlinear knapsackseparable objective
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 n 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
