Logarithmic hardness of the directed congestion minimization problem
From MaRDI portal
Publication:2931414
DOI10.1145/1132516.1132592zbMath1301.68139MaRDI 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
90C35: Programming involving graphs or networks
90C59: Approximation methods and heuristics in mathematical programming
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs, Hardness of Routing for Minimizing Superlinear Polynomial Cost in Directed Graphs
