{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T16:27:52Z","timestamp":1747153672661,"version":"3.40.5"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,5,1]],"date-time":"2023-05-01T00:00:00Z","timestamp":1682899200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,1]],"date-time":"2023-05-01T00:00:00Z","timestamp":1682899200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2023,5]]},"DOI":"10.1007\/s10878-023-01027-4","type":"journal-article","created":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T05:02:00Z","timestamp":1683003720000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Precedence-constrained covering problems with multiplicity constraints"],"prefix":"10.1007","volume":"45","author":[{"given":"Stavros G.","family":"Kolliopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7623-9419","authenticated-orcid":false,"given":"Antonis","family":"Skarlatos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,2]]},"reference":[{"issue":"2","key":"1027_CR1","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s10107-014-0803-z","volume":"153","author":"T Carnes","year":"2015","unstructured":"Carnes T, Shmoys DB (2015) Primal-dual schema for capacitated covering problems. Math Program 153(2):289\u2013308. https:\/\/doi.org\/10.1007\/s10107-014-0803-z","journal-title":"Math Program"},{"key":"1027_CR2","unstructured":"Carr R.D, Fleischer L, Leung V.J, Phillips C.A (2000) Strengthening integrality gaps for capacitated network design and covering problems. In: SODA. pp. 106\u2013115"},{"key":"1027_CR3","doi-asserted-by":"crossref","unstructured":"Dilworth R.P (2009) A decomposition theorem for partially ordered sets. In: Classic papers in combinatorics. pp. 139\u2013144. Springer: Berlin","DOI":"10.1007\/978-0-8176-4842-8_10"},{"issue":"5","key":"1027_CR4","doi-asserted-by":"publisher","first-page":"1129","DOI":"10.1137\/S0097539704443057","volume":"34","author":"I Dinur","year":"2005","unstructured":"Dinur I, Guruswami V, Khot S, Regev O (2005) A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM J Comput 34(5):1129\u20131146. https:\/\/doi.org\/10.1137\/S0097539704443057","journal-title":"SIAM J Comput"},{"key":"1027_CR5","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.dam.2015.05.020","volume":"194","author":"D Espinoza","year":"2015","unstructured":"Espinoza D, Goycoolea M, Moreno E (2015) The precedence constrained knapsack problem: separating maximally violated inequalities. Discrete Appl Math 194:65\u201380. https:\/\/doi.org\/10.1016\/j.dam.2015.05.020","journal-title":"Discrete Appl Math"},{"key":"1027_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin"},{"issue":"3","key":"1027_CR7","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2-epsilon. J Comput Syst Sci 74(3):335\u2013349. https:\/\/doi.org\/10.1016\/j.jcss.2007.06.019","journal-title":"J Comput Syst Sci"},{"key":"1027_CR8","doi-asserted-by":"crossref","unstructured":"Kolliopoulos SG, Skarlatos A (2021) Precedence-constrained covering problems with multiplicity constraints. In: K\u00f6nemann J, Peis B (eds) Approximation and online algorithms - 19th international workshop, WAOA 2021, vol 12982. Lecture Notes in Computer Science. Springer: Berlin, pp. 234\u2013251","DOI":"10.1007\/978-3-030-92702-8_15"},{"key":"1027_CR9","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/j.jcss.2005.05.002","volume":"71","author":"SG Kolliopoulos","year":"2005","unstructured":"Kolliopoulos SG, Young NE (2005) Approximation algorithms for covering\/ packing integer programs. J Comput Syst Sci 71:495\u2013505","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"1027_CR10","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s00453-012-9629-3","volume":"66","author":"C Koufogiannakis","year":"2013","unstructured":"Koufogiannakis C, Young NE (2013) Greedy $$\\Delta $$-approximation algorithm for covering with arbitrary constraints and submodular cost. Algorithmica 66(1):113\u2013152. https:\/\/doi.org\/10.1007\/s00453-012-9629-3","journal-title":"Algorithmica"},{"issue":"3","key":"1027_CR11","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1007\/s00453-016-0174-3","volume":"78","author":"ST McCormick","year":"2017","unstructured":"McCormick ST, Peis B, Verschae J, Wierz A (2017) Primal-dual algorithms for precedence constrained covering problems. Algorithmica 78(3):771\u2013787","journal-title":"Algorithmica"},{"key":"1027_CR12","doi-asserted-by":"crossref","unstructured":"Pritchard D, Chakrabarty D (2011) Approximability of sparse integer programs. Algorithmica 61(1):75\u201393","DOI":"10.1007\/s00453-010-9431-z"},{"key":"1027_CR13","doi-asserted-by":"crossref","unstructured":"Trevisan L (2001) Non-approximability results for optimization problems on bounded degree instances. In: Proceedings of the thirty-third annual ACM symposium on theory of computing. pp. 453\u2013461","DOI":"10.1145\/380752.380839"},{"issue":"1","key":"1027_CR14","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0166-218X(02)00427-4","volume":"131","author":"GJ Woeginger","year":"2003","unstructured":"Woeginger GJ (2003) On the approximability of average completion time scheduling under precedence constraints. Discrete Appl Math 131(1):237\u2013252","journal-title":"Discrete Appl Math"},{"key":"1027_CR15","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/BF01580441","volume":"8","author":"L Wolsey","year":"1975","unstructured":"Wolsey L (1975) Facets for a linear inequality in 0\u20131 variables. Math Program 8:168\u2013175","journal-title":"Math Program"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-023-01027-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-023-01027-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-023-01027-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,27]],"date-time":"2023-05-27T03:41:59Z","timestamp":1685158919000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-023-01027-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["1027"],"URL":"https:\/\/doi.org\/10.1007\/s10878-023-01027-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2023,5]]},"assertion":[{"value":"24 March 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 May 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"106"}}