{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T13:25:10Z","timestamp":1775049910062,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,2,21]],"date-time":"2018-02-21T00:00:00Z","timestamp":1519171200000},"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":["J Comb Optim"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s10878-018-0262-1","type":"journal-article","created":{"date-parts":[[2018,2,21]],"date-time":"2018-02-21T16:20:29Z","timestamp":1519230029000},"page":"937-964","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Subset sum problems with digraph constraints"],"prefix":"10.1007","volume":"36","author":[{"given":"Laurent","family":"Gourv\u00e8s","sequence":"first","affiliation":[]},{"given":"J\u00e9r\u00f4me","family":"Monnot","sequence":"additional","affiliation":[]},{"given":"Lydia","family":"Tlilane","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,2,21]]},"reference":[{"issue":"1\u20132","key":"262_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti P, Kann V (2000) Some APX-completeness results for cubic graphs. Theor Comput Sci 237(1\u20132):123\u2013134","journal-title":"Theor Comput Sci"},{"issue":"1","key":"262_CR2","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0890-5401(03)00060-9","volume":"184","author":"EM Arkin","year":"2003","unstructured":"Arkin EM, Bender MA, Mitchell JSB, Skiena S (2003) The lazy bureaucrat scheduling problem. Inf Comput 184(1):129\u2013146","journal-title":"Inf Comput"},{"issue":"1","key":"262_CR3","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0166-218X(93)90246-K","volume":"41","author":"J Bang-Jensen","year":"1993","unstructured":"Bang-Jensen J, Hell P (1993) Fast algorithms for finding hamiltonian paths and cycles in in-tournament digraphs. Discrete Appl Math 41(1):75\u201379","journal-title":"Discrete Appl Math"},{"issue":"1\u20133","key":"262_CR4","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0166-218X(94)00143-2","volume":"62","author":"RI Becker","year":"1995","unstructured":"Becker RI, Perl Y (1995) The shifting algorithm technique for the partitioning of trees. Discrete Appl Math 62(1\u20133):15\u201334","journal-title":"Discrete Appl Math"},{"key":"262_CR5","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.orl.2014.12.007","volume":"43","author":"S Bervoets","year":"2015","unstructured":"Bervoets S, Merlin V, Woeginger GJ (2015) Vote trading and subset sums. Oper Res Lett 43:99\u2013102","journal-title":"Oper Res Lett"},{"key":"262_CR6","volume-title":"Graph theory 1736\u20131936","author":"NL Biggs","year":"1976","unstructured":"Biggs NL, Lloyd EK, Wilson RJ (1976) Graph theory 1736\u20131936. Clarendon Press, Oxford"},{"issue":"1\u20132","key":"262_CR7","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/s10107-010-0438-7","volume":"133","author":"N Boland","year":"2012","unstructured":"Boland N, Bley A, Fricke C, Froyland G, Sotirov R (2012) Clique-based facets for the precedence constrained knapsack problem. Math Program 133(1\u20132):481\u2013511","journal-title":"Math Program"},{"key":"262_CR8","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1016\/j.jda.2012.04.011","volume":"16","author":"G Borradaile","year":"2012","unstructured":"Borradaile G, Heeringa B, Wilfong GT (2012) The knapsack problem with neighbour constraints. J Discrete Algorithms 16:224\u2013235","journal-title":"J Discrete Algorithms"},{"issue":"11","key":"262_CR9","doi-asserted-by":"publisher","first-page":"1264","DOI":"10.1016\/j.ic.2008.07.003","volume":"206","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk M, Chleb\u00edkov\u00e1 J (2008) Approximation hardness of dominating set problems in bounded degree graphs. Inf Comput 206(11):1264\u20131275","journal-title":"Inf Comput"},{"issue":"4","key":"262_CR10","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1287\/ijoc.9.4.431","volume":"9","author":"G Cho","year":"1997","unstructured":"Cho G, Shaw DX (1997) A depth-first dynamic programming algorithm for the tree knapsack problem. INFORMS J Comput 9(4):431\u2013438","journal-title":"INFORMS J Comput"},{"key":"262_CR11","doi-asserted-by":"crossref","unstructured":"Cieliebak M, Eidenbenz S, Pagourtzis A (2003) Composing equipotent teams. In: Fundamentals of computation theory, 14th international symposium, FCT 2003, Malm\u00f6, Sweden, August 12\u201315, 2003, Proceedings, pp 98\u2013108","DOI":"10.1007\/978-3-540-45077-1_10"},{"issue":"3","key":"262_CR12","first-page":"151","volume":"14","author":"M Cieliebak","year":"2008","unstructured":"Cieliebak M, Eidenbenz S, Pagourtzis A, Schlude K (2008) On the complexity of variations of equal sum subsets. Nord J Comput 14(3):151\u2013172","journal-title":"Nord J Comput"},{"issue":"4","key":"262_CR13","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/s00224-013-9445-4","volume":"53","author":"C Eggermont","year":"2013","unstructured":"Eggermont C, Woeginger GJ (2013) Motion planning with pulley, rope, and baskets. Theory Comput Syst 53(4):569\u2013582","journal-title":"Theory Comput Syst"},{"key":"262_CR14","doi-asserted-by":"crossref","unstructured":"Esfahbod B, Ghodsi M, Sharifi A (2003) Common-deadline lazy bureaucrat scheduling problems. In: Dehne FKHA, Sack J, Smid MHM (eds), Algorithms and data structures, 8th international workshop, WADS 2003, Ottawa, Ontario, Canada, July 30\u2013August 1, 2003, Proceedings, vol 2748 of lecture notes in computer science, Springer, pp 59\u201366","DOI":"10.1007\/978-3-540-45078-8_6"},{"issue":"2","key":"262_CR15","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/s10878-007-9076-2","volume":"15","author":"L Gai","year":"2008","unstructured":"Gai L, Zhang G (2008) On lazy bureaucrat scheduling with common deadlines. J Comb Optim 15(2):191\u2013199","journal-title":"J Comb Optim"},{"key":"262_CR16","volume-title":"Computers and intractability","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D (1979) Computers and intractability, vol 174. Freeman, New York"},{"key":"262_CR17","doi-asserted-by":"crossref","unstructured":"Gourv\u00e8s L, Monnot J, Pagourtzis A (2014) The lazy matroid problem. In: Diaz J, Lanese I, Sangiorgi D (eds), Theoretical computer science\u20148th IFIP TC 1\/WG 2.2 international conference, TCS 2014, Rome, Italy, September 1\u20133, 2014. Proceedings, vol 8705 of lecture notes in computer science, Springer, pp 66\u201377","DOI":"10.1007\/978-3-662-44602-7_6"},{"key":"262_CR18","doi-asserted-by":"crossref","unstructured":"Gourv\u00e8s L, Monnot J, Pagourtzis AT (2013) The lazy bureaucrat problem with common arrivals and deadlines: approximation and mechanism design. In: Fundamentals of Computation Theory, Springer, pp 171\u2013182","DOI":"10.1007\/978-3-642-40164-0_18"},{"key":"262_CR19","doi-asserted-by":"crossref","unstructured":"Hajiaghayi MT, Jain K, Lau LC, Mandoiu II, Russell A, Vazirani VV (2006) Minimum multicolored subgraph problem in multiplex PCR primer set selection and population haplotyping. In: Alexandrov VN, van Albada GD, Sloot PMA, Dongarra J (eds) Computational science\u2014ICCS 2006, 6th international conference, Reading, UK, May 28\u201331, 2006, Proceedings, Part II, vol 3992 of lecture notes in computer science, Springer, pp 758\u2013766","DOI":"10.1007\/11758525_102"},{"issue":"4","key":"262_CR20","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","volume":"46","author":"MM Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson MM (1993) Approximating the minimum maximal independence number. Inf Process Lett 46(4):169\u2013172","journal-title":"Inf Process Lett"},{"key":"262_CR21","unstructured":"Hastad J (1996) Clique is hard to approximate within $$n^{1-\\varepsilon }$$ n 1 - \u03b5 . In: Proceedings 37th annual symposium on foundations of computer science, 1996, IEEE, pp 627\u2013636"},{"issue":"1","key":"262_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.8.1.1","volume":"8","author":"DS Johnson","year":"1983","unstructured":"Johnson DS, Niemi KA (1983) On knapsacks, partitions, and a new dynamic programming technique for trees. Math Oper Res 8(1):1\u201314","journal-title":"Math Oper Res"},{"key":"262_CR23","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":"8","key":"262_CR24","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1016\/j.dam.2006.08.006","volume":"155","author":"SG Kolliopoulos","year":"2007","unstructured":"Kolliopoulos SG, Steiner G (2007) Partially ordered knapsack and applications to scheduling. Discrete Appl Math 155(8):889\u2013897","journal-title":"Discrete Appl Math"},{"key":"262_CR25","doi-asserted-by":"crossref","unstructured":"Kothari A, Suri S, Zhou Y (2005) Interval subset sum and uniform-price auction clearing. In: Wang L (ed) Computing and Combinatorics, 11th annual international conference, COCOON 2005, Kunming, China, August 16\u201329, 2005, Proceedings, vol 3595 of lecture notes in computer science, Springer, pp 608\u2013620","DOI":"10.1007\/11533719_62"},{"issue":"1\u20133","key":"262_CR26","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(98)00147-4","volume":"91","author":"D Manlove","year":"1999","unstructured":"Manlove D (1999) On the algorithmic complexity of twelve covering and independence parameters of graphs. Discrete Appl Math 91(1\u20133):155\u2013175","journal-title":"Discrete Appl Math"},{"issue":"6","key":"262_CR27","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0020-0190(92)90226-L","volume":"42","author":"GJ Woeginger","year":"1992","unstructured":"Woeginger GJ, Yu Z (1992) On the equal-subset-sum problem. Inf Process Lett 42(6):299\u2013302","journal-title":"Inf Process Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0262-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0262-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0262-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,11]],"date-time":"2019-10-11T09:13:26Z","timestamp":1570785206000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0262-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,21]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["262"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0262-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,21]]},"assertion":[{"value":"21 February 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}