Publication:5111352

DOI10.4230/LIPIcs.ICALP.2017.22zbMath1441.68070arXiv1702.07669MaRDI QIDQ5111352

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

Publication date: 27 May 2020

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

zbMATH Keywords

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

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