{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T04:42:17Z","timestamp":1725856937625},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319334608"},{"type":"electronic","value":"9783319334615"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-33461-5_31","type":"book-chapter","created":{"date-parts":[[2016,5,24]],"date-time":"2016-05-24T22:35:59Z","timestamp":1464129359000},"page":"375-386","source":"Crossref","is-referenced-by-count":4,"title":["Approximation-Friendly Discrepancy Rounding"],"prefix":"10.1007","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,5,25]]},"reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Bansal, N.: Constructive algorithms for discrepancy minimization. In: Foundations of Computer Science (FOCS), pp. 3\u201310 (2010)","DOI":"10.1109\/FOCS.2010.7"},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Charikar, M., Krishnaswamy, R., Li, S.: Better algorithms and hardness for broadcast scheduling via a discrepancy approach. In: SODA, pp. 55\u201371 (2014)","DOI":"10.1137\/1.9781611973402.5"},{"issue":"1\u20132","key":"31_CR3","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/s10107-012-0537-8","volume":"141","author":"N Bansal","year":"2013","unstructured":"Bansal, N., Khandekar, R., K\u00f6nemann, J., Nagarajan, V., Peis, B.: On generalizations of network design problems with degree bounds. Math. Program. 141(1\u20132), 479\u2013506 (2013)","journal-title":"Math. Program."},{"key":"31_CR4","unstructured":"Bansal, N., Nagarajan, V.: Approximation-friendly discrepancy rounding. CoRR abs\/1512.02254 (2015)"},{"key":"31_CR5","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.: Integer-making theorems. Discrete Appl. Math. 3, 1\u20138 (1981)","journal-title":"Discrete Appl. Math."},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"Charikar, M., Newman, A., Nikolov, A.: Tight hardness results for minimizing discrepancy. In: SODA, pp. 1607\u20131614 (2011)","DOI":"10.1137\/1.9781611973082.124"},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondrak, J., Zenklusen, R.: Dependent randomized rounding via exchange properties of combinatorial structures. In: FOCS, pp. 575\u2013584 (2010)","DOI":"10.1109\/FOCS.2010.60"},{"issue":"1\u20132","key":"31_CR8","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/s10107-013-0703-7","volume":"146","author":"F Grandoni","year":"2014","unstructured":"Grandoni, F., Ravi, R., Singh, M., Zenklusen, R.: New approaches to multi-objective optimization. Math. Program. 146(1\u20132), 525\u2013554 (2014)","journal-title":"Math. Program."},{"key":"31_CR9","unstructured":"Harvey, N.J.A., Schwartz, R., Singh, M.: Discrepancy without partial colorings. In: APPROX\/RANDOM 2014, pp. 258\u2013273 (2014)"},{"key":"31_CR10","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF01840353","volume":"2","author":"RM Karp","year":"1987","unstructured":"Karp, R.M., Leighton, F.T., Rivest, R.L., Thompson, C.D., Vazirani, U.V., Vazirani, V.V.: Global wire routing in two-dimensional arrays. Algorithmica 2, 113\u2013129 (1987)","journal-title":"Algorithmica"},{"key":"31_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/978-3-540-68891-4_18","volume-title":"Integer Programming and Combinatorial Optimization","author":"T Kir\u00e1ly","year":"2008","unstructured":"Kir\u00e1ly, T., Lau, L.C., Singh, M.: Degree bounded matroids and submodular flows. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol. 5035, pp. 259\u2013272. Springer, Heidelberg (2008)"},{"key":"31_CR12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511977152","volume-title":"Iterative Methods in Combinatorial Optimization","author":"LC Lau","year":"2011","unstructured":"Lau, L.C., Ravi, R., Singh, M.: Iterative Methods in Combinatorial Optimization. Cambridge University Press, Cambridge (2011)"},{"issue":"2","key":"31_CR13","doi-asserted-by":"crossref","first-page":"626","DOI":"10.1137\/S0097539700379760","volume":"31","author":"FT Leighton","year":"2001","unstructured":"Leighton, F.T., Lu, C., Rao, S., Srinivasan, A.: New algorithmic aspects of the local lemma with applications to routing and partitioning. SIAM J. Comput. 31(2), 626\u2013641 (2001)","journal-title":"SIAM J. Comput."},{"key":"31_CR14","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/S0195-6698(86)80041-5","volume":"7","author":"L Lovasz","year":"1986","unstructured":"Lovasz, L., Spencer, J., Vesztergombi, K.: Discrepancy of set-systems and matrices. Eur. J. Combin. 7, 151\u2013160 (1986)","journal-title":"Eur. J. Combin."},{"key":"31_CR15","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_CR16","volume-title":"Geometric Discrepancy: An Illustrated Guide","author":"J Matou\u0161ek","year":"2010","unstructured":"Matou\u0161ek, J.: Geometric Discrepancy: An Illustrated Guide. Springer, Heidelberg (2010)"},{"key":"31_CR17","doi-asserted-by":"crossref","unstructured":"Nikolov, A., Talwar, K.: Approximating hereditary discrepancy via small width ellipsoids. In: Symposium on Discrete Algorithms, SODA, pp. 324\u2013336 (2015)","DOI":"10.1137\/1.9781611973730.24"},{"key":"31_CR18","doi-asserted-by":"crossref","unstructured":"Rothvoss, T.: Approximating bin packing within o(log OPT * log log OPT) bins. In: FOCS, pp. 20\u201329 (2013)","DOI":"10.1109\/FOCS.2013.11"},{"key":"31_CR19","doi-asserted-by":"crossref","unstructured":"Rothvoss, T.: Constructive discrepancy minimization for convex sets. In: IEEE Symposium on Foundations of Computer Science, FOCS, pp. 140\u2013145 (2014)","DOI":"10.1109\/FOCS.2014.23"},{"key":"31_CR20","doi-asserted-by":"crossref","unstructured":"Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: STOC, pp. 661\u2013670 (2007)","DOI":"10.1145\/1250790.1250887"},{"issue":"2","key":"31_CR21","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_CR22","unstructured":"Srinivasan, A.: Improving the discrepancy bound for sparse matrices: better approximations for sparse lattice approximation problems. In: Symposium on Discrete Algorithms (SODA), pp. 692\u2013701 (1997)"},{"key":"31_CR23","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer-Verlag, Heidelberg (2001)"},{"key":"31_CR24","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"D Williamson","year":"2011","unstructured":"Williamson, D., Shmoys, D.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"}],"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-33461-5_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T14:52:00Z","timestamp":1498315920000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-33461-5_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319334608","9783319334615"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-33461-5_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}