{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T05:44:40Z","timestamp":1648878280473},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,7,30]],"date-time":"2018-07-30T00:00:00Z","timestamp":1532908800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s10479-018-2986-9","type":"journal-article","created":{"date-parts":[[2018,7,30]],"date-time":"2018-07-30T12:51:04Z","timestamp":1532955064000},"page":"87-103","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["When polynomial approximation meets exact computation"],"prefix":"10.1007","volume":"271","author":[{"given":"Vangelis Th.","family":"Paschos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,7,30]]},"reference":[{"issue":"3","key":"2986_CR1","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998). Proof verification and intractability of approximation problems. Journal of the Association for Computing Machinery, 45(3), 501\u2013555.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"2986_CR2","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. (1999). Complexity and approximation. Combinatorial optimization problems and their approximability properties. Berlin: Springer."},{"key":"2986_CR3","doi-asserted-by":"crossref","unstructured":"Avidor, A., Berkovitch, I., & Zwick, U. (2006). Improved approximation algorithms for MAX NAE-SAT and MAX SAT. In T.\u00a0Erlebach & G.\u00a0Persiano (Eds.), Proceedimgs of workshop on approximation and online algorithms, WAOA\u201905, Lecture notes in computer science (Vol. 3879, pp. 27\u201340). Springer.","DOI":"10.1007\/11671411_3"},{"key":"2986_CR4","volume-title":"Graphs and hypergraphs","author":"C Berge","year":"1973","unstructured":"Berge, C. (1973). Graphs and hypergraphs. Amsterdam: North Holland."},{"key":"2986_CR5","doi-asserted-by":"crossref","unstructured":"Berman, P., & Fujito, T. (1995). On the approximation properties of independent set problem in degree\u00a03 graphs. In Proceedings of international workshop on algorithms and data structures, WADS\u201995, Lecture notes in computer science (Vol. 955, pp. 449\u2013460). Springer.","DOI":"10.1007\/3-540-60220-8_84"},{"issue":"2","key":"2986_CR6","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/s00453-007-9149-8","volume":"52","author":"A Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, A., & Husfeldt, T. (2008). Exact algorithms for exact satisfiability and number of perfect matchings. Algorithmica, 52(2), 226\u2013249.","journal-title":"Algorithmica"},{"issue":"2","key":"2986_CR7","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., & Koivisto, M. (2009). Set partitioning via inclusion-exclusion. SIAM Journal on Computing, 39(2), 546\u2013563.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"2986_CR8","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/s00453-014-9889-1","volume":"71","author":"E Bonnet","year":"2015","unstructured":"Bonnet, E., Escoffier, B., Kim, E., & Paschos, V Th. (2015). On subexponential and fpt-time inapproximability. Algorithmica, 71(3), 541\u2013565.","journal-title":"Algorithmica"},{"key":"2986_CR9","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.jda.2013.06.011","volume":"22","author":"N Boria","year":"2013","unstructured":"Boria, N., Bourgeois, N., Escoffier, B., & Paschos, V Th. (2013). Exponential approximation schemata for some network design problems. Journal of Discrete Algorithms, 22, 43\u201352.","journal-title":"Journal of Discrete Algorithms"},{"issue":"4\u20135","key":"2986_CR10","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1016\/j.dam.2012.01.003","volume":"161","author":"N Bourgeois","year":"2013","unstructured":"Bourgeois, N., Della Croce, F., Escoffier, B., & Paschos, V. Th. (2013). Fast algorithms for min independent dominating set. Discrete Applied Mathematics, 161(4\u20135), 558\u2013572.","journal-title":"Discrete Applied Mathematics"},{"issue":"21\u201323","key":"2986_CR11","doi-asserted-by":"publisher","first-page":"2184","DOI":"10.1016\/j.tcs.2009.02.007","volume":"410","author":"N Bourgeois","year":"2009","unstructured":"Bourgeois, N., Escoffier, B., & Paschos, V Th. (2009). Efficient approximation of min set cover by moderately exponential algorithms. Theoretical Computer Science, 410(21\u201323), 2184\u20132195.","journal-title":"Theoretical Computer Science"},{"issue":"17","key":"2986_CR12","doi-asserted-by":"publisher","first-page":"1954","DOI":"10.1016\/j.dam.2011.07.009","volume":"159","author":"N Bourgeois","year":"2011","unstructured":"Bourgeois, N., Escoffier, B., & Paschos, V Th. (2011). Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discrete Applied Mathematics, 159(17), 1954\u20131970.","journal-title":"Discrete Applied Mathematics"},{"issue":"6","key":"2986_CR13","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/j.orl.2004.03.002","volume":"32","author":"JM Byskov","year":"2004","unstructured":"Byskov, J. M. (2004). Enumerating maximal independent sets with applications to graph colouring. Operations Research Letters, 32(6), 547\u2013556.","journal-title":"Operations Research Letters"},{"key":"2986_CR14","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Laekhanukit, B., & Nanongkai, D. (2013). Independent set, induced matching, and pricing: Connections and tight (subexponential time) approximation hardnesses. In Proceedings of FOCS\u201913 (pp. 370\u2013379).","DOI":"10.1109\/FOCS.2013.47"},{"issue":"16","key":"2986_CR15","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1016\/j.ipl.2009.05.003","volume":"109","author":"M Cygan","year":"2009","unstructured":"Cygan, M., Kowalik, L., & Wykurz, M. (2009). Exponential-time approximation of weighted set cover. Information Processing Letters, 109(16), 957\u2013961.","journal-title":"Information Processing Letters"},{"issue":"40\u201342","key":"2986_CR16","doi-asserted-by":"publisher","first-page":"3701","DOI":"10.1016\/j.tcs.2010.06.018","volume":"411","author":"M Cygan","year":"2010","unstructured":"Cygan, M., & Pilipczuk, M. (2010). Exact and approximate bandwidth. Theoretical Computer Science, 411(40\u201342), 3701\u20133713.","journal-title":"Theoretical Computer Science"},{"key":"2986_CR17","doi-asserted-by":"crossref","unstructured":"Cygan, M., Pilipczuk, M., & Wojtaszczyk, J. O. (2010). Capacitated domination faster than\u00a0\n                    \n                      \n                    \n                    $${O}(2^n)$$\n                    \n                      \n                        \n                          O\n                          (\n                          \n                            2\n                            n\n                          \n                          )\n                        \n                      \n                    \n                  . In H.\u00a0Kaplan (Ed.) Proceedings of scandinavian symposium and workshops on algorithm theory, SWAT\u201910, Lecture notes in computer science (Vol. 6139, pp. 74\u201380). Springer.","DOI":"10.1007\/978-3-642-13731-0_8"},{"key":"2986_CR18","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0168-0072(01)00052-5","volume":"113","author":"E Dantsin","year":"2002","unstructured":"Dantsin, E., Gavrilovich, M., Hirsch, E. A., & Konev, B. (2002). MAX SAT approximation beyond the limits of polynomial-time approximation. Annals of Pure and Applied Logic, 113, 81\u201394.","journal-title":"Annals of Pure and Applied Logic"},{"issue":"3","key":"2986_CR19","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/1236457.1236459","volume":"54","author":"Irit Dinur","year":"2007","unstructured":"Dinur, I. (2007). The PCP theorem by gap amplification. Journal of the Association for Computing Machinery, 54(3), Article 12.","journal-title":"Journal of the ACM"},{"issue":"2","key":"2986_CR20","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.tcs.2014.10.039","volume":"560","author":"B Escoffier","year":"2014","unstructured":"Escoffier, B., Paschos, V Th, & Tourniaire, E. (2014). Approximating max sat by moderately exponential and parameterized algorithms. Theoretical Computer Science, 560(2), 147\u2013157.","journal-title":"Theoretical Computer Science"},{"key":"2986_CR21","doi-asserted-by":"crossref","unstructured":"Fomin, F. V., Grandoni, F., & Kratsch, D. (2005). Measure and conquer: Domination\u2014A case study. In L.\u00a0Caires, G.F. Italiano, L.\u00a0Monteiro, C.\u00a0Palamidessi, & M.\u00a0Yung (Eds.), Proceedings of ICALP\u201905, Lecture notes in computer science (Vol. 3580, pp. 191\u2013203). Springer.","DOI":"10.1007\/11523468_16"},{"key":"2986_CR22","series-title":"EATCS","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact exponential algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F. V., & Kratsch, D. (2010). Exact exponential algorithms., EATCS Berlin: Springer."},{"issue":"3","key":"2986_CR23","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1137\/0216034","volume":"16","author":"Y Gurevich","year":"1987","unstructured":"Gurevich, Y., & Shelah, S. (1987). Expected computation time for Hamiltonian path problem. SIAM Journal on Computing, 16(3), 486\u2013502.","journal-title":"SIAM Journal on Computing"},{"key":"2986_CR24","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","volume":"46","author":"MM Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson, M. M. (1993). Approximating the minimum maximal independence number. Information Processing Letters, 46, 169\u2013172.","journal-title":"Information Processing Letters"},{"key":"2986_CR25","first-page":"196","volume":"10","author":"M Held","year":"1962","unstructured":"Held, M., & Karp, R. (1962). A dynamic programming approach to sequencing problems. Journal of SIAM, 10, 196\u2013210.","journal-title":"Journal of SIAM"},{"key":"2986_CR26","volume-title":"Approximation algorithms for NP-hard problems","year":"1997","unstructured":"Hochbaum, D. S. (Ed.). (1997). Approximation algorithms for NP-hard problems. Boston: PWS."},{"key":"2986_CR27","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D. S. (1974). Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9, 256\u2013278.","journal-title":"Journal of Computer and System Sciences"},{"key":"2986_CR28","doi-asserted-by":"crossref","unstructured":"Khot, S., & Regev, O. (2003). Vertex cover might be hard to approximate to within \n                    \n                      \n                    \n                    $$2-\\varepsilon $$\n                    \n                      \n                        \n                          2\n                          -\n                          \u03b5\n                        \n                      \n                    \n                  . In Proceedings of annual conference on computational complexity, CCC\u201903 (pp. 379\u2013386).","DOI":"10.1109\/CCC.2003.1214437"},{"key":"2986_CR29","doi-asserted-by":"crossref","unstructured":"Moshkovitz, D. (2012). The projection games conjecture and the NP-hardness of \n                    \n                      \n                    \n                    $$\\ln {n}$$\n                    \n                      \n                        \n                          ln\n                          n\n                        \n                      \n                    \n                  -approximating set-cover. In A.\u00a0Gupta, K.\u00a0Jansen, J. D. P. Rolim, & R. A. Servedio (Eds.), Proceedings of workshop on approximation algorithms for combinatorial optimization problems and workshop on randomization and computation, APPROX-RANDOM\u201912, Lecture notes in computer science (Vol. 7408, pp. 276\u2013287). Springer.","DOI":"10.1007\/978-3-642-32512-0_24"},{"key":"2986_CR30","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser, G. L., & Trotter, L. E. (1975). Vertex packings: Structural properties and algorithms. Mathematical Programming, 8, 232\u2013248.","journal-title":"Mathematical Programming"},{"key":"2986_CR31","doi-asserted-by":"crossref","unstructured":"Paluch, K. E., Mucha, M., & Madry, A. (2009). A 7\/9-approximation algorithm for the maximum traveling salesman problem. In I.\u00a0Dinur, K.\u00a0Jansen, J.\u00a0Naor, & J. D. P. Rolim (Eds.), Proceedings on approximation, randomization and combinatorial optimization. Algorithms and techniques, APPROX-RANDOM\u201909, Lecture notes in computer science (Vol. 5687, pp. 298\u2013311). Springer.","DOI":"10.1007\/978-3-642-03685-9_23"},{"key":"2986_CR32","volume-title":"Combinatorial optimization: Algorithms and complexity","author":"CH Papadimitriou","year":"1981","unstructured":"Papadimitriou, C. H., & Steiglitz, K. (1981). Combinatorial optimization: Algorithms and complexity. NJ: Prentice Hall."},{"key":"2986_CR33","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C. H., & Yannakakis, M. (1991). Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43, 425\u2013440.","journal-title":"Journal of Computer and System Sciences"},{"key":"2986_CR34","volume-title":"Complexit\u00e9 et approximation polynomiale","author":"VTh Paschos","year":"2004","unstructured":"Paschos, V Th. (2004). Complexit\u00e9 et approximation polynomiale. Paris: Herm\u00e8s."},{"issue":"3","key":"2986_CR35","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s10288-015-0294-7","volume":"13","author":"V Th Paschos","year":"2015","unstructured":"Paschos, V. Th. (2015). When polynomial approximation meets exact computation. 4OR, 13(3), 227\u2013245.","journal-title":"4OR"},{"key":"2986_CR36","volume-title":"Approximation algorithms","author":"V Vazirani","year":"2001","unstructured":"Vazirani, V. (2001). Approximation algorithms. Berlin: Springer."},{"key":"2986_CR37","doi-asserted-by":"crossref","unstructured":"Woeginger, G.\u00a0J. (2003). Exact algorithms for NP-hard problems: a survey. In M.\u00a0Juenger, G.\u00a0Reinelt, & G.\u00a0Rinaldi (Eds.), Combinatorial Optimization\u2014Eureka! You shrink!, Lecture notes in computer science (Vol. 2570, pp. 185\u2013207). Springer.","DOI":"10.1007\/3-540-36478-1_17"},{"key":"2986_CR38","unstructured":"Xiao, M., & Nagamochi, H. (2013). Exact algorithms for maximum independent set. CoRR. \n                    arXiv:1312.6260\n                    \n                  ."},{"issue":"6","key":"2986_CR39","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D. (2007). Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(6), 103\u2013128.","journal-title":"Theory of Computing"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-018-2986-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-018-2986-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-018-2986-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,29]],"date-time":"2019-07-29T23:26:38Z","timestamp":1564442798000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-018-2986-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,30]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["2986"],"URL":"https:\/\/doi.org\/10.1007\/s10479-018-2986-9","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,30]]},"assertion":[{"value":"30 July 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}