{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:17:52Z","timestamp":1750306672210,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2015,1,7]],"date-time":"2015-01-07T00:00:00Z","timestamp":1420588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["DO 749\/4"],"award-info":[{"award-number":["DO 749\/4"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2015,2,3]]},"abstract":"<jats:p>We consider the problem of generating randomized roundings that satisfy a single cardinality constraint and admit Chernoff-type large deviation bounds for weighted sums of the variables. That this can be done efficiently was proven by Srinivasan [2001], a different approach was later given by the first author [Doerr 2006]. In this work, we (a) present an improved version of the bitwise derandomization given by Doerr, (b) give the first derandomization of Srinivasan's tree-based randomized approach and prove its correctness, and (c) experimentally compare the resulting algorithms.<\/jats:p>\n          <jats:p>Our experiments show that adding a single cardinality constraint typically reduces the rounding errors and only moderately increases the running times. In general, our derandomization of the tree-based approach is superior to the derandomized bitwise one, while the two randomized versions produce very similar rounding errors. When implementing the derandomized tree-based approach, however, the choice of the tree is important.<\/jats:p>","DOI":"10.1145\/2594409","type":"journal-article","created":{"date-parts":[[2014,5,20]],"date-time":"2014-05-20T13:47:43Z","timestamp":1400593663000},"source":"Crossref","is-referenced-by-count":1,"title":["Randomized Rounding in the Presence of a Cardinality Constraint"],"prefix":"10.1145","volume":"19","author":[{"given":"Benjamin","family":"Doerr","sequence":"first","affiliation":[{"name":"Max--Planck--Institut f\u00fcr Informatik, Germany"}]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[{"name":"Max--Planck--Institut f\u00fcr Informatik, Germany"}]}],"member":"320","published-online":{"date-parts":[[2015,1,7]]},"reference":[{"volume-title":"Proceedings of the 7th International Conference on Integer Programming and Combinatorial Optimization (IPCO). 17--30","author":"Ageev A. A.","key":"e_1_2_1_1_1"},{"volume-title":"Proceedings of the 8th Annual European Symposium on Algorithms (ESA). 32--41","author":"Ageev A. A.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000038913.96607.c2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100271"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702417511"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1985.10478201"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.60"},{"volume-title":"Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1080--1097","author":"Chekuri C.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703422479"},{"volume-title":"Tech. Rep. 31, IBM Tech., Disclosure Bull.","year":"1989","author":"Ditlow G.","key":"e_1_2_1_10_1"},{"volume-title":"Fundamentals of Computation Theory","author":"Doerr B.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703430154"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_51"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_47"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"B. Doerr and M. Gnewuch. 2008. Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding. In Monte Carlo and Quasi-Monte Carlo Methods 2006 A. Keller S. Heinrich and H. Niederreiter Eds. Springer Berlin 299--312.  B. Doerr and M. Gnewuch. 2008. Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding. In Monte Carlo and Quasi-Monte Carlo Methods 2006 A. Keller S. Heinrich and H. Niederreiter Eds. Springer Berlin 299--312.","DOI":"10.1007\/978-3-540-74496-2_17"},{"volume-title":"Proceedings of the 13th Workshop on Algorithm Engineering and Experiments (ALENEX). 96--107","author":"Doerr B.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972894.16"},{"volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). 164--175","author":"Gandhi R.","key":"e_1_2_1_18_1"},{"volume-title":"Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS). 323--332","author":"Gandhi R.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147956"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00066-7"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d. 2005. Design and Analysis of Randomized Algorithms. Introduction to Design Paradigms. Texts in Theoretical Computer Science An EATCS Series Springer-Verlag Berlin.   J. Hromkovi\u010d. 2005. Design and Analysis of Randomized Algorithms. Introduction to Design Paradigms. Texts in Theoretical Computer Science An EATCS Series Springer-Verlag Berlin.","DOI":"10.1007\/3-540-27903-2"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.21"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1552285.1552289"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"D. L. Lau and G. R. Arce. 2008. Modern Digital Halftoning. CRC Press.   D. L. Lau and G. R. Arce. 2008. Modern Digital Halftoning. CRC Press.","DOI":"10.1201\/9781420047547"},{"key":"e_1_2_1_26_1","unstructured":"R. Motwani J. Naor and P. Raghavan. 1997. Randomized approximation algorithms in combinatorial optimization. In Approximation Algorithms for NP-hard Problems D. Hochbaum Ed. PWS Publishing Co. Boston MA 447--481.   R. Motwani J. Naor and P. Raghavan. 1997. Randomized approximation algorithms in combinatorial optimization. In Approximation Algorithms for NP-hard Problems D. Hochbaum Ed. PWS Publishing Co. Boston MA 447--481."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/27738.27741"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759035"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875563"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2594409","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2594409","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:00:52Z","timestamp":1750230052000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2594409"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,7]]},"references-count":31,"alternative-id":["10.1145\/2594409"],"URL":"https:\/\/doi.org\/10.1145\/2594409","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2015,1,7]]}}}