{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T12:04:51Z","timestamp":1750161891688},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325113"},{"type":"electronic","value":"9783642325120"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_26","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T22:21:08Z","timestamp":1342822868000},"page":"301-312","source":"Crossref","is-referenced-by-count":9,"title":["Hardness of Vertex Deletion and Project Scheduling"],"prefix":"10.1007","author":[{"given":"Ola","family":"Svensson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1109\/FOCS.2009.23","volume-title":"Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009","author":"N. Bansal","year":"2009","unstructured":"Bansal, N., Khot, S.: Optimal long code test with one free bit. In: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 453\u2013462. IEEE Computer Society, Washington, DC (2009)"},{"key":"26_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/978-3-642-14165-2_22","volume-title":"Automata, Languages and Programming","author":"N. Bansal","year":"2010","unstructured":"Bansal, N., Khot, S.: Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 250\u2013261. Springer, Heidelberg (2010)"},{"issue":"2","key":"26_CR3","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0377-2217(94)00187-H","volume":"81","author":"P. De","year":"1995","unstructured":"De, P., James Dunne, E., Ghosh, J.B., Wells, C.E.: The discrete time-cost tradeoff problem revisited. European Journal of Operational Research\u00a081(2), 225\u2013238 (1995)","journal-title":"European Journal of Operational Research"},{"key":"26_CR4","first-page":"2005","volume":"162","author":"I. Dinur","year":"2004","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annals of Mathematics\u00a0162, 2005 (2004)","journal-title":"Annals of Mathematics"},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G. Even","year":"1998","unstructured":"Even, G., (Seffi) Naor, J., Schieber, B., Sudan, M.: Approximating minimum feedback sets and multi-cuts in directed graphs. Algorithmica\u00a020, 151\u2013174 (1998)","journal-title":"Algorithmica"},{"issue":"2","key":"26_CR6","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1287\/mnsc.7.2.167","volume":"7","author":"D.R. Fulkerson","year":"1961","unstructured":"Fulkerson, D.R.: A network flow computation for project cost curves. Management Science\u00a07(2), 167\u2013178 (1961)","journal-title":"Management Science"},{"issue":"2-3","key":"26_CR7","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s00236-004-0150-2","volume":"41","author":"A. Grigoriev","year":"2004","unstructured":"Grigoriev, A., Woeginger, G.J.: Project scheduling with irregular costs: complexity, approximability, and algorithms. Acta Inf.\u00a041(2-3), 83\u201397 (2004)","journal-title":"Acta Inf."},{"issue":"3","key":"26_CR8","doi-asserted-by":"publisher","first-page":"878","DOI":"10.1137\/090756144","volume":"40","author":"V. Guruswami","year":"2011","unstructured":"Guruswami, V., H\u00e5stad, J., Manokaran, R., Raghavendra, P., Charikar, M.: Beating the random ordering is hard: Every ordering CSP is approximation resistant. SIAM J. Comput.\u00a040(3), 878\u2013914 (2011)","journal-title":"SIAM J. Comput."},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"26_CR10","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1287\/opre.9.3.296","volume":"9","author":"J.E. Kelley","year":"1961","unstructured":"Kelley, J.E.: Critical-path planning and scheduling: Mathematical basis. Operations Research\u00a09(3), 296\u2013320 (1961)","journal-title":"Operations Research"},{"key":"26_CR11","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1145\/1460299.1460318","volume-title":"Critical-path planning and scheduling. Papers presented at the December 1-3, Eastern Joint IRE-AIEE-ACM Computer Conference, IRE-AIEE-ACM 1959 (Eastern)","author":"J.E. Kelley Jr.","year":"1959","unstructured":"Kelley Jr., J.E., Walker, M.R.: Critical-path planning and scheduling. Papers presented at the December 1-3, Eastern Joint IRE-AIEE-ACM Computer Conference, IRE-AIEE-ACM 1959 (Eastern), pp. 160\u2013173. ACM, New York (1959)"},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Reif, J.H. (ed.) STOC, pp. 767\u2013775. ACM (2002)","DOI":"10.1145\/510014.510017"},{"key":"26_CR13","first-page":"422","volume-title":"Proceedings of the 29th Annual Symposium on Foundations of Computer Science, SFCS 1988","author":"T. Leighton","year":"1988","unstructured":"Leighton, T., Rao, S.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, SFCS 1988, pp. 422\u2013431. IEEE Computer Society, Washington, DC (1988)"},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"Mossel, E., O\u2019Donnell, R., Oleszkiewicz, K.: Noise stability of functions with low influences: Invariance and optimality. Annals of Mathematics\u00a0171(1) (2010)","DOI":"10.4007\/annals.2010.171.295"},{"issue":"9","key":"26_CR15","doi-asserted-by":"publisher","first-page":"1091","DOI":"10.1109\/12.312117","volume":"43","author":"D. Paik","year":"1994","unstructured":"Paik, D., Reddy, S., Sahni, S.: Deleting vertices to bound path length. IEEE Trans. Comput.\u00a043(9), 1091\u20131096 (1994)","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"26_CR16","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"P.D. Seymour","year":"1995","unstructured":"Seymour, P.D.: Packing directed circuits fractionally. Combinatorica\u00a015(2), 281\u2013288 (1995)","journal-title":"Combinatorica"},{"issue":"4","key":"26_CR17","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1287\/moor.23.4.909","volume":"23","author":"M. Skutella","year":"1998","unstructured":"Skutella, M.: Approximation algorithms for the discrete time-cost tradeoff problem. Mathematics of Operations Research\u00a023(4), 909\u2013929 (1998)","journal-title":"Mathematics of Operations Research"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32512-0_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:05:28Z","timestamp":1620129928000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}