On Problems Equivalent to (min,+)-Convolution

DOI10.1145/3293465zbMath1454.68052OpenAlexW3125825223WikidataQ112313931 ScholiaQ112313931MaRDI QIDQ4629984

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

Publication date: 28 March 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7421/

zbMATH Keywords

knapsackconditional lower boundsfine-grained complexity(min,+)-convolutionsubquadratic equivalence

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)

Related Items (18)

Faster minimization of tardy processing time on a single machine ⋮ Approximating subset sum ratio via subset sum computations ⋮ Bisection of bounded treewidth graphs by convolutions ⋮ Unnamed Item ⋮ Solving cut-problems in quadratic time for graphs with bounded treewidth ⋮ Unnamed Item ⋮ On the complexity of scheduling problems with a fixed number of parallel identical machines ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ A polyhedral perspective on tropical convolutions ⋮ Computing generalized convolutions faster than brute force ⋮ ON BINARY SOLUTIONS TO SYSTEMS OF EQUATIONS ⋮ Unnamed Item ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Unnamed Item ⋮ Unnamed Item ⋮ More on change-making and related problems ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.

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