{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:37:48Z","timestamp":1725543468925},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540357537"},{"type":"electronic","value":"9783540357551"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11785293_28","type":"book-chapter","created":{"date-parts":[[2006,6,26]],"date-time":"2006-06-26T01:24:10Z","timestamp":1151285050000},"page":"292-303","source":"Crossref","is-referenced-by-count":1,"title":["Approximability of Minimum AND-Circuits"],"prefix":"10.1007","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","reference":[{"key":"28_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)"},{"key":"28_CR2","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, Heidelberg (1999)"},{"issue":"7","key":"28_CR3","doi-asserted-by":"publisher","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 Transactions on Information Theory\u00a051(7), 2554\u20132576 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"28_CR4","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0354(3), 320\u2013338 (2006)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"28_CR5","doi-asserted-by":"publisher","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 Journal on Computing\u00a010(3), 638\u2013646 (1981)","journal-title":"SIAM Journal on Computing"},{"key":"28_CR6","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, Heidelberg (1999)"},{"key":"28_CR7","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. 73\u201379. ACM Press, New York (2000)"},{"issue":"3","key":"28_CR8","doi-asserted-by":"publisher","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 Transactions on Information Theory\u00a046(3), 737\u2013754 (2000)","journal-title":"IEEE Transactions on Information Theory"},{"key":"28_CR9","series-title":"The Art of Computer Programming","volume-title":"Seminumerical Algorithms","author":"D.E. Knuth","year":"1981","unstructured":"Knuth, D.E.: Seminumerical Algorithms, 2nd edn. The Art of Computer Programming, vol.\u00a02. Addison-Wesley, Reading (1981)","edition":"2"},{"key":"28_CR10","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/800133.804329","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. 30\u201339. ACM Press, New York (1978)"},{"key":"28_CR11","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0167-5060(08)70326-1","volume":"2","author":"R.E. Tarjan","year":"1978","unstructured":"Tarjan, R.E.: Complexity of monotone networks for computing conjunctions. Annals of Discrete Mathematics\u00a02, 121\u2013133 (1978)","journal-title":"Annals of Discrete Mathematics"},{"issue":"4","key":"28_CR12","doi-asserted-by":"publisher","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 Journal on Computing\u00a028(4), 1247\u20131263 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"28_CR13","volume-title":"The Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner, Chichester (1987)"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11785293_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:19:20Z","timestamp":1619493560000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11785293_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540357537","9783540357551"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/11785293_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}