{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T09:33:54Z","timestamp":1763544834811},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319592497"},{"type":"electronic","value":"9783319592503"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-59250-3_31","type":"book-chapter","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T13:04:39Z","timestamp":1495544679000},"page":"380-391","source":"Crossref","is-referenced-by-count":13,"title":["Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method"],"prefix":"10.1007","author":[{"given":"Avi","family":"Levy","sequence":"first","affiliation":[]},{"given":"Harishchandra","family":"Ramadas","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Rothvoss","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"issue":"6","key":"31_CR1","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theor. Comput. 8(6), 121\u2013164 (2012)","journal-title":"Theor. Comput."},{"key":"31_CR2","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","doi-asserted-by":"crossref","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method","author":"N Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization, 3rd edn. John Wiley & Sons Inc., Hoboken (2008). With an appendix on the life and work of Paul Erd\u0151s","edition":"3"},{"issue":"4","key":"31_CR3","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1002\/(SICI)1098-2418(199807)12:4<351::AID-RSA3>3.0.CO;2-S","volume":"12","author":"W Banaszczyk","year":"1998","unstructured":"Banaszczyk, W.: Balancing vectors and Gaussian measures of $$n$$ -dimensional convex bodies. Random Struct. Algorithms 12(4), 351\u2013360 (1998)","journal-title":"Random Struct. Algorithms"},{"key":"31_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N.: Constructive algorithms for discrepancy minimization. In: FOCS, pp. 3\u201310 (2010)","DOI":"10.1109\/FOCS.2010.7"},{"key":"31_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Dadush, D., Garg, S: An algorithm for koml\u00f3s conjecture matching banaszczyk\u2019s bound. CoRR, abs\/1605.02882 (2016)","DOI":"10.1109\/FOCS.2016.89"},{"issue":"4","key":"31_CR6","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/BF02579452","volume":"1","author":"J Beck","year":"1981","unstructured":"Beck, J.: Roth\u2019s estimate of the discrepancy of integer sequences is nearly sharp. Combinatorica 1(4), 319\u2013325 (1981)","journal-title":"Combinatorica"},{"issue":"1","key":"31_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(81)90022-6","volume":"3","author":"J Beck","year":"1981","unstructured":"Beck, J., Fiala, T.: \u201cInteger-making\" theorems. Discrete Appl. Math. 3(1), 1\u20138 (1981)","journal-title":"Discrete Appl. Math."},{"key":"31_CR8","series-title":"Graduate Texts in Mathematics","volume-title":"Matrix Analysis","author":"B Rajendra","year":"1997","unstructured":"Rajendra, B.: Matrix Analysis. Graduate Texts in Mathematics. Springer, New York (1997)"},{"issue":"2","key":"31_CR9","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1002\/rsa.3240010208","volume":"1","author":"G Bohus","year":"1990","unstructured":"Bohus, G.: On the discrepancy of 3 permutations. Random Struct. Algorithms 1(2), 215\u2013220 (1990)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"31_CR10","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s00453-012-9728-1","volume":"67","author":"N Bansal","year":"2013","unstructured":"Bansal, N., Spencer, J.: Deterministic discrepancy minimization. Algorithmica 67(4), 451\u2013471 (2013)","journal-title":"Algorithmica"},{"key":"31_CR11","volume-title":"The Discrepancy Method - Randomness and Complexity","author":"B Chazelle","year":"2001","unstructured":"Chazelle, B.: The Discrepancy Method - Randomness and Complexity. University Press, Cambridge (2001)"},{"issue":"3","key":"31_CR12","doi-asserted-by":"crossref","first-page":"225","DOI":"10.4064\/sm-122-3-225-234","volume":"122","author":"A Giannopoulos","year":"1997","unstructured":"Giannopoulos, A.: On some vector balancing problems. Stud. Math. 122(3), 225\u2013234 (1997)","journal-title":"Stud. Math."},{"issue":"1","key":"31_CR13","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1070\/SM1989v064n01ABEH003295","volume":"64","author":"ED Gluskin","year":"1989","unstructured":"Gluskin, E.D.: Extremal properties of orthogonal parallelepipeds and their applications to the geometry of banach spaces. Math. USSR Sb. 64(1), 85 (1989)","journal-title":"Math. USSR Sb."},{"key":"31_CR14","doi-asserted-by":"crossref","unstructured":"Lovett, S., Meka, R.: Constructive discrepancy minimization by walking on the edges. In: FOCS, pp. 61\u201367 (2012)","DOI":"10.1109\/FOCS.2012.23"},{"key":"31_CR15","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-03942-3","volume-title":"Geometric Discrepancy","author":"J Matou\u0161ek","year":"1999","unstructured":"Matou\u0161ek, J.: Geometric Discrepancy. Algorithms and Combinatorics. Springer, Berlin (1999). An illustrated guide"},{"key":"31_CR16","unstructured":"Marcus, A., Spielman, D.A., Srivastava, N.: Interlacing families, I.I.: mixed characteristic polynomials and the Kadison-singer problem. arXiv e-prints, June 2013"},{"key":"31_CR17","unstructured":"Nikolov, A.: The komlos conjecture holds for vector colorings. arXiv e-prints, Jan 2013"},{"key":"31_CR18","doi-asserted-by":"crossref","unstructured":"Newman, A., Neiman, O., Nikolov, A.: Beck\u2019s three permutations conjecture: a counterexample and some consequences. In: FOCS, pp. 253\u2013262 (2012)","DOI":"10.1109\/FOCS.2012.84"},{"issue":"1","key":"31_CR19","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/0095-8956(77)90057-0","volume":"23","author":"J Spencer","year":"1977","unstructured":"Spencer, J.: Balancing games. J. Comb. Theor. Ser. B 23(1), 68\u201374 (1977)","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"2","key":"31_CR20","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1090\/S0002-9947-1985-0784009-0","volume":"289","author":"J Spencer","year":"1985","unstructured":"Spencer, J.: Six standard deviations suffice. Trans. Am. Math. Soc. 289(2), 679\u2013706 (1985)","journal-title":"Trans. Am. Math. Soc."},{"key":"31_CR21","unstructured":"Srinivasan, A.: Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems. In: SODA 1997, ACM SIGACT, SIAM, Philadelphia, PA, pp. 692\u2013701 (1997)"},{"key":"31_CR22","unstructured":"Spencer, J.H., Srinivasan, A., Tetali, P.: The discrepancy of permutation families. Unpublished manuscript"},{"key":"31_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1007\/978-3-642-31594-7_71","volume-title":"Automata, Languages, and Programming","author":"A Zouzias","year":"2012","unstructured":"Zouzias, A.: A Matrix hyperbolic cosine algorithm and applications. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 846\u2013858. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-31594-7_71"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59250-3_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T23:50:14Z","timestamp":1569369014000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59250-3_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319592497","9783319592503"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59250-3_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}