On Problems Equivalent to (min,+)-Convolution

DOI10.4230/LIPICS.ICALP.2017.22MaRDI QIDQ5111352zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Marcin Mucha, Karol Węgrzycki, Michał Włodarczyk

Publication date 27 May 2020

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

zbMATH Keywords

knapsackconditional lower boundsfine-grained complexitysubquadratic equivalence\((\min,+)\)-convolution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Abstract: In recent years, significant progress has been made in explaining the apparent hardness of improving upon the naive solutions for many fundamental polynomially solvable problems. This progress has come in the form of conditional lower bounds -- reductions from a problem assumed to be hard. The hard problems include 3SUM, All-Pairs Shortest Path, SAT, Orthogonal Vectors, and others. In the $(min,+)$-convolution problem, the goal is to compute a sequence $(c[i]{)}_{i=0}^{n-1}$, where $c[k]=$ $mi{n}_{i=0,ldots,k}$ $$ $+$ $$, given sequences $(a[i]{)}_{i=0}^{n-1}$ and $(b[i]{)}_{i=0}^{n-1}$. This can easily be done in $O(n^2)$ time, but no $O(n^{2-varepsilon})$ algorithm is known for $varepsilon>0$. In this paper, we undertake a systematic study of the $(min,+)$-convolution problem as a hardness assumption. First, we establish the equivalence of this problem to a group of other problems, including variants of the classic knapsack problem and problems related to subadditive sequences. The $(min,+)$-convolution problem has been used as a building block in algorithms for many problems, notably problems in stringology. It has also appeared as an ad hoc hardness assumption. Second, we investigate some of these connections and provide new reductions and other results. We also explain why replacing this assumption with the SETH might not be possible for some problems.

Recommendations

• On problems equivalent to \((\min,+)\)-convolution
• On convolutions of convex sets and related problems
• An extremal problem in convolutions
• An extremal problem in convolutions
• On the infimum convolution inequality
• On convolution ofL-convex functions
• scientific article; zbMATH DE number 1342076
• On convolution equivalence with applications
• A note on the convex infimum convolution inequality
• On the convex infimum convolution inequality with optimal cost function

Cited in

(14)

• Smallest k-enclosing rectangle revisited
• scientific article; zbMATH DE number 7561512 (Why is no real title available?)
• scientific article; zbMATH DE number 7204473 (Why is no real title available?)
• Fast algorithms for knapsack via convolution and prediction
• \((\min ,+)\) matrix and vector products for inputs decomposable into few monotone subsequences
• Smallest \(k\)-enclosing rectangle revisited
• Extreme witnesses and their applications
• On integer programming and convolution
• Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
• Hamming Distance Completeness
• On problems equivalent to \((\min,+)\)-convolution
• Fine-Grained Complexity Theory (Tutorial)
• scientific article; zbMATH DE number 7617051 (Why is no real title available?)
• On the convex infimum convolution inequality with optimal cost function

This page was built for publication: On Problems Equivalent to (min,+)-Convolution

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