### Almost-tight hardness of directed congestion minimizationAlmost-tight hardness of directed congestion minimization

Access Restriction
Subscribed

 Author Andrews, Matthew ♦ Zhang, Lisa Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2008 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Hardness of approximation ♦ Congestion minimization ♦ Undirected graphs Abstract Given a set of demands in a directed graph, the directed congestion minimization problem is to route every demand with the objective of minimizing the heaviest load over all edges. We show that for any constant ϵ > 0, there is no $Ω(log^{1™ϵ}$ $\textit{M})-approximation$ algorithm on networks of size $\textit{M}$ unless $\textit{NP}$ ⊆ $\textit{ZPTIME}(\textit{n}polylog$ $\textit{n}).$ This bound is almost tight given the $\textit{O}(log$ $\textit{M}/log$ log $\textit{M})-approximation$ via randomized rounding due to Raghavan and Thompson. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2008-12-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 55 Issue Number 6 Page Count 20 Starting Page 1 Ending Page 20

#### Open content in new tab

Source: ACM Digital Library