Logarithmic hardness of the directed congestion minimization problem

DOI10.1145/1132516.1132592zbMath1301.68139OpenAlexW2125725829MaRDI QIDQ2931414

Lisa Zhang, Matthew T. Andrews

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1132516.1132592

zbMATH Keywords

directed graphshardness of approximationcongestion minimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ Hardness of Routing for Minimizing Superlinear Polynomial Cost in Directed Graphs

This page was built for publication: Logarithmic hardness of the directed congestion minimization problem