{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T09:06:11Z","timestamp":1761987971317,"version":"build-2065373602"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,7,8]],"date-time":"2015-07-08T00:00:00Z","timestamp":1436313600000},"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":["4OR-Q J Oper Res"],"published-print":{"date-parts":[[2015,9]]},"DOI":"10.1007\/s10288-015-0294-7","type":"journal-article","created":{"date-parts":[[2015,7,7]],"date-time":"2015-07-07T10:51:27Z","timestamp":1436266287000},"page":"227-245","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["When polynomial approximation meets exact computation"],"prefix":"10.1007","volume":"13","author":[{"given":"Vangelis Th.","family":"Paschos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,8]]},"reference":[{"issue":"3","key":"294_CR1","doi-asserted-by":"crossref","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. J Assoc Comput Mach 45(3):501\u2013555","journal-title":"J Assoc Comput Mach"},{"key":"294_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, Protasi M (1999) Complexity and approximation. Combinatorial optimization problems and their approximability properties. Springer, Berlin"},{"key":"294_CR3","doi-asserted-by":"crossref","unstructured":"Avidor A, Berkovitch I, Zwick U (2006) Improved approximation algorithms for MAX NAE-SAT and MAX SAT. In: Erlebach T, Persiano G (eds) Proceedings of workshop on approximation and online algorithms, WAOA\u201905, vol 3879 of lecture notes in computer science. Springer, pp 27\u201340","DOI":"10.1007\/11671411_3"},{"key":"294_CR4","volume-title":"Graphs and hypergraphs","author":"C Berge","year":"1973","unstructured":"Berge C (1973) Graphs and hypergraphs. North Holland, Amsterdam"},{"key":"294_CR5","doi-asserted-by":"crossref","unstructured":"Berman P, Fujito T (1995) On the approximation properties of independent set problem in degree 3 graphs. In: Proceedings of international workshop on algorithms and data structures, WADS\u201995, vol 955 of lecture notes in computer science. Springer, pp 449\u2013460","DOI":"10.1007\/3-540-60220-8_84"},{"issue":"2","key":"294_CR6","doi-asserted-by":"crossref","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":"294_CR7","doi-asserted-by":"crossref","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\u2013exclusion. SIAM J Comput 39(2):546\u2013563","journal-title":"SIAM J Comput"},{"issue":"3","key":"294_CR8","doi-asserted-by":"crossref","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 VTh (2015) On subexponential and fpt-time inapproximability. Algorithmica 71(3):541\u2013565","journal-title":"Algorithmica"},{"key":"294_CR9","doi-asserted-by":"crossref","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 VTh (2013) Exponential approximation schemata for some network design problems. J Discrete Algorithms 22:43\u201352","journal-title":"J Discrete Algorithms"},{"issue":"4\u20135","key":"294_CR10","doi-asserted-by":"crossref","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 VTh (2013) Fast algorithms for min independent dominating set. Discrete Appl Math 161(4\u20135):558\u2013572","journal-title":"Discrete Appl Math"},{"issue":"21\u201323","key":"294_CR11","doi-asserted-by":"crossref","first-page":"2184","DOI":"10.1016\/j.tcs.2009.02.007","volume":"410","author":"N Bourgeois","year":"2009","unstructured":"Bourgeois N, Escoffier B, Paschos VTh (2009) Efficient approximation of min set cover by moderately exponential algorithms. Theor Comput Sci 410(21\u201323):2184\u20132195","journal-title":"Theor Comput Sci"},{"issue":"17","key":"294_CR12","doi-asserted-by":"crossref","first-page":"1954","DOI":"10.1016\/j.dam.2011.07.009","volume":"159","author":"N Bourgeois","year":"2011","unstructured":"Bourgeois N, Escoffier B, Paschos VTh (2011) Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discrete Appl Math 159(17):1954\u20131970","journal-title":"Discrete Appl Math"},{"issue":"6","key":"294_CR13","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1016\/j.orl.2004.03.002","volume":"32","author":"JM Byskov","year":"2004","unstructured":"Byskov JM (2004) Enumerating maximal independent sets with applications to graph colouring. Oper Res Lett 32(6):547\u2013556","journal-title":"Oper Res Lett"},{"key":"294_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":"294_CR15","doi-asserted-by":"crossref","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. Inf Process Lett 109(16):957\u2013961","journal-title":"Inf Process Lett"},{"issue":"40\u201342","key":"294_CR16","doi-asserted-by":"crossref","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. Theor Comput Sci 411(40\u201342):3701\u20133713","journal-title":"Theor Comput Sci"},{"key":"294_CR17","doi-asserted-by":"crossref","unstructured":"Cygan M, Pilipczuk M, Wojtaszczyk JO (2010) Capacitated domination faster than $${O}(2^n)$$ O ( 2 n ) . In: Kaplan H (eds) Proceedings of scandinavian symposium and workshops on algorithm theory, SWAT\u201910, vol 6139 of lecture notes in computer science. Spinger, pp 74\u201380","DOI":"10.1007\/978-3-642-13731-0_8"},{"key":"294_CR18","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0168-0072(01)00052-5","volume":"113","author":"E Dantsin","year":"2002","unstructured":"Dantsin E, Gavrilovich M, Hirsch EA, Konev B (2002) max sat approximation beyond the limits of polynomial-time approximation. Ann Pure Appl Log 113:81\u201394","journal-title":"Ann Pure Appl Log"},{"key":"294_CR19","doi-asserted-by":"crossref","unstructured":"Dinur I (2007) The PCP theorem by gap amplification. J Assoc Comput Mach 54(3)","DOI":"10.1145\/1236457.1236459"},{"issue":"2","key":"294_CR20","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.tcs.2014.10.039","volume":"560","author":"B Escoffier","year":"2014","unstructured":"Escoffier B, Paschos VTh, Tourniaire E (2014) Approximating Max Sat by moderately exponential and parameterized algorithms. Theor Comput Sci 560(2):147\u2013157","journal-title":"Theor Comput Sci"},{"key":"294_CR21","doi-asserted-by":"crossref","unstructured":"Fomin FV, Grandoni F, Kratsch D (2005) Measure and conquer: domination\u2014a case study. In: Caires L, Italiano GF, Monteiro L, Palamidessi C, Yung M (eds) Proceedings of ICALP\u201905, vol 3580 of lecture notes in computer science. Springer, pp 191\u2013203","DOI":"10.1007\/11523468_16"},{"key":"294_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact exponential algorithms. EATCS","author":"FV Fomin","year":"2010","unstructured":"Fomin FV, Kratsch D (2010) Exact exponential algorithms. EATCS. Springer, Berlin"},{"issue":"3","key":"294_CR23","doi-asserted-by":"crossref","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 J Comput 16(3):486\u2013502","journal-title":"SIAM J Comput"},{"key":"294_CR24","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","volume":"46","author":"MM Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson MM (1993) Approximating the minimum maximal independence number. Inf Process Lett 46:169\u2013172","journal-title":"Inf Process Lett"},{"key":"294_CR25","first-page":"196","volume":"10","author":"M Held","year":"1962","unstructured":"Held M, Karp R (1962) A dynamic programming approach to sequencing problems. J SIAM 10:196\u2013210","journal-title":"J SIAM"},{"volume-title":"Approximation algorithms for NP-hard problems","year":"1997","key":"294_CR26","unstructured":"Hochbaum DS (ed) (1997) Approximation algorithms for NP-hard problems. PWS, Boston"},{"key":"294_CR27","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson DS (1974) Approximation algorithms for combinatorial problems. J Comput Syst Sci 9:256\u2013278","journal-title":"J Comput Syst Sci"},{"key":"294_CR28","unstructured":"Khot S, Regev O (2003) Vertex cover might be hard to approximate to within $$2-\\varepsilon $$ 2 - \u03b5 . In: Proceedings of annual conference on computational complexity, CCC\u201903, pp 379\u2013386"},{"key":"294_CR29","doi-asserted-by":"crossref","unstructured":"Moshkovitz D (2012) The projection games conjecture and the NP-hardness of $$\\ln {n}$$ ln n -approximating set-cover. In Gupta A, Jansen K, Rolim JDP, Servedio RA (eds) Proceedings of workshop on approximation algorithms for combinatorial optimization problems and workshop on randomization and computation, APPROX-RANDOM\u201912, vol 7408 of lecture notes in computer science. Springer, pp 276\u2013287","DOI":"10.1007\/978-3-642-32512-0_24"},{"key":"294_CR30","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser GL, Trotter LE (1975) Vertex packings: structural properties and algorithms. Math Program 8:232\u2013248","journal-title":"Math Program"},{"key":"294_CR31","doi-asserted-by":"crossref","unstructured":"Paluch KE, Mucha M, Madry A (2009) A 7\/9-approximation algorithm for the maximum traveling salesman problem. In Dinur I, Jansen K, Naor J, Rolim JDP (eds) Proceedings of approximation, randomization and combinatorial optimization. Algorithms and techniques, APPROX-RANDOM\u201909, vol 5687 of lecture notes in computer science. Springer, pp 298\u2013311","DOI":"10.1007\/978-3-642-03685-9_23"},{"key":"294_CR32","volume-title":"Combinatorial optimization: algorithms and complexity","author":"CH Papadimitriou","year":"1981","unstructured":"Papadimitriou CH, Steiglitz K (1981) Combinatorial optimization: algorithms and complexity. Prentice Hall, New Jersey"},{"key":"294_CR33","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou CH, Yannakakis M (1991) Optimization, approximation and complexity classes. J Comput Syst Sci 43:425\u2013440","journal-title":"J Comput Syst Sci"},{"key":"294_CR34","volume-title":"Complexit\u00e9 et approximation polynomiale","author":"VTh Paschos","year":"2004","unstructured":"Paschos VTh (2004) Complexit\u00e9 et approximation polynomiale. Herm\u00e8s, Paris"},{"key":"294_CR35","volume-title":"Approximation algorithms","author":"V Vazirani","year":"2001","unstructured":"Vazirani V (2001) Approximation algorithms. Springer, Berlin"},{"key":"294_CR36","doi-asserted-by":"crossref","unstructured":"Woeginger GJ (2003) Exact algorithms for NP-hard problems: a survey. In: Juenger M, Reinelt G, Rinaldi G (eds) Combinatorial optimization\u2014Eureka! You shrink!, vol 2570 of lecture notes in computer science. Springer, pp 185\u2013207","DOI":"10.1007\/3-540-36478-1_17"},{"key":"294_CR37","doi-asserted-by":"crossref","unstructured":"Xiao M, Nagamochi H (2013) Exact algorithms for maximum independent set. CoRR, abs\/1312.6260","DOI":"10.1007\/978-3-642-45030-3_31"},{"issue":"6","key":"294_CR38","doi-asserted-by":"crossref","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 Comput 3(6):103\u2013128","journal-title":"Theory Comput"}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-015-0294-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10288-015-0294-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-015-0294-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T12:13:00Z","timestamp":1559131980000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10288-015-0294-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,8]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["294"],"URL":"https:\/\/doi.org\/10.1007\/s10288-015-0294-7","relation":{},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"type":"print","value":"1619-4500"},{"type":"electronic","value":"1614-2411"}],"subject":[],"published":{"date-parts":[[2015,7,8]]}}}