{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T18:42:38Z","timestamp":1772044958523,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,11,22]],"date-time":"2011-11-22T00:00:00Z","timestamp":1321920000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2011,12]]},"DOI":"10.1007\/s00037-011-0028-y","type":"journal-article","created":{"date-parts":[[2011,11,21]],"date-time":"2011-11-21T06:52:26Z","timestamp":1321858346000},"page":"679-740","source":"Crossref","is-referenced-by-count":14,"title":["Toward a Model for Backtracking and Dynamic Programming"],"prefix":"10.1007","volume":"20","author":[{"given":"Michael","family":"Alekhnovich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Allan","family":"Borodin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joshua","family":"Buresh-Oppenheim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Russell","family":"Impagliazzo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avner","family":"Magen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,11,22]]},"reference":[{"key":"28_CR1","unstructured":"Dimitris Achlioptas & Gregory B. Sorkin (2000). Optimal myopic algorithms for random 3-SAT. In IEEE Symposium on Foundations of Computer Science, 590\u2013600."},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"M. Alekhnovich (2005). Lower bounds for k-DNF Resolution on random 3CNF. In Proceedings of the 37th Symposium on Theory of Computing, 251\u2013256.","DOI":"10.1145\/1060590.1060628"},{"key":"28_CR3","unstructured":"M. Alekhnovich, E. Hirsch & D. Itsykson (2005). Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. Journal of Automated Reasoning 35(1-3), 51\u201372. Preliminary version appeared in Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), 2004."},{"key":"28_CR4","unstructured":"M. Alekhnovich & A. Razborov (2001). Lower bounds for the polynomial calculus: non-binomial case. In Proc. 42nd Ann. Symp. on Foundations of Computer Science. IEEE Computer Society."},{"issue":"4","key":"28_CR5","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/s00453-004-1113-2","volume":"40","author":"S. Angelopoulos","year":"2004","unstructured":"Angelopoulos S., Borodin A. (2004) On the Power of Priority Algorithms for Facility Location and Set Cover. Algorithmica 40(4): 271\u2013291","journal-title":"Algorithmica"},{"key":"28_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(87)90037-0","volume":"18","author":"E.M. Arkin","year":"1987","unstructured":"Arkin E.M., Silverberg E.L. (1987) Scheduling Jobs with Fixed Start and End Times. Disc. Appl. Math 18: 1\u20138","journal-title":"Disc. Appl. Math"},{"issue":"2","key":"28_CR7","doi-asserted-by":"crossref","first-page":"19","DOI":"10.4086\/toc.2006.v002a002","volume":"2","author":"Sanjeev. Arora","year":"2006","unstructured":"Arora Sanjeev., Bollob\u00e1s B\u00e9la., Lov\u00e1sz L\u00e1szl\u00f3., Tourlakis Iannis (2006) Proving Integrality Gaps without Knowing the Linear Program. Theory of Computing 2(2): 19\u201351","journal-title":"Theory of Computing"},{"key":"28_CR8","volume-title":"Social Choice and Individual Values","author":"Kenneth Arrow","year":"1951","unstructured":"Arrow Kenneth (1951) Social Choice and Individual Values. Wiley, New York"},{"key":"28_CR9","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/s00453-003-1036-3","volume":"37","author":"A. Borodin","year":"2003","unstructured":"Borodin A., Nielsen M., Rackoff C. (2003) (Incremental) Priority Algorithms. Algorithmica 37: 295\u2013326","journal-title":"Algorithmica"},{"key":"28_CR10","doi-asserted-by":"crossref","unstructured":"Allan Borodin, Joan Boyar & Kim S. Larsen (2005). Priority Algorithms for Graph Optimization Problems. In Second Workshop on Approximation and Online Algorithms, volume 3351 of Lecture Notes in Computer Science, 126\u2013139. Springer-Verlag.","DOI":"10.1007\/978-3-540-31833-0_12"},{"key":"28_CR11","unstructured":"J. Buresh-Oppenheim, S. Davis & R. Impagliazzo (2010). A stronger model of dynamic programming algorithms. To appear in the journal Algorithmica."},{"issue":"6","key":"28_CR12","doi-asserted-by":"crossref","first-page":"1402","DOI":"10.1287\/opre.28.6.1402","volume":"28","author":"V. Chv\u00e1tal","year":"1985","unstructured":"Chv\u00e1tal V. (1985) Hard Knapsack Problems. Operations Research 28(6): 1402\u20131441","journal-title":"Operations Research"},{"key":"28_CR13","unstructured":"S. Cook & D. Mitchell (1997). Finding hard instances of the satisfiability problem: A survey. In DIMACS Series in Theoretical Computer Science."},{"key":"28_CR14","volume-title":"Introduction to Algorithms, Second Edition","author":"T. Cormen","year":"2001","unstructured":"Cormen T., Leiserson C., Rivest R., Stein C. (2001) Introduction to Algorithms, Second Edition. MIT Press, Cambridge, Mass"},{"key":"28_CR15","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"Davis M., Logemann G., Loveland D. (1962) A machine program for theorem proving. Communications of the ACM 5: 394\u2013397","journal-title":"Communications of the ACM"},{"key":"28_CR16","first-page":"201","volume":"7","author":"M. Davis","year":"1960","unstructured":"Davis M., Putnam H. (1960) A computing procedure for quantification theory. Communications of the ACM 7: 201\u2013215","journal-title":"Communications of the ACM"},{"key":"28_CR17","unstructured":"S. Davis, J. Edmonds & R.Impagliazzo (2010). Randomized priority algorithms, pBT, and free-branching pBT lower bounds. Manuscript in preparation."},{"key":"28_CR18","unstructured":"S. Davis & R. Impagliazzo (2009). Models of Greedy Algorithms for Graph Problems. Algorithmica 54(3). Preliminary version appeared in the Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004."},{"key":"28_CR19","doi-asserted-by":"crossref","unstructured":"B.C Dean, M.X. Goemans & J. Vondr\u00e1k (2004). Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity. In it Proc. 44th Ann. Symp. on Foundations of Computer Science.","DOI":"10.1109\/FOCS.2004.15"},{"key":"28_CR20","unstructured":"T. Erlebach & F.C.R. Spieksma (2002). Interval selection: Applications, algorithms, and lower bounds. Technical Report 152, Computer Engineering and Networks Laboratory, ETH."},{"key":"28_CR21","doi-asserted-by":"crossref","unstructured":"J. Gu, P. W. Purdom, J. Franco & B. J. Wah (1997). Algorithms for the Satisfiability (SAT) Problem: A Survey. In Satisfiability (SAT) Problem, DIMACS, 19\u2013151. American Mathematical Society.","DOI":"10.1090\/dimacs\/035\/02"},{"key":"28_CR22","doi-asserted-by":"crossref","unstructured":"M. Halldorsson, K. Iwama, S. Miyazaki & S. Taketomi (2002). Online Independent Sets. Theoretical Computer Science 953\u2013962.","DOI":"10.1016\/S0304-3975(01)00411-X"},{"key":"28_CR23","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad H. (2001) Some optimal inapproximability results. JACM 48: 798\u2013859","journal-title":"JACM"},{"issue":"1","key":"28_CR24","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1145\/58562.59304","volume":"36","author":"P. Helman","year":"1989","unstructured":"Helman P. (1989) A Common Schema for Dynamic Programming and Branch and Bound Algorithms. Journal of the Association of Computing Machinery 36(1): 97\u2013128","journal-title":"Journal of the Association of Computing Machinery"},{"key":"28_CR25","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1137\/0606032","volume":"6","author":"P. Helman","year":"1985","unstructured":"Helman P., Rosenthal A. (1985) A comprehensive model of dynamic programming. SIAM J. on Algebraic and Discrete Methods 6: 319\u2013334","journal-title":"SIAM J. on Algebraic and Discrete Methods"},{"key":"28_CR26","unstructured":"S.L. Horn (2004). One-Pass algorithms with revocable acceptances for job interval selection. MSc Thesis, University of Toronto."},{"key":"28_CR27","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O. Ibarra","year":"1975","unstructured":"Ibarra O., Kim C. (1975) Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems. JACM 22: 463\u2013468","journal-title":"JACM"},{"key":"28_CR28","doi-asserted-by":"crossref","unstructured":"A. Kaporis, L. Kirousis & E. Lalas (2003). Selecting complementary pairs of literals. In Proc. LICS\u201803 Workshop on Typical Case Complexity and Phase Transitions. citeseer.ist.psu.edu\/kaporis03selecting.html .","DOI":"10.1016\/S1571-0653(04)00462-7"},{"key":"28_CR29","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1137\/0115060","volume":"15","author":"R.M. Karp","year":"1967","unstructured":"Karp R.M., Held M. (1967) Finite state processes and dynamic programming. SIAM J. Applied Mathematics 15: 693\u2013718","journal-title":"SIAM J. Applied Mathematics"},{"key":"28_CR30","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1137\/S0097539795286612","volume":"28","author":"S. Khanna","year":"1998","unstructured":"Khanna S., Motwani R., Sudan M., Vazirani U. (1998) On Syntactic versus Computational Views of Approximability. SIAM Journal on Computing 28: 164\u2013191","journal-title":"SIAM Journal on Computing"},{"key":"28_CR31","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/BF00264289","volume":"1","author":"D.E. Knuth","year":"1971","unstructured":"Knuth D.E. (1971) Optimum binary search trees. Acta Informatica 1: 14\u201325","journal-title":"Acta Informatica"},{"key":"28_CR32","doi-asserted-by":"crossref","unstructured":"E. L. Lawler (1977). Fast Approximation Algorithms for Knapsack Problems. In Proc. 18th Ann. Symp. on Foundations of Computer Science. IEEE Computer Society, Long Beach, CA.","DOI":"10.1109\/SFCS.1977.11"},{"key":"28_CR33","unstructured":"Rajeev Motwani & Prabhakar Raghavan (1995). Randomized Algorithms. Cambridge University Press."},{"issue":"3","key":"28_CR34","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0020-0190(02)00264-8","volume":"84","author":"Regev Oded","year":"2002","unstructured":"Oded Regev (2002) Priority algorithms for makespan minimization in the subset model. Information Processing Letters 84(3): 153\u2013157","journal-title":"Information Processing Letters"},{"key":"28_CR35","unstructured":"Vijay V. Vazirani (2001). Approximation Algorithms. Springer-Verlag."},{"key":"28_CR36","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1287\/ijoc.12.1.57.11901","volume":"12","author":"G. Woeginger","year":"2000","unstructured":"Woeginger G. (2000) When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?. INFORMS Journal on Computing 12: 57\u201375","journal-title":"INFORMS Journal on Computing"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0028-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-011-0028-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0028-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,11]],"date-time":"2023-06-11T07:04:46Z","timestamp":1686467086000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-011-0028-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,22]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["28"],"URL":"https:\/\/doi.org\/10.1007\/s00037-011-0028-y","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11,22]]}}}