{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:14Z","timestamp":1759637834004,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,8,3]],"date-time":"2016-08-03T00:00:00Z","timestamp":1470182400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["327620-09"],"award-info":[{"award-number":["327620-09"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Ontario Early Researcher Award"},{"name":"NSERC Discovery Accelerator Supplement Award"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,9,2]]},"abstract":"<jats:p>\n            We consider the\n            <jats:italic>matroid median<\/jats:italic>\n            problem [Krishnaswamy et al. 2011], wherein we are given a set of facilities with opening costs and a matroid on the facility-set, and clients with demands and connection costs, and we seek to open an independent set of facilities and assign clients to open facilities so as to minimize the sum of the facility-opening and client-connection costs. We give a simple 8-approximation algorithm for this problem based on LP-rounding, which improves upon the 16-approximation in Krishnaswamy et al. [2011]. We illustrate the power and versatility of our techniques by deriving (a) an 8-approximation for the\n            <jats:italic>two-matroid median<\/jats:italic>\n            problem, a generalization of matroid median that we introduce involving two matroids; and (b) a 24-approximation algorithm for\n            <jats:italic>matroid median with penalties<\/jats:italic>\n            , which is a vast improvement over the 360-approximation obtained in Krishnaswamy et al. [2011]. We show that a variety of seemingly disparate facility-location problems considered in the literature\u2014data placement problem, mobile facility location,\n            <jats:italic>k<\/jats:italic>\n            -median forest, metric uniform minimum-latency Uncapacitated Facility Location (UFL)\u2014in fact reduce to the matroid median or two-matroid median problems, and thus obtain\n            <jats:italic>improved<\/jats:italic>\n            approximation guarantees for all these problems. Our techniques also yield an improvement for the knapsack median problem.\n          <\/jats:p>","DOI":"10.1145\/2963170","type":"journal-article","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T13:26:34Z","timestamp":1470317194000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications"],"prefix":"10.1145","volume":"12","author":[{"given":"Chaitanya","family":"Swamy","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}]}],"member":"320","published-online":{"date-parts":[[2016,8,3]]},"reference":[{"volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1607--1621","author":"Ahmadian S.","key":"e_1_2_1_1_1"},{"volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901)","author":"Baev I.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/080715421"},{"volume-title":"Proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization (IPCO). 92--103","author":"Chakrabarty D.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1882"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_17"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703405754"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"W. Cook W. Cunningham W. Pulleyblank and A. Schrijver. 1998. Combinatorial Optimization. John Wiley and Sons Inc. New York.   W. Cook W. Cunningham W. Pulleyblank and A. Schrijver. 1998. Combinatorial Optimization. John Wiley and Sons Inc. New York.","DOI":"10.1002\/9781118033142"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1978782.1978783"},{"volume-title":"Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX). 230--241","author":"G\u00f8rtz I.","key":"e_1_2_1_10_1"},{"volume-title":"Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1117--1130","author":"Krishnaswamy R.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095182"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258600"},{"volume-title":"Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX). 403--418","year":"2014","author":"Swamy C.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1383369.1383382"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2963170","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2963170","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:04Z","timestamp":1750222444000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2963170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,3]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,9,2]]}},"alternative-id":["10.1145\/2963170"],"URL":"https:\/\/doi.org\/10.1145\/2963170","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2016,8,3]]},"assertion":[{"value":"2015-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}