Hardness of buy-at-bulk network design Export

@inproceedings{citeulike:3496844, abstract = {We consider the buy-at-bulk network design problem in which we wish to design a network for carrying multicommodity demands from a set of source nodes to a set of destination nodes. The key feature of the problem is that the cost of capacity on each edge is concave and hence exhibits economies of scale. If the cost of capacity per unit length can be different on different edges then, we say that the problem is non-uniform. The problem is uniform otherwise. We show that for any constant \&gamma;, if NP <br><table><tr><td align=center>\&nsub;<br>\&\#8254;</td></tr></table> ZPTIME(n^{polylog n}), then there is no O(log¹2 - \&gamma;/N)-approximation algorithm for non-uniform buy-at-bulk network design and there is no O(log¹4 - \&gamma;/N)-approximation algorithm for the uniform problem.}, author = {Andrews, M.}, booktitle = {Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on}, citeulike-article-id = {3496844}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/FOCS.2004.32}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1366231}, doi = {10.1109/FOCS.2004.32}, journal = {Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on}, keywords = {hardness, network\_design}, pages = {115--124}, posted-at = {2008-11-08 21:54:44}, priority = {2}, title = {Hardness of buy-at-bulk network design}, url = {http://dx.doi.org/10.1109/FOCS.2004.32}, year = {2004} }

TY - CONF ID - citeulike:3496844 L3 - citeulike-article-id:3496844 N2 - We consider the buy-at-bulk network design problem in which we wish to design a network for carrying multicommodity demands from a set of source nodes to a set of destination nodes. The key feature of the problem is that the cost of capacity on each edge is concave and hence exhibits economies of scale. If the cost of capacity per unit length can be different on different edges then, we say that the problem is non-uniform. The problem is uniform otherwise. We show that for any constant &gamma;, if NP <br><table><tr><td align=center>&nsub;<br>&#8254;</td></tr></table> ZPTIME(n^{polylog n}), then there is no O(log¹2 - &gamma;/N)-approximation algorithm for non-uniform buy-at-bulk network design and there is no O(log¹4 - &gamma;/N)-approximation algorithm for the uniform problem. JF - Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on EP - 124 TI - Hardness of buy-at-bulk network design T2 - Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on SP - 115 KW - hardness KW - network_design AU - Andrews, M PY - 2004/// UR - http://dx.doi.org/10.1109/FOCS.2004.32 ER -