{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T15:59:25Z","timestamp":1774022365727,"version":"3.50.1"},"reference-count":14,"publisher":"World Scientific Pub Co Pte Ltd","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2017,12]]},"abstract":"<jats:p>This paper studies the combination problem of parallel machine scheduling and the vertex cover problem. Wang and Cui developed a [Formula: see text]-approximation algorithm for this problem [13], where [Formula: see text] is the number of parallel machines. We reduce the approximation factors from [Formula: see text] to [Formula: see text] for [Formula: see text], from [Formula: see text] to [Formula: see text] for [Formula: see text], and to [Formula: see text] for [Formula: see text].<\/jats:p>","DOI":"10.1142\/s0129054117500344","type":"journal-article","created":{"date-parts":[[2018,2,26]],"date-time":"2018-02-26T06:42:48Z","timestamp":1519627368000},"page":"977-992","source":"Crossref","is-referenced-by-count":3,"title":["Improved Approximation Algorithm for the Combination of Parallel Machine Scheduling and Vertex Cover"],"prefix":"10.1142","volume":"28","author":[{"given":"Wenyi","family":"Hong","sequence":"first","affiliation":[{"name":"Department of Mathematical Sciences, Tsinghua University, Beijing 100084, P. R. China"}]},{"given":"Zhenbo","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Tsinghua University, Beijing 100084, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2018,2,25]]},"reference":[{"key":"S0129054117500344BIB001","doi-asserted-by":"publisher","DOI":"10.1145\/1041680.1041683"},{"key":"S0129054117500344BIB002","first-page":"27","volume":"25","author":"Bar-Yehuda R.","year":"1985","journal-title":"Ann. Discrete Math."},{"key":"S0129054117500344BIB003","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.439"},{"key":"S0129054117500344BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-9992-y"},{"key":"S0129054117500344BIB005","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"S0129054117500344BIB006","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"S0129054117500344BIB007","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"Hochbaum D. S.","year":"1997"},{"key":"S0129054117500344BIB008","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7535"},{"key":"S0129054117500344BIB009","first-page":"41:1","volume":"5","author":"Karakostas G.","year":"2009","journal-title":"ACM T. Algorithms"},{"key":"S0129054117500344BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"S0129054117500344BIB011","doi-asserted-by":"crossref","DOI":"10.1201\/9780203489802","volume-title":"Handbook of Scheduling","author":"Leung J. Y.","year":"2004"},{"key":"S0129054117500344BIB012","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321934"},{"key":"S0129054117500344BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.06.003"},{"key":"S0129054117500344BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100262"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054117500344","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,14]],"date-time":"2022-08-14T21:44:48Z","timestamp":1660513488000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054117500344"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12]]},"references-count":14,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2018,2,25]]},"published-print":{"date-parts":[[2017,12]]}},"alternative-id":["10.1142\/S0129054117500344"],"URL":"https:\/\/doi.org\/10.1142\/s0129054117500344","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12]]}}}