{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T14:12:57Z","timestamp":1773583977656,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,7,1]],"date-time":"2005-07-01T00:00:00Z","timestamp":1120176000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2005,7]]},"abstract":"<jats:p>\n            Network design problems, such as generalizations of the Steiner Tree Problem, can be cast as edge-cost-flow problems. An edge-cost flow problem is a min-cost flow problem in which the cost of the flow equals the sum of the costs of the edges carrying positive flow.We prove a hardness result for the Minimum Edge Cost Flow Problem (MECF). Using the one-round two-prover scenario, we prove that MECF does not admit a 2\n            <jats:sup>\n              log\n              <jats:sup>1-\u03b5<\/jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            -ratio approximation, for every constant \u03b5 &gt; 0, unless\n            <jats:italic>NP<\/jats:italic>\n            \u2286\n            <jats:italic>DTIME<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>polylogn<\/jats:sup>\n            ).A restricted version of MECF, called Infinite Capacity MECF (ICF), is defined. The ICF problem is defined as follows: (i) all edges have infinite capacity, (ii) there are multiple sources and sinks, where flow can be delivered from every source to every sink, (iii) each source and sink has a supply amount and demand amount, respectively, and (iv) the required total flow is given as part of the input. The goal is to find a minimum edge-cost flow that meets the required total flow while obeying the demands of the sinks and the supplies of the sources. This problem naturally arises in practical scheduling applications, and is equivalent to the special case of single source MECF, with all edges not touching the source or the sink having infinite capacity.The directed ICF generalizes the Covering Steiner Problem in directed and undirected graphs. The undirected version of ICF generalizes several network design problems, such as: Steiner Tree Problem,\n            <jats:italic>k<\/jats:italic>\n            -MST, Point-to-point Connection Problem, and the generalized Steiner Tree Problem.An\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>x<\/jats:italic>\n            )-approximation algorithm for undirected ICF is presented. We also present a bi-criteria approximation algorithm for directed ICF. The algorithm for directed ICF finds a flow that delivers half the required flow at a cost that is at most\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03b5<\/jats:sup>\n            \/\u03b5\n            <jats:sup>4<\/jats:sup>\n            ) times bigger than the cost of an optimal flow. The running time of the algorithm is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            <jats:sup>2\/\u03b5<\/jats:sup>\n            \u010b\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1+1\/\u03b5<\/jats:sup>\n            ), where\n            <jats:italic>x<\/jats:italic>\n            denotes the required total flow.Randomized approximation algorithms for the Covering Steiner Problem in directed and undirected graphs are presented. The algorithms are based on a randomized reduction to a problem called 1\/2-Group Steiner. In undirected graphs, the approximation ratio matches the approximation ratio of Konjevod et al. [2002]. However, our algorithm is much simpler. In directed graphs, the algorithm is the first nontrivial approximation algorithm for the Covering Steiner Problem. Deterministic algorithms are obtained by derandomization.\n          <\/jats:p>","DOI":"10.1145\/1077464.1077470","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"74-101","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["On network design problems: fixed cost flows and the covering steiner problem"],"prefix":"10.1145","volume":"1","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[{"name":"Rutgers University, Camden, New Jersey"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wolfgang","family":"Slany","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Wien, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of SWAT","author":"Arata K.","year":"2000","unstructured":"Arata , K. , Iwata , S. , Makino , K. , and Fujishige , S . 2000. Source location: Locating sources to meet flow demands in undirected networks . In Proceedings of SWAT 2000 .]] Arata, K., Iwata, S., Makino, K., and Fujishige, S.2000. Source location: Locating sources to meet flow demands in undirected networks. In Proceedings of SWAT 2000.]]"},{"key":"e_1_2_1_3_1","unstructured":"Arora S. and Lund C. 1996. Hardness of approximations. In Approximation Algorithms for NP-hard Problems Dorit Hochbaum Ed. PWS Publishing.]]   Arora S. and Lund C. 1996. Hardness of approximations. In Approximation Algorithms for NP-hard Problems Dorit Hochbaum Ed. PWS Publishing.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1542"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1042"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the Symposium on Foundations of Computer Scince. IEEE Computer Society Press, Los Alamitos, Calif.]]","author":"Charikar M.","unstructured":"Charikar , M. , Chekuri , C. , Goel , A. Guha , S. , and Plotkin , S . 1998. Approximating a finite metric by small number of trees . In Proceedings of the Symposium on Foundations of Computer Scince. IEEE Computer Society Press, Los Alamitos, Calif.]] Charikar, M., Chekuri, C., Goel, A. Guha, S., and Plotkin, S. 1998. Approximating a finite metric by small number of trees. In Proceedings of the Symposium on Foundations of Computer Scince. IEEE Computer Society Press, Los Alamitos, Calif.]]"},{"key":"e_1_2_1_8_1","first-page":"60","volume-title":"IPCO","author":"Chudak F.","unstructured":"Chudak , F. , Roughgarden , T. , and Williamson , D . 2001. Approximate k-MSTs and k-Steiner trees via the primal-dual method and lagrangean Relaxation . In IPCO , pp. 60 -- 70 .]] Chudak, F., Roughgarden, T., and Williamson, D.2001. Approximate k-MSTs and k-Steiner trees via the primal-dual method and lagrangean Relaxation. In IPCO, pp. 60--70.]]"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00310-3"},{"key":"e_1_2_1_10_1","first-page":"593","volume-title":"Proceedings of the European Symposium on Algorithms (ESA)","author":"Di Gaspero L.","unstructured":"Di Gaspero , L. , G\u00e4rtner , J. , Kortsarz , G. , Musliu , N. , Schaerf , A. , and Slany , W . 2003. The minimum shift design problem: Theory and practice . In Proceedings of the European Symposium on Algorithms (ESA) , pp. 593 -- 604 .]] Di Gaspero, L., G\u00e4rtner, J., Kortsarz, G., Musliu, N., Schaerf, A., and Slany, W. 2003. The minimum shift design problem: Theory and practice. In Proceedings of the European Symposium on Algorithms (ESA), pp. 593--604.]]"},{"key":"e_1_2_1_11_1","volume-title":"Graph theory","author":"Diestel R.","unstructured":"Diestel , R. 2000. Graph theory , 2 nd Ed. Springer-Verlag , New York , URL: http:\/\/www.math.uni-hamburg.de\/home\/diestel\/books\/graph.theory\/.]] Diestel, R. 2000. Graph theory, 2nd Ed. Springer-Verlag, New York, URL: http:\/\/www.math.uni-hamburg.de\/home\/diestel\/books\/graph.theory\/.]]","edition":"2"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(96)00085-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2786335.2786340"},{"key":"e_1_2_1_14_1","volume-title":"1979. Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","unstructured":"Garey , M. R. , and Johnson , D. S . 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman and Company .]] Garey, M. R., and Johnson, D. S.1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company.]]"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 37th Symposium on Foundation of Computer Science","author":"Garg N.","unstructured":"Garg , N. 1996. A 3-approximation for minimum spanning tree spanning k vertices . In Proceedings of the 37th Symposium on Foundation of Computer Science . IEEE Computer Society Press , Los Alamitos , Calif., 302--309.]] Garg, N.1996. A 3-approximation for minimum spanning tree spanning k vertices. In Proceedings of the 37th Symposium on Foundation of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 302--309.]]"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"e_1_2_1_17_1","volume-title":"1996. Bounding procedures for multicommodity capacitated fixed charge network design problems. Publication CRT-96-06","author":"Gendron B.","unstructured":"Gendron , B. , and Crainic , T. G . 1996. Bounding procedures for multicommodity capacitated fixed charge network design problems. Publication CRT-96-06 , Centre de recherche sur les transports, Universit\u00e9 de Montr\u00e9al, Montreal, Ont., Canada.]] Gendron, B., and Crainic, T. G.1996. Bounding procedures for multicommodity capacitated fixed charge network design problems. Publication CRT-96-06, Centre de recherche sur les transports, Universit\u00e9 de Montr\u00e9al, Montreal, Ont., Canada.]]"},{"key":"e_1_2_1_18_1","first-page":"114","volume-title":"Ed. PWS Publishing Company","author":"Goemans M. X.","unstructured":"Goemans , M. X. , and Williamson , D. P . 1997. The primal-dual method for approximation algorithms and its application to network design problems. In Approximation Algorithms, D. Hochbaum , Ed. PWS Publishing Company , pp. 114 -- 191 .]] Goemans, M. X., and Williamson, D. P. 1997. The primal-dual method for approximation algorithms and its application to network design problems. In Approximation Algorithms, D. Hochbaum, Ed. PWS Publishing Company, pp. 114--191.]]"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)00177-N"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230190304"},{"key":"e_1_2_1_21_1","first-page":"62","volume-title":"Proceedings of the 4th Meeting of the Nordic Section of the Mathematical Programming Society","author":"Holmberg K.","unstructured":"Holmberg , K. , and Yuan , D . 1997. A Lagrangean heuristic-based branch-and-bound approach for the capacitated network design problem . In Proceedings of the 4th Meeting of the Nordic Section of the Mathematical Programming Society ( Arhus, Denmark, Aug. 16--18). Kim Allan Andersen ed., Univ. of Arhus, Department of Operations Research, Publications at the Departments of Mathematical Sciences. Working Papers 97-1 , pp. 62 -- 97 .]] Holmberg, K., and Yuan, D.1997. A Lagrangean heuristic-based branch-and-bound approach for the capacitated network design problem. In Proceedings of the 4th Meeting of the Nordic Section of the Mathematical Programming Society (Arhus, Denmark, Aug. 16--18). Kim Allan Andersen ed., Univ. of Arhus, Department of Operations Research, Publications at the Departments of Mathematical Sciences. Working Papers 97-1, pp. 62--97.]]"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(99)00004-8"},{"key":"e_1_2_1_24_1","first-page":"338","volume-title":"Proceedings of the 11th ACM\/SIAM Symposium on Discrete Algorithms (Jan.). ACM","author":"Konjevod G.","unstructured":"Konjevod , G. , and Ravi , R . 2000. An approximation algorithm for the covering Steiner problem . In Proceedings of the 11th ACM\/SIAM Symposium on Discrete Algorithms (Jan.). ACM , New York , pp. 338 -- 334 .]] Konjevod, G., and Ravi, R.2000. An approximation algorithm for the covering Steiner problem. In Proceedings of the 11th ACM\/SIAM Symposium on Discrete Algorithms (Jan.). ACM, New York, pp. 338--334.]]"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10038"},{"key":"e_1_2_1_26_1","first-page":"135","volume-title":"Proceedings of the 1st International Workshop (Approx-98)","author":"Kortsarz G.","unstructured":"Kortsarz , G. 1998. On the hardness of approximating spanners . In Proceedings of the 1st International Workshop (Approx-98) . pp. 135 -- 146 .]] Kortsarz, G.1998. On the hardness of approximating spanners. In Proceedings of the 1st International Workshop (Approx-98). pp. 135--146.]]"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00111-0"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Krumke S. O. Noltemeier H. Schwarz S. Wirth H.-C. and Ravi R.1998. Flow improvement and network flows with fixed costs. OR-98 Z\u00fcrich.]]  Krumke S. O. Noltemeier H. Schwarz S. Wirth H.-C. and Ravi R.1998. Flow improvement and network flows with fixed costs. OR-98 Z\u00fcrich.]]","DOI":"10.1007\/978-3-642-58409-1_15"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.15807\/jorsj.39.88"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759032"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90258-C"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.18.1.1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121090"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge Mass.]]   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge Mass.]]","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194266331"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579435"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523690"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1077464.1077470","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1077464.1077470","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:23:51Z","timestamp":1750267431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1077464.1077470"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,7]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,7]]}},"alternative-id":["10.1145\/1077464.1077470"],"URL":"https:\/\/doi.org\/10.1145\/1077464.1077470","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,7]]},"assertion":[{"value":"2005-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}