On Problems Equivalent to (min,+)-Convolution

DOI10.4230/LIPICS.ICALP.2017.22zbMath1441.68070arXiv1702.07669OpenAlexW2946474232MaRDI QIDQ5111352

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

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)

Related Items (6)

Unnamed Item ⋮ Smallest \(k\)-enclosing rectangle revisited ⋮ Hamming Distance Completeness ⋮ Smallest k-enclosing rectangle revisited ⋮ On Integer Programming and Convolution. ⋮ Fine-Grained Complexity Theory (Tutorial)

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