{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:35:38Z","timestamp":1774946138803,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1995,7,1]],"date-time":"1995-07-01T00:00:00Z","timestamp":804556800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1995,7]]},"DOI":"10.1007\/bf01585561","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T08:42:17Z","timestamp":1114677737000},"page":"269-309","source":"Crossref","is-referenced-by-count":37,"title":["About strongly polynomial time algorithms for quadratic optimization over submodular constraints"],"prefix":"10.1007","volume":"69","author":[{"given":"Dorit S.","family":"Hochbaum","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sung-Pil","family":"Hong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"805","DOI":"10.1109\/59.65909","volume":"5","author":"R. Baldick","year":"1990","unstructured":"R. Baldick and F.F. Wu, \u201cEfficient integer optimization algorithms for optimal coordination of capacitators and regulators,\u201dIEEE Transactions on Power Systems 5 (1990) 805\u2013812.","journal-title":"IEEE Transactions on Power Systems"},{"key":"CR2","unstructured":"M.J. Best and R.Y. Tan, \u201cAn O(n 2 logn) strongly polynomial algorithm for quadratic program with two equations and lower and upper bounds,\u201d Research Report CORR 90-04, Department of Combinatorics and Optimization, University of Waterloo (1990)."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1972","unstructured":"M. Blum, R.W. Floyd, V.R. Pratt, R.L. Rivest and R.E. Tarjan, \u201cTime bounds for selection,\u201dJournal of Computer and Systems Sciences 7 (1972) 448\u2013461.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0167-6377(84)90010-5","volume":"3","author":"P. Brucker","year":"1984","unstructured":"P. Brucker, \u201cAn O(n) algorithm for quadratic knapsack problems,\u201dOperations Research Letters 3 (1984) 163\u2013166.","journal-title":"Operations Research Letters"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BF01582230","volume":"34","author":"W. Cook","year":"1986","unstructured":"W. Cook, A.M.H. Gerards, A. Schrijver and E. Tardos, \u201cSensitivity results in integer linear programming,\u201dMathematical Programming 34 (1986) 251\u2013264.","journal-title":"Mathematical Programming"},{"issue":"1","key":"CR6","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1287\/moor.19.1.94","volume":"19","author":"S. Cosares","year":"1994","unstructured":"S. Cosares and D.S. Hochbaum, \u201cStrongly polynomial algorithms for the quadratic transportation problem with fixed number of sources,\u201dMathematics of Operations Research 19(1) (1994) 94\u2013111.","journal-title":"Mathematics of Operations Research"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0166-218X(90)90098-W","volume":"26","author":"M.E. Dyer","year":"1990","unstructured":"M.E. Dyer and A.M. Frieze, \u201cOn an optimization problem with nested constraints,\u201dDiscrete Applied Mathematics 26 (1990) 159\u2013173.","journal-title":"Discrete Applied Mathematics"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0022-0000(82)90048-4","volume":"24","author":"G.N. Frederickson","year":"1982","unstructured":"G.N. Frederickson and D.B. Johnson, \u201cThe complexity of selection and ranking inX+Y and matrices with sorted columns,\u201dJournal of Computer and Systems Sciences 24 (1982) 197\u2013208.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1287\/moor.5.2.186","volume":"5","author":"S. Fujishige","year":"1980","unstructured":"S. Fujishige, \u201cLexicographically optimal base of a polymatroid with respect to a weight vector,\u201dMathematics of Operations Research 5 (1980) 186\u2013196.","journal-title":"Mathematics of Operations Research"},{"key":"CR10","volume-title":"Submodular Functions and Optimization, Annals of Discrete Mathematics 47","author":"S. Fujishige","year":"1991","unstructured":"S. Fujishige,Submodular Functions and Optimization, Annals of Discrete Mathematics 47 (North-Holland, Amsterdam, 1991)."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H.N. Gabow","year":"1985","unstructured":"H.N. Gabow and R.E. Tarjan, \u201cA linear-time algorithm for a special case of disjoint set union,\u201dJournal of Computer and System Sciences 30 (1985) 209\u2013221.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G. Gallo","year":"1989","unstructured":"G. Gallo, M.E. Grigoriadis and R.E. Tarjan, \u201cA fast parametric maximum flow algorithm and applications,\u201dSIAM Journal of Computing 18 (1989) 30\u201355.","journal-title":"SIAM Journal of Computing"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"A.V. Goldberg and R.E. Tarjan, \u201cA new approach to the maximum flow problem,\u201d in:Proceedings of the 18th Annual ACM Symposium on Theory of Computing (1986) pp. 136\u2013146.","DOI":"10.1145\/12130.12144"},{"key":"CR14","unstructured":"F. Granot and J. Skorin-Kapov, \u201cSome proximity and sensitivity results in quadratic integer programming,\u201d Working Paper No. 1207, University of British Columbia (1986)."},{"key":"CR15","unstructured":"F. Granot and J. Skorin-Kapov, \u201cStrongly polynomial solvability of a nonseparable quadratic integer program with applications to toxic waste disposal,\u201d Manuscript (1990)."},{"key":"CR16","unstructured":"H. Groenevelt, \u201cTwo algorithms for maximizing a separable concave function over a polymatroidal feasible region,\u201d Technical Report, The Graduate School of Management, University of Rochester (1985)."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1287\/moor.19.2.390","volume":"19","author":"D.S. Hochbaum","year":"1994","unstructured":"D.S. Hochbaum, \u201cOn the impossibility of strongly polynomial algorithms for the allocation problem and its extensions,\u201d in:Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference (1990) pp. 261\u2013274; D.S. Hochbaum, \u201cLower and upper bounds for the allocation problem and other nonlinear optimization problems,\u201dMathematics of Operations Research 19 (1994) 390\u2013409.","journal-title":"Mathematics of Operations Research"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1145\/96559.96597","volume":"37","author":"D.S. Hochbaum","year":"1990","unstructured":"D.S. Hochbaum and J.G. Shanthikumar, \u201cConvex separable optimization is not much harder than linear optimization,\u201dJournal of ACM 37 (1990) 843\u2013862.","journal-title":"Journal of ACM"},{"issue":"3","key":"CR19","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF01581207","volume":"55","author":"D.S. Hochbaum","year":"1992","unstructured":"D.S. Hochbaum, R. Shamir and J.G. Shanthikumar, \u201cA polynomial algorithm for an integer quadratic nonseparable transportation problem,\u201dMathematical Programming 55(3) (1992) 359\u2013372.","journal-title":"Mathematical Programming"},{"key":"CR20","volume-title":"Resource Allocation Problems: Algorithmic Approaches","author":"T. Ibaraki","year":"1988","unstructured":"T. Ibaraki and N. Katoh,Resource Allocation Problems: Algorithmic Approaches (MIT Press, Cambridge, MA, 1988)."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0167-6377(93)90041-E","volume":"13","author":"N. Megiddo","year":"1993","unstructured":"N. Megiddo and A. Tamir, \u201cLinear time algorithms for some separable quadratic programming problems,\u201dOperations Research Letters 13 (1993) 203\u2013211.","journal-title":"Operations Research Letters"},{"key":"CR22","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"G.L. Nemhauser","year":"1988","unstructured":"G.L. Nemhauser and L.A. Wolsey,Integer and Combinatorial Optimization (Wiley, New York, 1988)."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF01581240","volume":"59","author":"A. Tamir","year":"1993","unstructured":"A. Tamir, \u201cA strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on series-parallel networks,\u201dMathematical Programming 59 (1993) 117\u2013132.","journal-title":"Mathematical Programming"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E. Tardos","year":"1986","unstructured":"E. Tardos, \u201cA strongly polynomial algorithm to solve combinatorial linear programs,\u201dOperations Research 34 (1986) 250\u2013256.","journal-title":"Operations Research"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585561.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01585561\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585561","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T08:20:00Z","timestamp":1706170800000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01585561"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,7]]},"references-count":24,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1995,7]]}},"alternative-id":["BF01585561"],"URL":"https:\/\/doi.org\/10.1007\/bf01585561","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,7]]}}}