{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,12]],"date-time":"2026-10-12T20:32:30Z","timestamp":1791837150713,"version":"4.3.4"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["617951"],"award-info":[{"award-number":["617951"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.022.211"],"award-info":[{"award-number":["639.022.211"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.071.510"],"award-info":[{"award-number":["639.071.510"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["022.005.025"],"award-info":[{"award-number":["022.005.025"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most $t$ sets. We give an efficient algorithm that finds a coloring with discrepancy $O((t \\log n)^{1\/2})$, matching the best known nonconstructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an $O(t^{1\/2} \\log n)$ bound. The result also extends to the more general Koml\u00f3s setting and gives an algorithmic $O(\\log^{1\/2} n)$ bound.<\/jats:p>","DOI":"10.1137\/17m1126795","type":"journal-article","created":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T12:31:59Z","timestamp":1556627519000},"page":"534-553","source":"Crossref","is-referenced-by-count":14,"title":["An Algorithm for Koml\u00f3s Conjecture Matching Banaszczyk's Bound"],"prefix":"10.1137","volume":"48","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Dadush","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shashwat","family":"Garg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,4,30]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199807)12:4<351::AID-RSA3>3.0.CO;2-S"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"N. Bansal,\n                      Constructive algorithms for discrepancy minimization\n                      , in Foundations of Computer Science (FOCS), IEEE Computer Society, Low Alamitos, CA, 2010, pp. 3-10.","DOI":"10.1109\/FOCS.2010.7"},{"key":"atypb3","first-page":"55","author":"Bansal N.","year":"2014","journal-title":"Philadelphia"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90022-6"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"N. Bansal and S. Garg,\n                      Algorithmic discrepancy beyond partial coloring\n                      , in Proceedings of the 49th Annual ACM Symposium on Theory of Computing, STOC 2017, Montreal, ACM, New York. 2017, pp. 914-926.","DOI":"10.1145\/3055399.3055490"},{"key":"atypb6","unstructured":"N. Bansal and S. Garg,\n                      Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems\n                      , preprint, arXiv:1601.03311, 2016."},{"key":"atypb7","first-page":"375","author":"Bansal N.","year":"2016","journal-title":"Berlin"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000140"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"B. Chazelle,\n                      The Discrepancy Method: Randomness and Complexity\n                      , Cambridge University Press, Cambridge, 2000.","DOI":"10.1017\/CBO9780511626371"},{"key":"atypb10","first-page":"1607","author":"Charikar M.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"W. Chen, A. Srivastav, G. Travaglini, et al.\n                      A Panorama of Discrepancy Theory\n                      , Lexture Notes in Math. 2107, Springer, Cham, Switzerland, 2014.","DOI":"10.1007\/978-3-319-04696-9"},{"key":"atypb12","unstructured":"D. Dadush, S. Garg, S. Lovett, and A. Nikolov,\n                      Towards a constructive version of Banaszczyk's vector balancing theorem\n                      , in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Paris, K. Jansen, C. Mathieu, J. D. P. Rolim, and C. Umans, eds., 2016, LIPIcs 60, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Wadern, Germany, 2016."},{"key":"atypb13","unstructured":"E. Ezra and S. Lovett,\n                      On the Beck-Fiala Conjecture for Random Set Systems\n                      , preprint, arXiv:1511.00583, 2015."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996452"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"B. G\u00e4rtner and J. Matousek,\n                      Approximation Algorithms and Semidefinite Programming\n                      , Springer, Heidelberg, 2012.","DOI":"10.1007\/978-3-642-22015-9"},{"key":"atypb17","first-page":"258","author":"Harvey N. J. A.","year":"2014","journal-title":"Germany"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"S. Lovett and R. Meka,\n                      Constructive discrepancy minimization by walking on the edges\n                      , in Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 2012, pp. 61-67.","DOI":"10.1109\/FOCS.2012.23"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"A. Levy, H. Ramadas, and T. Rothvoss,\n                      Deterministic discrepancy minimization via the multiplicative weight update method\n                      , in Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 10328, Springer, Cham, Switzerland, 2017.","DOI":"10.1007\/978-3-319-59250-3_31"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(86)80041-5"},{"key":"atypb21","unstructured":"J. Matousek,\n                      Geometric Discrepancy: An Illustrated Guide\n                      , Springer Science, 2009."},{"key":"atypb22","unstructured":"A. Nikolov,\n                      The Koml\u00f3s conjecture holds for vector colorings\n                      , preprint, arXiv:1301.4039, 2013."},{"key":"atypb23","first-page":"324","author":"Nikolov A.","year":"2015","journal-title":"Philadelphia"},{"key":"atypb24","first-page":"351","author":"Nikolov A.","year":"2013","journal-title":"Philadelphia"},{"key":"atypb25","first-page":"356","author":"Rothvoss T.","year":"2012","journal-title":"Philadelphia"},{"key":"atypb26","first-page":"20","author":"Rothvoss T.","year":"2013","journal-title":"NJ"},{"key":"atypb27","first-page":"140","author":"Rothvoss T.","year":"2014","journal-title":"NJ"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1985-0784009-0"},{"key":"atypb29","first-page":"692","author":"Srinivasan A.","year":"1997","journal-title":"Philadelphia"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1126795","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:16:50Z","timestamp":1787339810000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1126795"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/17M1126795"],"URL":"https:\/\/doi.org\/10.1137\/17m1126795","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}