{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T01:04:55Z","timestamp":1775523895923,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,3,28]],"date-time":"2015-03-28T00:00:00Z","timestamp":1427500800000},"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":["Algorithmica"],"published-print":{"date-parts":[[2016,3]]},"DOI":"10.1007\/s00453-015-9992-y","type":"journal-article","created":{"date-parts":[[2015,3,28]],"date-time":"2015-03-28T22:14:28Z","timestamp":1427580868000},"page":"1148-1173","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Vertex Cover Meets Scheduling"],"prefix":"10.1007","volume":"74","author":[{"given":"Leah","family":"Epstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Asaf","family":"Levin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,3,28]]},"reference":[{"issue":"2","key":"9992_CR1","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1006\/jagm.1995.1008","volume":"18","author":"Y Azar","year":"1995","unstructured":"Azar, Y., Naor, J., Rom, R.: The competitiveness of on-line assignments. J. Algorithms 18(2), 221\u2013237 (1995)","journal-title":"J. Algorithms"},{"issue":"2","key":"9992_CR2","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R Bar-Yehuda","year":"1981","unstructured":"Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2), 198\u2013203 (1981)","journal-title":"J. Algorithms"},{"issue":"4","key":"9992_CR3","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"DG Corneil","year":"2005","unstructured":"Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput. 34(4), 825\u2013847 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9992_CR4","doi-asserted-by":"crossref","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162(1), 439\u2013485 (2005)","journal-title":"Ann. Math."},{"issue":"2","key":"9992_CR5","doi-asserted-by":"crossref","first-page":"141","DOI":"10.7155\/jgaa.00065","volume":"7","author":"W Espelage","year":"2003","unstructured":"Espelage, W., Gurski, F., Wanke, E.: Deciding clique-width for graphs of bounded tree-width. J. Graph Algorithms Appl. 7(2), 141\u2013180 (2003)","journal-title":"J. Graph Algorithms Appl."},{"key":"9992_CR6","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W Fernandez de la Vega","year":"1981","unstructured":"Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within $$1+\\varepsilon $$ 1 + \u03b5 in linear time. Combinatorica 1, 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"9992_CR7","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessor anomalies. Bell Syst. Tech. J. 45, 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"key":"9992_CR8","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17, 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"9992_CR9","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"issue":"3","key":"9992_CR10","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. 11(3), 555\u2013556 (1982)","journal-title":"SIAM J. Comput."},{"key":"9992_CR11","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/BF01585160","volume":"62","author":"DS Hochbaum","year":"1993","unstructured":"Hochbaum, D.S., Megiddo, N., Naor, J., Tamir, A.: Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Math. Program. 62, 69\u201383 (1993)","journal-title":"Math. Program."},{"issue":"1","key":"9992_CR12","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34(1), 144\u2013162 (1987)","journal-title":"J. ACM"},{"issue":"3","key":"9992_CR13","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"DS Hochbaum","year":"1988","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM J. Comput. 17(3), 539\u2013551 (1988)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9992_CR14","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E Horowitz","year":"1976","unstructured":"Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23(2), 317\u2013327 (1976)","journal-title":"J. ACM"},{"key":"9992_CR15","first-page":"256","volume":"3","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Computi. 3, 256\u2013278 (1974)","journal-title":"SIAM J. Computi."},{"key":"9992_CR16","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd annual symposium on foundations of computer science (FOCS\u201982), pp 312\u2013320 (1982)","DOI":"10.1109\/SFCS.1982.61"},{"issue":"3","key":"9992_CR17","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"9992_CR18","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"JK Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259\u2013271 (1990)","journal-title":"Math. Program."},{"issue":"4","key":"9992_CR19","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra Jr, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"9992_CR20","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter Jr, L.E.: Vertex packings: structural properties and algorithms. Math. Program. 8(1), 232\u2013248 (1975)","journal-title":"Math. Program."},{"key":"9992_CR21","doi-asserted-by":"crossref","unstructured":"Nip, K., Wang, Z.: Combination of two-machine flow shop scheduling and shortest path problems. In: Proc. of the 19th international conference on computing and combinatorics (COCOON\u201913), pp 680\u2013687 (2013)","DOI":"10.1007\/978-3-642-38768-5_60"},{"issue":"1","key":"9992_CR22","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/s10878-013-9670-4","volume":"29","author":"K Nip","year":"2015","unstructured":"Nip, K., Wang, Z., Nobibon, F.T., Leus, R.: A combination of flow shop scheduling and the shortest path problem. J. Comb. Optim. 29(1), 36\u201352 (2015)","journal-title":"J. Comb. Optim."},{"key":"9992_CR23","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"DB Shmoys","year":"1993","unstructured":"Shmoys, D.B., Tardos, \u00c9.: An approximation algorithm for the generalized assignment problem. Math. Program. 62, 461\u2013474 (1993)","journal-title":"Math. Program."},{"key":"9992_CR24","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/j.tcs.2012.06.003","volume":"460","author":"Z Wang","year":"2012","unstructured":"Wang, Z., Cui, Z.: Combination of parallel machine scheduling and vertex cover. Theor. Comput. Sci. 460, 10\u201315 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"9992_CR25","first-page":"577","volume":"10","author":"Z Wang","year":"2014","unstructured":"Wang, Z., Hong, W., He, D.: A combination of parallel machine scheduling and the covering problem. Pac. J. Optim. 10, 577\u2013591 (2014)","journal-title":"Pac. J. Optim."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9992-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-9992-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9992-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:23Z","timestamp":1559072843000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-9992-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,28]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["9992"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-9992-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,28]]}}}