{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T17:17:14Z","timestamp":1768324634345,"version":"3.49.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2018,2,14]],"date-time":"2018-02-14T00:00:00Z","timestamp":1518566400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s10107-018-1244-x","type":"journal-article","created":{"date-parts":[[2018,2,14]],"date-time":"2018-02-14T02:38:46Z","timestamp":1518575926000},"page":"307-353","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Nearly linear-time packing and covering LP solvers"],"prefix":"10.1007","volume":"175","author":[{"given":"Zeyuan","family":"Allen-Zhu","sequence":"first","affiliation":[]},{"given":"Lorenzo","family":"Orecchia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,2,14]]},"reference":[{"key":"1244_CR1","doi-asserted-by":"crossref","unstructured":"Allen-Zhu, Z., Lee, Y.T., Orecchia, L.: Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver. In: SODA (2016)","DOI":"10.1137\/1.9781611974331.ch127"},{"key":"1244_CR2","unstructured":"Allen-Zhu, Z., Li, Y., Oliveira, R., Wigderson, A: Much faster algorithms for matrix scaling. In: FOCS, 2017. arXiv:1704.02315"},{"key":"1244_CR3","doi-asserted-by":"crossref","unstructured":"Allen-Zhu, Z., Liao, Z., Orecchia, L.: Spectral sparsification and regret minimization beyond multiplicative updates. In: STOC (2015)","DOI":"10.1145\/2746539.2746610"},{"key":"1244_CR4","doi-asserted-by":"crossref","unstructured":"Allen-Zhu, Z., Orecchia, L.: Using optimization to break the epsilon barrier: a faster and simpler width-independent algorithm for solving positive linear programs in parallel. In: SODA (2015)","DOI":"10.1137\/1.9781611973730.95"},{"key":"1244_CR5","unstructured":"Allen-Zhu, Z., Orecchia, L.: Linear coupling: an ultimate unification of gradient and mirror descent. In: ITCS (2017)"},{"key":"1244_CR6","unstructured":"Allen-Zhu, Z., Qu, Z., Richt\u00e1rik, P., Yuan, Y.: Even faster accelerated coordinate descent using non-uniform sampling. In: ICML (2016)"},{"key":"1244_CR7","doi-asserted-by":"publisher","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. Theory Comput. 8, 121\u2013164 (2012)","journal-title":"Theory Comput."},{"key":"1244_CR8","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Khandekar, R.: Stateless distributed gradient descent for positive linear programs. In: STOC (2008)","DOI":"10.1145\/1374376.1374476"},{"issue":"1","key":"1244_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2390176.2390179","volume":"9","author":"B Awerbuch","year":"2012","unstructured":"Awerbuch, B., Khandekar, R., Rao, S.: Distributed algorithms for multicommodity flow problems via approximate steepest descent framework. ACM Trans. Algorithms 9(1), 1\u201314 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"1244_CR10","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Byers, J.W., Raz, D.: Global optimization using local information with applications to flow control. In: Proceedings 38th Annual Symposium on Foundations of Computer Science, pp. 303\u2013312. IEEE Computer Society (1997)","DOI":"10.1109\/SFCS.1997.646119"},{"issue":"6","key":"1244_CR11","doi-asserted-by":"publisher","first-page":"1261","DOI":"10.1137\/S0097539700379383","volume":"33","author":"Y Bartal","year":"2004","unstructured":"Bartal, Y., Byers, J.W., Raz, D.: Fast, distributed approximation algorithms for positive linear programming with applications to flow control. SIAM J. Comput. 33(6), 1261\u20131279 (2004)","journal-title":"SIAM J. Comput."},{"key":"1244_CR12","unstructured":"Ben-Tal, A., Arkadi, N.: Lectures on modern convex optimization. Soc. Ind. Appl. Math. 315\u2013341 (2013)"},{"key":"1244_CR13","unstructured":"Bienstock, D., Iyengar, G.: Faster approximation algorithms for packing and covering problems. Technical report, Columbia University, September 2004. Preliminary version published in STOC \u201904"},{"key":"1244_CR14","unstructured":"Byers, J., Nasser, G.: Utility-based decision-making in wireless sensor networks. In: 2000 first annual workshop on mobile and ad hoc networking and computing, 2000. MobiHOC, pp. 143\u2013144. IEEE (2000)"},{"key":"1244_CR15","doi-asserted-by":"crossref","unstructured":"Chudak, F.A., Eleut\u00e9rio, V. : Improved approximation schemes for linear programming relaxations of combinatorial optimization problems. In: Proceedings of the 11th International IPCO Conference on Integer Programming and Combinatorial Optimization, pp. 81\u201396 (2005)","DOI":"10.1007\/11496915_7"},{"issue":"1","key":"1244_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2529989","volume":"61","author":"R Duan","year":"2014","unstructured":"Duan, R., Pettie, S.: Linear-time approximation for maximum weight matching. J. ACM 61(1), 1\u201323 (2014)","journal-title":"J. ACM"},{"issue":"4","key":"1244_CR17","doi-asserted-by":"publisher","first-page":"1997","DOI":"10.1137\/130949993","volume":"25","author":"O Fercoq","year":"2015","unstructured":"Fercoq, O., Richt\u00e1rik, P.: Accelerated, parallel and proximal coordinate descent. SIAM J. Optim. 25(4), 1997\u20132023 (2015)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"1244_CR18","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/S0895480199355754","volume":"13","author":"LK Fleischer","year":"2000","unstructured":"Fleischer, L.K.: Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discrete Math. 13(4), 505\u2013520 (2000)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"1244_CR19","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1137\/S0097539704446232","volume":"37","author":"N Garg","year":"2007","unstructured":"Garg, N., K\u00f6nemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput. 37(2), 630\u2013652 (2007)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1244_CR20","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1137\/0804004","volume":"4","author":"MD Grigoriadis","year":"1994","unstructured":"Grigoriadis, M.D., Khachiyan, L.G.: Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. Optim. 4(1), 86\u2013107 (1994)","journal-title":"SIAM J. Optim."},{"issue":"6","key":"1244_CR21","first-page":"30","volume":"58","author":"R Jain","year":"2011","unstructured":"Jain, R., Ji, Z., Upadhyay, S., Watrous, J.: QIP = PSPACE. J. ACM JACM 58(6), 30 (2011)","journal-title":"J. ACM JACM"},{"issue":"4","key":"1244_CR22","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1137\/12087222X","volume":"44","author":"P Klein","year":"2015","unstructured":"Klein, P., Young, N.E.: On the number of iterations for Dantzig\u2013Wolfe optimization and packing-covering approximation algorithms. SIAM J. Comput. 44(4), 1154\u20131172 (2015)","journal-title":"SIAM J. Comput."},{"key":"1244_CR23","first-page":"494","volume":"70","author":"C Koufogiannakis","year":"2013","unstructured":"Koufogiannakis, C., Young, N.E.: A nearly linear-time PTAS for explicit fractional packing and covering linear programs. Algorithmica 70, 494\u2013506 (2013). (Previously appeared in FOCS \u201907)","journal-title":"Algorithmica"},{"key":"1244_CR24","doi-asserted-by":"crossref","unstructured":"Luby, M., Nisan, N.: A parallel approximation algorithm for positive linear programming. In: STOC, pp. 448\u2013457. ACM Press, New York (1993)","DOI":"10.1145\/167088.167211"},{"key":"1244_CR25","doi-asserted-by":"crossref","unstructured":"Madry, A.: Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In: STOC. ACM Press, New York (2010)","DOI":"10.1145\/1806689.1806708"},{"issue":"1","key":"1244_CR26","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1137\/S1052623403425629","volume":"15","author":"A Nemirovski","year":"2004","unstructured":"Nemirovski, A.: Prox-method with rate of convergence $$O(1\/t)$$ O ( 1 \/ t ) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15(1), 229\u2013251 (2004)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1244_CR27","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1080\/10556780701550059","volume":"23","author":"Y Nesterov","year":"2008","unstructured":"Nesterov, Y.: Rounding of convex sets and efficient gradient methods for linear programming problems. Optim. Methods Softw. 23(1), 109\u2013128 (2008)","journal-title":"Optim. Methods Softw."},{"key":"1244_CR28","first-page":"543","volume":"269","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method of solving a convex programming problem with convergence rate $$O(1\/k^2)$$ O ( 1 \/ k 2 ) . Sov. Math. Dokl. 269, 543\u2013547 (1983)","journal-title":"Sov. Math. Dokl."},{"issue":"1","key":"1244_CR29","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","volume":"103","author":"Y Nesterov","year":"2005","unstructured":"Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103(1), 127\u2013152 (2005)","journal-title":"Math. Program."},{"issue":"2","key":"1244_CR30","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/100802001","volume":"22","author":"Y Nesterov","year":"2012","unstructured":"Nesterov, Y.: Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J Optim. 22(2), 341\u2013362 (2012)","journal-title":"SIAM J Optim."},{"issue":"2","key":"1244_CR31","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"SA Plotkin","year":"1995","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20(2), 257\u2013301 (1995). (conference version published in FOCS 1991)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1244_CR32","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/PL00009209","volume":"21","author":"L Trevisan","year":"1998","unstructured":"Trevisan, L.: Parallel approximation algorithms by positive linear programming. Algorithmica 21(1), 72\u201388 (1998)","journal-title":"Algorithmica"},{"key":"1244_CR33","unstructured":"Wang, D., Mahoney, M., Mohan, N., Rao, S.: Faster parallel solver for positive linear programs via dynamically-bucketed selective coordinate descent. ArXiv e-prints arXiv:1511.06468 (2015)"},{"key":"1244_CR34","unstructured":"Wang, D., Rao, S., Mahoney, M.W.: Unified acceleration method for packing and covering problems via diameter reduction. In: ICALP (2016)"},{"key":"1244_CR35","doi-asserted-by":"crossref","unstructured":"Young, N.E.: Sequential and parallel algorithms for mixed packing and covering. In: 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201901), pp. 538\u2013546. IEEE Computer Society (2001)","DOI":"10.1109\/SFCS.2001.959930"},{"key":"1244_CR36","unstructured":"Young, N.E.: Nearly linear-time approximation schemes for mixed packing\/covering and facility-location linear programs. ArXiv e-prints arXiv:1407.3015 (2014)"},{"key":"1244_CR37","doi-asserted-by":"crossref","unstructured":"Zurel, E., Nisan, N.: An efficient approximate allocation algorithm for combinatorial auctions. In: Proceedings of the 3rd ACM Conference on Electronic Commerce, pp. 125\u2013136. ACM (2001)","DOI":"10.1145\/501158.501172"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-018-1244-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1244-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1244-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T20:33:06Z","timestamp":1751401986000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-018-1244-x"}},"subtitle":["Achieving width-independence and -convergence"],"short-title":[],"issued":{"date-parts":[[2018,2,14]]},"references-count":37,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["1244"],"URL":"https:\/\/doi.org\/10.1007\/s10107-018-1244-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,14]]},"assertion":[{"value":"8 August 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 February 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}