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

Revision as of 20:24, 23 August 2024

scientific article; zbMATH DE number 7792585

Language	Label	Description	Also known as
English	Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems	scientific article; zbMATH DE number 7792585

Statements

instance of

scholarly article

0 references

title

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

0 references

published in

Optimization Letters

0 references

publication date

22 January 2024

0 references

zbMATH Keywords

convolution

0 references

nonlinear knapsack

0 references

separable objective

0 references

shortest vector problem

0 references

closest vector problem

0 references

dynamic programming

0 references

integer programming

0 references

piece-wise linear

0 references

MaRDI profile type

Publication

0 references

cites work

Solving the Shortest Vector Problem in 2 <sup>n</sup> Time Using Discrete Gaussian Sampling

0 references

A sieve algorithm for the shortest lattice vector problem

0 references

Some Sieving Algorithms for Lattice Problems

0 references

Q5091168

0 references

Better Approximations for Tree Sparsity in Nearly-Linear Time

0 references

Fast algorithms for knapsack via convolution and prediction

0 references

Sampling methods for shortest vectors, closest vectors and successive minima

0 references

Necklaces, Convolutions, and X + Y

0 references

Smallest \(k\)-enclosing rectangle revisited

0 references

Clustered Integer 3SUM via Additive Combinatorics

0 references

Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky

0 references

Faster min-plus product for monotone instances

0 references

On Problems Equivalent to (min,+)-Convolution

0 references

Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings

0 references

Covering cubes and the closest vector problem

0 references

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

0 references

Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis

0 references

An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem

0 references

FPT-algorithms for some problems related to integer programming

0 references

Algorithms for the Shortest and Closest Lattice Vector Problems

0 references

Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm

0 references

Algorithms to construct Minkowski reduced and Hermite reduced lattice bases

0 references

On Integer Programming and Convolution.

0 references

Minkowski's Convex Body Theorem and Integer Programming

0 references

Improved dynamic programming in connection with an FPTAS for the knapsack problem

0 references

Ottimizzazione Combinatoria

0 references

Q5875578

0 references

Q5111351

0 references

Q5417723

0 references

A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations

0 references

Fast Lattice Point Enumeration with Minimal Overhead

0 references

Sieve algorithms for the shortest vector problem are practical

0 references

Dynamic programming revisited: Improving knapsack algorithms

0 references

On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications

0 references

Q4221106

0 references

Finding the Closest Lattice Point by Iterative Slicing

0 references

Q4227352

0 references

Smooth strongly convex interpolation and exact worst-case performance of first-order methods

0 references

Faster All-Pairs Shortest Paths via Circuit Complexity

0 references

A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge

0 references

Identifiers

DOI

10.1007/s11590-023-02017-5

0 references

Mathematics Subject Classification ID

90Cxx

0 references

zbMATH DE Number

7792585

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6181364

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