Almost-tight hardness of directed congestion minimization

DOI10.1145/1455248.1455251zbMath1325.68094OpenAlexW1978807904MaRDI QIDQ3452193

Lisa Zhang, Matthew T. Andrews

Publication date: 11 November 2015

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

directed graphshardness of approximationcongestion minimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

Routing in Undirected Graphs with Constant Congestion

This page was built for publication: Almost-tight hardness of directed congestion minimization