On Problems Equivalent to (min,+)-Convolution

DOI10.1145/3293465zbMath1454.68052WikidataQ112313931 ScholiaQ112313931MaRDI QIDQ4629984

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

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

knapsack; conditional lower bounds; fine-grained complexity; (min,+)-convolution; subquadratic equivalence

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C27: Combinatorial optimization

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W32: Algorithms on strings