{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T14:43:33Z","timestamp":1780065813605,"version":"3.54.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,3,6]],"date-time":"2018-03-06T00:00:00Z","timestamp":1520294400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Adobe Inc"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 1010789 and CCF 1422569"],"award-info":[{"award-number":["CNS 1010789 and CCF 1422569"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004442","name":"National Science Centre","doi-asserted-by":"crossref","award":["NCN 2015\/18\/E\/ST6\/00456 and NCN 2012\/07\/N\/ST6\/03068"],"award-info":[{"award-number":["NCN 2015\/18\/E\/ST6\/00456 and NCN 2012\/07\/N\/ST6\/03068"]}],"id":[{"id":"10.13039\/501100004442","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,4,30]]},"abstract":"<jats:p>\n                    Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to negative correlation properties. However, what if an application naturally calls for dependent rounding on the one hand and desires positive correlation on the other? More generally, we develop algorithms that guarantee the known properties of dependent rounding but also have nearly bestpossible behavior\u2014near-independence, which generalizes positive correlation\u2014on \u201csmall\u201d subsets of the variables. The recent breakthrough of Li and Svensson for the classical\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -median problem has to handle positive correlation in certain dependent rounding settings, and does so implicitly. We improve upon Li-Svensson\u2019s approximation ratio for\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -median from 2.732 + \u03f5 to 2.675 + \u03f5 by developing an algorithm that improves upon various aspects of their work. Our dependent rounding approach helps us improve the dependence of the runtime on the parameter \u03f5 from Li-Svensson\u2019s\n                    <jats:italic toggle=\"yes\">N<\/jats:italic>\n                    <jats:sup>\n                      <jats:italic toggle=\"yes\">O<\/jats:italic>\n                      (1\/\u03f5\n                      <jats:sup>2<\/jats:sup>\n                      )\n                    <\/jats:sup>\n                    to\n                    <jats:italic toggle=\"yes\">N<\/jats:italic>\n                    <jats:sup>\n                      <jats:italic toggle=\"yes\">O<\/jats:italic>\n                      ((1\/\u03f5)log(1\/\u03f5))\n                    <\/jats:sup>\n                    .\n                  <\/jats:p>","DOI":"10.1145\/2981561","type":"journal-article","created":{"date-parts":[[2017,3,7]],"date-time":"2017-03-07T14:12:04Z","timestamp":1488895924000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":71,"title":["An Improved Approximation for\n                    <i>k<\/i>\n                    -Median and Positive Correlation in Budgeted Optimization"],"prefix":"10.1145","volume":"13","author":[{"given":"Jaros\u0142aw","family":"Byrka","sequence":"first","affiliation":[{"name":"University of Wroc\u0142aw, Wroc\u0142aw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Pensyl","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Room, MD"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bartosz","family":"Rybicki","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw, Wroc\u0142aw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Room, MD"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Khoa","family":"Trinh","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Room, MD"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,3,6]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000038913.96607.c2"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07557-0_5"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416402"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2220253.2220257"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722179"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1695"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301257"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133118"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634198"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703422479"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007772"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/297201.297202"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.06.004"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147956"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480192243516"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634143"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950621"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510012"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000095"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0380-8"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488723"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930200021"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993716"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875563"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1971947"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545448"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2981561","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2981561","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2981561","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:35:39Z","timestamp":1763458539000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2981561"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,6]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4,30]]}},"alternative-id":["10.1145\/2981561"],"URL":"https:\/\/doi.org\/10.1145\/2981561","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,6]]},"assertion":[{"value":"2015-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}