{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:24:25Z","timestamp":1742912665691,"version":"3.40.3"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319487489"},{"type":"electronic","value":"9783319487496"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-48749-6_7","type":"book-chapter","created":{"date-parts":[[2016,10,30]],"date-time":"2016-10-30T04:16:59Z","timestamp":1477801019000},"page":"92-106","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Approximability of Partial\u00a0VC\u00a0Dimension"],"prefix":"10.1007","author":[{"given":"Cristina","family":"Bazgan","sequence":"first","affiliation":[]},{"given":"Florent","family":"Foucaud","sequence":"additional","affiliation":[]},{"given":"Florian","family":"Sikora","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,31]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: The shortest vector problem in L2 is NP-hard for randomized reductions. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC 1998), pp. 10\u201319 (1998)","DOI":"10.1145\/276698.276705"},{"key":"7_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"624","DOI":"10.1007\/3-540-45022-X_53","volume-title":"Automata, Languages and Programming","author":"VSA Kumar","year":"2000","unstructured":"Kumar, V.S.A., Arya, S., Ramesh, H.: Hardness of set cover with intersection 1. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 624\u2013635. Springer, Heidelberg (2000)"},{"issue":"1","key":"7_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.jda.2014.05.001","volume":"27","author":"C Bazgan","year":"2014","unstructured":"Bazgan, C., Chopin, M., Nichterlein, A., Sikora, F.: Parameterized approximability of maximizing the spread of influence in networks. J. Discrete Algorithms 27, 54\u201365 (2014)","journal-title":"J. Discrete Algorithms"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an \n                      \n                        \n                      \n                      $$O(n^{1\/4})$$\n                     approximation for densest \n                      \n                        \n                      \n                      $$k$$\n                    -subgraph. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC 2010), pp. 201\u2013210 (2010)","DOI":"10.1145\/1806689.1806719"},{"issue":"12","key":"7_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H Bodlaender","year":"1998","unstructured":"Bodlaender, H.: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209(12), 1\u201345 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"1068","DOI":"10.1016\/j.ejc.2006.04.003","volume":"28","author":"B Bollob\u00e1s","year":"2007","unstructured":"Bollob\u00e1s, B., Scott, A.D.: On separating systems. Eur. J. Comb. 28, 1068\u20131071 (2007)","journal-title":"Eur. J. Comb."},{"issue":"2","key":"7_CR8","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0095-8956(72)90025-1","volume":"12","author":"JA Bondy","year":"1972","unstructured":"Bondy, J.A.: Induced subsets. J. Comb. Theory, Ser. B 12(2), 201\u2013202 (1972)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"7_CR9","unstructured":"Bousquet, N.: Hitting sets: VC-dimension and multicut. Ph.D. thesis, Universit\u00e9 Montepellier II, France (2013). \n                      http:\/\/tel.archives-ouvertes.fr\/tel-01012106\/"},{"issue":"4","key":"7_CR10","doi-asserted-by":"publisher","first-page":"2047","DOI":"10.1137\/14097879X","volume":"29","author":"N Bousquet","year":"2015","unstructured":"Bousquet, N., Lagoutte, A., Li, Z., Parreau, A., Thomass\u00e9, S.: Identifying codes in hereditary classes of graphs and VC-dimension. SIAM J. Discrete Math. 29(4), 2047\u20132064 (2015)","journal-title":"SIAM J. Discrete Math."},{"issue":"12","key":"7_CR11","doi-asserted-by":"publisher","first-page":"2302","DOI":"10.1016\/j.disc.2015.05.026","volume":"338","author":"N Bousquet","year":"2015","unstructured":"Bousquet, N., Thomass\u00e9, S.: VC-dimension and Erd\u0151s-P\u00f3sa property of graphs. Discrete Math. 338(12), 2302\u20132317 (2015)","journal-title":"Discrete Math."},{"key":"7_CR12","unstructured":"Bringmann, K., Kozma, L., Moran, S., Narayanaswamy, N.S.: Hitting Set in hypergraphs of low VC-dimension. Manuscript (2015). \n                      http:\/\/arxiv.org\/abs\/1512.00481"},{"issue":"9","key":"7_CR13","doi-asserted-by":"publisher","first-page":"1344","DOI":"10.1016\/j.dam.2005.05.036","volume":"154","author":"M Bruglieri","year":"2006","unstructured":"Bruglieri, M., Ehrgott, M., Hamacher, H.W., Maffioli, F.: An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints. Discrete Appl. Math. 154(9), 1344\u20131357 (2006)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"7_CR14","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1093\/comjnl\/bxm086","volume":"51","author":"L Cai","year":"2007","unstructured":"Cai, L.: Parameterized complexity of cardinality constrained optimization problems. Comput. J. 51(1), 102\u2013121 (2007)","journal-title":"Comput. J."},{"issue":"1","key":"7_CR15","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/S0304-3975(01)00343-7","volume":"289","author":"L Cai","year":"2002","unstructured":"Cai, L., Juedes, D., Kanj, I.: The inapproximability of non-NP-hard optimization problems. Theoret. Comput. Sci. 289(1), 553\u2013571 (2002)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"7_CR16","doi-asserted-by":"publisher","first-page":"403","DOI":"10.3934\/amc.2008.2.403","volume":"2","author":"E Charbit","year":"2008","unstructured":"Charbit, E., Charon, I., Cohen, G., Hudry, O., Lobstein, A.: Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity. Adv. Math. Commun. 2(4), 403\u2013420 (2008)","journal-title":"Adv. Math. Commun."},{"issue":"2","key":"7_CR17","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10878-006-7137-6","volume":"11","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: On the computational hardness based on linear FPT-reductions. J. Comb. Optim. 11(2), 231\u2013247 (2006)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"7_CR18","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s00453-014-9948-7","volume":"74","author":"R Crowston","year":"2016","unstructured":"Crowston, R., Gutin, G., Jones, M., Muciaccia, G., Yeo, A.: Parameterizations of test cover with bounded test sizes. Algorithmica 74(1), 367\u2013384 (2016)","journal-title":"Algorithmica"},{"key":"7_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/978-3-642-32589-2_27","volume-title":"Mathematical Foundations of Computer Science 2012","author":"R Crowston","year":"2012","unstructured":"Crowston, R., Gutin, G., Jones, M., Saurabh, S., Yeo, A.: Parameterized study of the test cover problem. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 283\u2013295. Springer, Heidelberg (2012)"},{"key":"7_CR20","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/s10107-003-0414-6","volume":"98","author":"KMJ Bontridder De","year":"2003","unstructured":"De Bontridder, K.M.J., Halld\u00f3rsson, B.V., Halld\u00f3rsson, M.M., Hurkens, C.A.J., Lenstra, J.K., Ravi, R., Stougie, L.: Approximation algorithms for the test cover problem. Math. Program. Ser. B 98, 477\u2013491 (2003)","journal-title":"Math. Program. Ser. B"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Evans, P.A., Fellows, M.R.: Parameterized learning complexity. In: Proceedings of the 6th Annual Conference on Computational Learning Theory (COLT 1993), pp. 51\u201357 (1993)","DOI":"10.1145\/168304.168311"},{"issue":"16","key":"7_CR22","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1016\/j.ipl.2011.05.016","volume":"111","author":"FV Fomin","year":"2011","unstructured":"Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Subexponential algorithms for partial cover problems. Inf. Process. Lett. 111(16), 814\u2013818 (2011)","journal-title":"Inf. Process. Lett."},{"key":"7_CR23","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.jda.2014.08.004","volume":"31","author":"F Foucaud","year":"2015","unstructured":"Foucaud, F.: Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes. J. Discrete Algorithms 31, 48\u201368 (2015)","journal-title":"J. Discrete Algorithms"},{"key":"7_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1007\/978-3-662-53174-7_32","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F Foucaud","year":"2016","unstructured":"Foucaud, F., Mertzios, G.B., Naserasr, R., Parreau, A., Valicov, P.: Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs. In: Mayr, E.W. (ed.) WG 2015. LNCS, vol. 9224, pp. 456\u2013471. Springer, Heidelberg (2016). doi:\n                      10.1007\/978-3-662-53174-7_32"},{"key":"7_CR25","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman, New York (1979)"},{"issue":"4","key":"7_CR26","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1007\/s00373-013-1311-2","volume":"30","author":"MA Henning","year":"2014","unstructured":"Henning, M.A., Yeo, A.: Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs. Graphs Comb. 30(4), 909\u2013932 (2014)","journal-title":"Graphs Comb."},{"key":"7_CR27","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1109\/18.661507","volume":"44","author":"MG Karpovsky","year":"1998","unstructured":"Karpovsky, M.G., Chakrabarty, K., Levitin, L.B.: On a new class of codes for identifying vertices in graphs. IEEE Trans. Inf. Theory 44, 599\u2013611 (1998)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"7_CR28","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1137\/S0097539705447037","volume":"36","author":"S Khot","year":"2006","unstructured":"Khot, S.: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36(4), 1025\u20131071 (2006)","journal-title":"SIAM J. Comput."},{"key":"7_CR29","doi-asserted-by":"crossref","unstructured":"Kneis, J., M\u00f6lle, D., Rossmanith, P.: Partial vs. complete domination: \n                      \n                        \n                      \n                      $$t$$\n                    -dominating set. In: Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2007), pp. 367\u2013376 (2007)","DOI":"10.1007\/978-3-540-69507-3_31"},{"issue":"3","key":"7_CR30","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0166-218X(96)00137-0","volume":"77","author":"E Kranakis","year":"1997","unstructured":"Kranakis, E., Krizanc, D., Ruf, B., Urrutia, J., Woeginger, G.J.: The VC-dimension of set systems defined by graphs. Discrete Appl. Math. 77(3), 237\u2013257 (1997)","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"7_CR31","doi-asserted-by":"publisher","first-page":"2008","DOI":"10.1137\/S0097539700373039","volume":"30","author":"D Micciancio","year":"2001","unstructured":"Micciancio, D.: The shortest vector in a lattice is hard to approximate to within some constant. SIAM J. Comput. 30(6), 2008\u20132035 (2001)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"7_CR32","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1017\/S0963548309990344","volume":"18","author":"T M\u00fcller","year":"2009","unstructured":"M\u00fcller, T., Sereni, J.-S.: Identifying and locating-dominating codes in (random) geometric networks. Comb. Probab. Comput. 18(6), 925\u2013952 (2009)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"7_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.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"7_CR34","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1006\/jcss.1996.0058","volume":"53","author":"CH Papadimitriou","year":"1996","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On limited nondeterminism and the complexity of the V-C dimension. J. Comput. Syst. Sci. 53(2), 161\u2013170 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"7_CR35","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E Petrank","year":"1994","unstructured":"Petrank, E.: The hardness of approximation: gap location. Comput. Complex. 4, 133\u2013157 (1994)","journal-title":"Comput. Complex."},{"key":"7_CR36","first-page":"97","volume":"45","author":"PJ Slater","year":"1984","unstructured":"Slater, P.J., Rall, D.F.: On location-domination numbers for certain classes of graphs. Congr. Numerantium 45, 97\u2013106 (1984)","journal-title":"Congr. Numerantium"},{"key":"7_CR37","first-page":"75","volume":"22","author":"A R\u00e9nyi","year":"1961","unstructured":"R\u00e9nyi, A.: On random generating elements of a finite Boolean algebra. Acta Sci. Math. Szeged 22, 75\u201381 (1961)","journal-title":"Acta Sci. Math. Szeged"},{"key":"7_CR38","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N Sauer","year":"1972","unstructured":"Sauer, N.: On the density of families of sets. J. Comb. Theory Ser. A 13, 145\u2013147 (1972)","journal-title":"J. Comb. Theory Ser. A"},{"key":"7_CR39","doi-asserted-by":"publisher","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S Shelah","year":"1972","unstructured":"Shelah, S.: A combinatorial problem; stability and order for models and theories in infinitary languages. Pac. J. Math. 41, 247\u2013261 (1972)","journal-title":"Pac. J. Math."},{"key":"7_CR40","first-page":"264","volume":"16","author":"VN Vapnik","year":"1971","unstructured":"Vapnik, V.N., \u010cervonenkis, A.J.: The uniform convergence of frequencies of the appearance of events to their probabilities. Akademija Nauk SSSR 16, 264\u2013279 (1971)","journal-title":"Akademija Nauk SSSR"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-48749-6_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T22:20:08Z","timestamp":1558477208000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-48749-6_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319487489","9783319487496"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-48749-6_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"31 October 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hong Kong","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 December 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 December 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conference.cs.cityu.edu.hk\/cocoa2016\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}