{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:42Z","timestamp":1750306122850,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,7,13]],"date-time":"2017-07-13T00:00:00Z","timestamp":1499904000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1464239, 1218620 and 1540547"],"award-info":[{"award-number":["1464239, 1218620 and 1540547"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,7,31]]},"abstract":"<jats:p>\n            In the Steiner\n            <jats:italic>k<\/jats:italic>\n            -Forest problem, we are given an edge weighted graph, a collection\n            <jats:italic>D<\/jats:italic>\n            of node pairs, and an integer\n            <jats:italic>k<\/jats:italic>\n            \u2a7d |\n            <jats:italic>D<\/jats:italic>\n            |. The goal is to find a min-weight subgraph that connects at least\n            <jats:italic>k<\/jats:italic>\n            pairs. The best known ratio for this problem is min {\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            ),\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>k<\/jats:italic>\n            )} [Gupta et al. 2010]. In Gupta et al. [2010], it is also shown that ratio \u03c1 for Steiner\n            <jats:italic>k<\/jats:italic>\n            -Forest implies ratio\n            <jats:italic>O<\/jats:italic>\n            (\u03c1 \u00b7 log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) for the related Dial-a-Ride problem. The only other algorithm known for Dial-a-Ride, besides the one resulting from Gupta et al. [2010], has ratio\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            ) [Charikar and Raghavachari 1998].\n          <\/jats:p>\n          <jats:p>\n            We obtain approximation ratio\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>0.448<\/jats:sup>\n            for Steiner\n            <jats:italic>k<\/jats:italic>\n            -Forest and Dial-a-Ride with unit weights, breaking the\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            ) approximation barrier for this natural case. We also show that if the maximum edge-weight is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03f5<\/jats:sup>\n            ), then one can achieve ratio\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>(1 + \u03f5) \u00b7 0.448<\/jats:sup>\n            ), which is less than \u221a\n            <jats:italic>n<\/jats:italic>\n            if \u03f5 is small enough. The improvement for Dial-a-Ride is the first progress for this problem in 15 years. To prove our main result, we consider the following generalization of the Minimum\n            <jats:italic>k<\/jats:italic>\n            -Edge Subgraph (M\n            <jats:italic>k<\/jats:italic>\n            -ES) problem, which we call Min-Cost \u2113-Edge-Profit Subgraph (MC\u2113-EPS): Given a graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) with edge-profits\n            <jats:italic>p<\/jats:italic>\n            = {\n            <jats:italic>\n              p\n              <jats:sub>e<\/jats:sub>\n            <\/jats:italic>\n            :\n            <jats:italic>e<\/jats:italic>\n            \u2208\n            <jats:italic>E<\/jats:italic>\n            } and node-costs\n            <jats:italic>c<\/jats:italic>\n            = {\n            <jats:italic>\n              c\n              <jats:sub>v<\/jats:sub>\n            <\/jats:italic>\n            :\n            <jats:italic>v<\/jats:italic>\n            \u2208\n            <jats:italic>V<\/jats:italic>\n            }, and a lower profit bound \u2113, find a minimum node-cost subgraph of\n            <jats:italic>G<\/jats:italic>\n            of edge-profit at least \u2113. The M\n            <jats:italic>k<\/jats:italic>\n            -ES problem is a special case of MC\u2113-EPS with unit node costs and unit edge profits. The currently best known ratio for M\n            <jats:italic>k<\/jats:italic>\n            -ES is\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3-2\u221a2 + \u03f5<\/jats:sup>\n            [Chlamtac et al. 2012]. We extend this ratio to MC\u2113-EPS for general node costs and profits bounded by a polynomial in\n            <jats:italic>n<\/jats:italic>\n            , which may be of independent interest.\n          <\/jats:p>","DOI":"10.1145\/3077581","type":"journal-article","created":{"date-parts":[[2017,7,13]],"date-time":"2017-07-13T13:44:03Z","timestamp":1499953443000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Improved Approximation Algorithm for Steiner\n            <i>k<\/i>\n            -Forest with Nearly Uniform Weights"],"prefix":"10.1145","volume":"13","author":[{"given":"Michael","family":"Dinitz","sequence":"first","affiliation":[{"name":"Johns Hopkins University, Baltimore, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[{"name":"Rutgers University, Camden, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zeev","family":"Nutov","sequence":"additional","affiliation":[{"name":"The Open University of Israel, Raanana, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,7,13]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1137\/S0097539792236237"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1007\/BF02189308"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/4221.4227"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/1109557.1109627"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/1806689.1806719"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/2432622.2432628"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1109\/SFCS.1998.743496"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1109\/FOCS.2012.61"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1137\/S0097539703422479"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1007\/s004530010050"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1016\/j.jcss.2011.05.009"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1016\/j.jcss.2005.06.004"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/1060590.1060650"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/1721837.1721857"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/1109557.1109626"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1109\/SFCS.1993.366818"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3077581","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3077581","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3077581","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:49Z","timestamp":1750217809000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3077581"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,13]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7,31]]}},"alternative-id":["10.1145\/3077581"],"URL":"https:\/\/doi.org\/10.1145\/3077581","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2017,7,13]]},"assertion":[{"value":"2015-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}