Logarithmic hardness of the directed congestion minimization problem

DOI10.1145/1132516.1132592MaRDI QIDQ2931414zbMATH OpenOpenAlexFDO

Authors Lisa Zhang, Matthew 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

congestion minimizationdirected graphshardness of approximation

Mathematics Subject Classification ID

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

Recommendations

• Almost-tight hardness of directed congestion minimization
• Hardness of the Undirected Congestion Minimization Problem
• Hardness of the undirected congestion minimization problem
• New hardness results for congestion minimization and machine scheduling
• New hardness results for congestion minimization and machine scheduling

Cited in

(8)

• Hardness of routing for minimizing superlinear polynomial cost in directed graphs
• Almost-tight hardness of directed congestion minimization
• Hardness of the undirected congestion minimization problem
• Hardness of the Undirected Congestion Minimization Problem
• New hardness results for congestion minimization and machine scheduling
• New hardness results for congestion minimization and machine scheduling
• Improved hardness of approximation of diameter in the CONGEST model
• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931414)