{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T02:02:04Z","timestamp":1649124124322},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,9,28]],"date-time":"2007-09-28T00:00:00Z","timestamp":1190937600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,3]]},"DOI":"10.1007\/s00453-007-9039-0","type":"journal-article","created":{"date-parts":[[2007,9,27]],"date-time":"2007-09-27T14:18:26Z","timestamp":1190902706000},"page":"337-357","source":"Crossref","is-referenced-by-count":1,"title":["Approximability of Minimum AND-Circuits"],"prefix":"10.1007","volume":"53","author":[{"given":"Jan","family":"Arpe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,9,28]]},"reference":[{"key":"9039_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs (1993)"},{"issue":"1\u20132","key":"9039_CR2","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P. Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1\u20132), 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"9039_CR3","doi-asserted-by":"crossref","unstructured":"Allender, E., Hellerstein, L., McCabe, P., Pitassi, T., Saks, M.: Minimizing DNF formulas and AC d 0 circuits given a truth table. In: Proc. of the 21st Ann. IEEE Conference on Computational Complexity (CCC), pp. 237\u2013251. IEEE Press (2006)","DOI":"10.1109\/CCC.2006.27"},{"key":"9039_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, New York (1999)"},{"issue":"7","key":"9039_CR5","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"9039_CR6","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1016\/j.tcs.2005.11.029","volume":"354","author":"M. Chleb\u00edk","year":"2006","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Complexity of approximating bounded variants of optimization problems. Theor. Comput. Sci. 354(3), 320\u2013338 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"9039_CR7","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"23","author":"G.P. Cornu\u00e9jols","year":"1977","unstructured":"Cornu\u00e9jols, G.P., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Manag. Sci. 23(8), 789\u2013810 (1977)","journal-title":"Manag. Sci."},{"issue":"3","key":"9039_CR8","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1137\/0210047","volume":"10","author":"P.J. Downey","year":"1981","unstructured":"Downey, P.J., Leong, B.L., Sethi, R.: Computing sequences with addition chains. SIAM J. Comput. 10(3), 638\u2013646 (1981)","journal-title":"SIAM J. Comput."},{"key":"9039_CR9","series-title":"Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"9039_CR10","first-page":"363","volume-title":"Proc. of the 38th Ann. ACM Symp. on Theory of Computing (STOC)","author":"V. Feldman","year":"2006","unstructured":"Feldman, V.: Hardness of approximate two-level logic minimization and PAC learning with membership queries. In: Proc. of the 38th Ann. ACM Symp. on Theory of Computing (STOC), pp.\u00a0363\u2013372. ACM Press, New York (2006)"},{"issue":"3","key":"9039_CR11","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.K.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9039_CR12","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"9039_CR13","first-page":"73","volume-title":"Proc. of the 32nd Ann. ACM Symp. on Theory of Computing (STOC)","author":"V. Kabanets","year":"2000","unstructured":"Kabanets, V., Cai, J.-Y.: Circuit minimization problems. In: Proc. of the 32nd Ann. ACM Symp. on Theory of Computing (STOC), pp.\u00a073\u201379. ACM Press, New York (2000)"},{"issue":"3","key":"9039_CR14","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1109\/18.841160","volume":"46","author":"J.C. Kieffer","year":"2000","unstructured":"Kieffer, J.C., Yang, E.-H.: Grammar based codes: a new class of universal lossless source codes. IEEE Trans. Inf. Theory 46(3), 737\u2013754 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9039_CR15","series-title":"The Art of Computer Programming","volume-title":"Seminumerical Algorithms","author":"D.E. Knuth","year":"1981","unstructured":"Knuth, D.E.: Seminumerical Algorithms, vol.\u00a02, The Art of Computer Programming, 2nd edn. Addison-Wesley, Reading (1981)","edition":"2"},{"key":"9039_CR16","first-page":"30","volume-title":"Proc. of the 10th Ann. ACM Symp. on Theory of Computing (STOC)","author":"J.A. Storer","year":"1978","unstructured":"Storer, J.A., Szymanski, T.G.: The macro model for data compression. In: Proc. of the 10th Ann. ACM Symp. on Theory of Computing (STOC), pp.\u00a030\u201339. ACM Press, New York (1978)"},{"key":"9039_CR17","first-page":"12","volume":"2","author":"R.E. Tarjan","year":"1978","unstructured":"Tarjan, R.E.: Complexity of monotone networks for computing conjunctions. Ann. Discret. Math. 2, 121\u2013133 (1978)","journal-title":"Ann. Discret. Math."},{"issue":"4","key":"9039_CR18","doi-asserted-by":"crossref","first-page":"1247","DOI":"10.1137\/S0097539795295663","volume":"28","author":"E.G. Thurber","year":"1999","unstructured":"Thurber, E.G.: Efficient generation of minimal length addition chains. SIAM J. Comput. 28(4), 1247\u20131263 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9039_CR19","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1006\/jcss.2001.1775","volume":"63","author":"C. Umans","year":"2001","unstructured":"Umans, C.: The minimum equivalent DNF problem and shortest implicants. J. Comput. Syst. Sci. 63(4), 597\u2013611 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9039_CR20","doi-asserted-by":"crossref","unstructured":"Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner (1987)","DOI":"10.1007\/3-540-18170-9_185"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9039-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9039-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9039-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:44:59Z","timestamp":1559123099000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9039-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,28]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["9039"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9039-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9,28]]}}}