{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:56Z","timestamp":1725663416146},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540542339"},{"type":"electronic","value":"9783540475163"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_177","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:39:30Z","timestamp":1330191570000},"page":"719-727","source":"Crossref","is-referenced-by-count":4,"title":["An almost linear-time algorithm for the dense subset-sum problem"],"prefix":"10.1007","author":[{"given":"Zvi","family":"Galil","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oded","family":"Margalit","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"57_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon and G. A. Freiman, On sums of subsets of a set of integers, it Combinatorica, to appear.","DOI":"10.1007\/BF02189086"},{"key":"57_CR2","unstructured":"A. A. Berstein and G. A. Freiman, Analytical methods of discrete optimization, ZEMJ, 89\u2013105, 1979."},{"key":"57_CR3","unstructured":"M. Chaimovich, An efficient algorithm for subset-sum problem, a manuscript, 1989."},{"key":"57_CR4","unstructured":"M. Chaimovich, Fast exact and approximate algorithms for k-partition and scheduling independent tasks, a manuscript, 1989."},{"key":"57_CR5","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0885-064X(89)90025-3","volume":"5","author":"M. Chaimovich","year":"1989","unstructured":"M. Chaimovich, G. A. Freiman and Z. Galil, Solving Dense subset-sum problems by using analytic number theory, J. of Complexity 5, 271\u2013282, 1989.","journal-title":"J. of Complexity"},{"key":"57_CR6","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1287\/opre.5.2.266","volume":"5","author":"G. B. Dantzig","year":"1957","unstructured":"Dantzig, G. B., Discrete-variable extremum problems, Operations Research 5, 266\u2013277, 1957.","journal-title":"Operations Research"},{"key":"57_CR7","unstructured":"P. Erd\u00f6s and G. A. Freiman, On two additive problems, J. Number Theory, to appear, 1989."},{"key":"57_CR8","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1111\/j.1749-6632.1980.tb18009.x","volume":"337","author":"G. A. Freiman","year":"1980","unstructured":"G. A. Freiman, An analytical method of analysis of linear Boolean equations, Ann. N.Y. Acad. Sci. 337, 97\u2013102, 1980.","journal-title":"Ann. N.Y. Acad. Sci."},{"key":"57_CR9","unstructured":"G. A. Freiman [1987], On extremal additive problems of Paul Erd\u00f6s, in \u201cProc. Canberra Conference on Combinatorics,\u201d August 1987."},{"key":"57_CR10","unstructured":"G. A. Freiman, Subset-sum problem with different summands, submitted, 1988."},{"key":"57_CR11","unstructured":"G. A. Freiman, A new analytic result on the subset-sum problem, in \u201cProc. French-Israeli Conference on Combinatorics and Algorithms\u201d, November 1988."},{"key":"57_CR12","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A guide to the theory of NP-completeness, San Francisco, W. H. Freeman & Company, 1979."},{"key":"57_CR13","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and M. Naor, Efficient cryptographic schemes provably as secure as subset sum, in \u201cProc. 30th IEEE Symp. on Foundations of Computer Science,\u201d pp. 236\u2013241, October 1989.","DOI":"10.1109\/SFCS.1989.63484"},{"key":"57_CR14","doi-asserted-by":"crossref","unstructured":"J. Lagarias and A. Odlyzko, Solving low-density subset sums, in \u201cProc. 24th IEEE Symp. on Foundations of Computer Science,\u201d pp. 1\u201310, October 1983.","DOI":"10.1109\/SFCS.1983.70"},{"key":"57_CR15","doi-asserted-by":"crossref","unstructured":"E. Lipkin, On representation of r-powers by subset sums, Acta Arithmetica, to appear.","DOI":"10.4064\/aa-52-4-353-365"},{"key":"57_CR16","unstructured":"A. Sark\u00f6zy, Finite addition theorems, II, J. Number Theory, to appear."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_177.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:53:22Z","timestamp":1605628402000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_177"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_177","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}