Hardness of the undirected congestion minimization problem
From MaRDI portal
Publication:3581429
DOI10.1145/1060590.1060633zbMath1192.68310MaRDI QIDQ3581429
Lisa Zhang, Matthew T. Andrews
Publication date: 16 August 2010
Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1060590.1060633
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Flows on few paths: Algorithms and lower bounds, Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs, A fast heuristic algorithm for the maximum concurrent \(k\)-splittable flow problem, An exact approach for the maximum concurrent \(k\)-splittable flow problem, On the approximation of the single source \(k\)-splittable flow problem, Inapproximability and approximability of minimal tree routing and coloring, Hardness of Routing for Minimizing Superlinear Polynomial Cost in Directed Graphs