Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max

DOI10.1145/3313276.3316373zbMath1433.68611arXiv1907.11078OpenAlexW3101250927WikidataQ112313933 ScholiaQ112313933MaRDI QIDQ5212835

Karl Bringmann, Karol Węgrzycki, Marvin Künnemann

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximation schemeshardness of approximationstrongly polynomial algorithmsfine-grained complexity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (1)

Computing generalized convolutions faster than brute force

This page was built for publication: Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max