{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T16:11:19Z","timestamp":1742919079503,"version":"3.40.3"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030394783"},{"type":"electronic","value":"9783030394790"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"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":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-39479-0_12","type":"book-chapter","created":{"date-parts":[[2020,1,24]],"date-time":"2020-01-24T20:03:47Z","timestamp":1579896227000},"page":"170-187","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Precedence-Constrained Scheduling and Min-Sum Set Cover"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8062-3632","authenticated-orcid":false,"given":"Felix","family":"Happach","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9595-459X","authenticated-orcid":false,"given":"Andreas S.","family":"Schulz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,25]]},"reference":[{"issue":"4","key":"12_CR1","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1007\/s00453-008-9251-6","volume":"53","author":"C Amb\u00fchl","year":"2009","unstructured":"Amb\u00fchl, C., Mastrolilli, M.: Single machine precedence constrained scheduling is a vertex cover problem. Algorithmica 53(4), 488\u2013503 (2009). \nhttps:\/\/doi.org\/10.1007\/s00453-008-9251-6","journal-title":"Algorithmica"},{"issue":"4","key":"12_CR2","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1287\/moor.1110.0512","volume":"36","author":"C Amb\u00fchl","year":"2011","unstructured":"Amb\u00fchl, C., Mastrolilli, M., Mutsanas, N., Svensson, O.: On the approximability of single-machine scheduling with precedence constraints. Math. Oper. Res. 36(4), 653\u2013669 (2011). \nhttps:\/\/doi.org\/10.1287\/moor.1110.0512","journal-title":"Math. Oper. Res."},{"key":"12_CR3","doi-asserted-by":"publisher","unstructured":"Azar, Y., Gamzu, I., Yin, X.: Multiple intents re-ranking. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 669\u2013678. ACM (2009). \nhttps:\/\/doi.org\/10.1145\/1536414.1536505","DOI":"10.1145\/1536414.1536505"},{"key":"12_CR4","doi-asserted-by":"publisher","unstructured":"Bansal, N., Gupta, A., Krishnaswamy, R.: A constant factor approximation algorithm for generalized min-sum set cover. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1539\u20131545. SIAM (2010). \nhttps:\/\/doi.org\/10.1137\/1.9781611973075.125","DOI":"10.1137\/1.9781611973075.125"},{"key":"12_CR5","doi-asserted-by":"publisher","unstructured":"Bansal, N., Khot, S.: Optimal long code test with one free bit. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 453\u2013462. IEEE (2009). \nhttps:\/\/doi.org\/10.1109\/FOCS.2009.23","DOI":"10.1109\/FOCS.2009.23"},{"issue":"2","key":"12_CR6","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1006\/inco.1997.2677","volume":"140","author":"A Bar-Noy","year":"1998","unstructured":"Bar-Noy, A., Bellare, M., Halld\u00f3rsson, M.M., Shachnai, H., Tamir, T.: On chromatic sums and distributed resource allocation. Inf. Comput. 140(2), 183\u2013202 (1998). \nhttps:\/\/doi.org\/10.1006\/inco.1997.2677","journal-title":"Inf. Comput."},{"key":"12_CR7","doi-asserted-by":"publisher","unstructured":"Charikar, M., Naamad, Y., Wirth, A.: On approximating target set selection. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Leibniz International Proceedings in Informatics (LIPIcs), vol. 60, pp. 4:1\u20134:16 (2016). \nhttps:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2016.4","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2016.4"},{"issue":"1\u20132","key":"12_CR8","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0166-218X(98)00143-7","volume":"98","author":"C Chekuri","year":"1999","unstructured":"Chekuri, C., Motwani, R.: Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discrete Appl. Math. 98(1\u20132), 29\u201338 (1999). \nhttps:\/\/doi.org\/10.1016\/S0166-218X(98)00143-7","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"12_CR9","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/S0097539797327180","volume":"31","author":"C Chekuri","year":"2001","unstructured":"Chekuri, C., Motwani, R., Natarajan, B., Stein, C.: Approximation techniques for average completion time scheduling. SIAM J. Comput. 31(1), 146\u2013166 (2001). \nhttps:\/\/doi.org\/10.1137\/S0097539797327180","journal-title":"SIAM J. Comput."},{"issue":"5","key":"12_CR10","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0167-6377(99)00056-5","volume":"25","author":"FA Chudak","year":"1999","unstructured":"Chudak, F.A., Hochbaum, D.S.: A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Oper. Res. Lett. 25(5), 199\u2013204 (1999). \nhttps:\/\/doi.org\/10.1016\/S0167-6377(99)00056-5","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"12_CR11","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1287\/moor.1050.0158","volume":"30","author":"JR Correa","year":"2005","unstructured":"Correa, J.R., Schulz, A.S.: Single-machine scheduling with precedence constraints. Math. Oper. Res. 30(4), 1005\u20131021 (2005). \nhttps:\/\/doi.org\/10.1287\/moor.1050.0158","journal-title":"Math. Oper. Res."},{"key":"12_CR12","doi-asserted-by":"publisher","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 624\u2013633. ACM (2014). \nhttps:\/\/doi.org\/10.1145\/2591796.2591884","DOI":"10.1145\/2591796.2591884"},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/978-3-540-24592-6_10","volume-title":"Approximation and Online Algorithms","author":"T Erlebach","year":"2004","unstructured":"Erlebach, T., K\u00e4\u00e4b, V., M\u00f6hring, R.H.: Scheduling AND\/OR-networks on identical parallel machines. In: Solis-Oba, R., Jansen, K. (eds.) WAOA 2003. LNCS, vol. 2909, pp. 123\u2013136. Springer, Heidelberg (2004). \nhttps:\/\/doi.org\/10.1007\/978-3-540-24592-6_10"},{"key":"12_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/3-540-45753-4_10","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"U Feige","year":"2002","unstructured":"Feige, U., Lov\u00e1sz, L., Tetali, P.: Approximating min-sum set cover. In: Jansen, K., Leonardi, S., Vazirani, V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 94\u2013107. Springer, Heidelberg (2002). \nhttps:\/\/doi.org\/10.1007\/3-540-45753-4_10"},{"issue":"4","key":"12_CR15","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s00453-004-1110-5","volume":"40","author":"U Feige","year":"2004","unstructured":"Feige, U., Lov\u00e1sz, L., Tetali, P.: Approximating min sum set cover. Algorithmica 40(4), 219\u2013234 (2004). \nhttps:\/\/doi.org\/10.1007\/s00453-004-1110-5","journal-title":"Algorithmica"},{"key":"12_CR16","unstructured":"Goemans, M.X.: Cited as personal communication in [35] (1996)"},{"issue":"2","key":"12_CR17","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1137\/S089548019936223X","volume":"15","author":"MX Goemans","year":"2002","unstructured":"Goemans, M.X., Queyranne, M., Schulz, A.S., Skutella, M., Wang, Y.: Single machine scheduling with release dates. SIAM J. Discrete Math. 15(2), 165\u2013192 (2002). \nhttps:\/\/doi.org\/10.1137\/S089548019936223X","journal-title":"SIAM J. Discrete Math."},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume-title":"Discrete Optimization II, Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium co-sponsored by IBM Canada and SIAM Banff, Aha. and V","author":"R.L. Graham","year":"1979","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Annals of Discrete Mathematics, vol. 5, pp. 287\u2013326. Elsevier (1979). \nhttps:\/\/doi.org\/10.1016\/S0167-5060(08)70356-X"},{"issue":"3","key":"12_CR19","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/moor.22.3.513","volume":"22","author":"LA Hall","year":"1997","unstructured":"Hall, L.A., Schulz, A.S., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: off-line and on-line approximation algorithms. Math. Oper. Res. 22(3), 513\u2013544 (1997). \nhttps:\/\/doi.org\/10.1287\/moor.22.3.513","journal-title":"Math. Oper. Res."},{"key":"12_CR20","unstructured":"Hall, L.A., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: off-line and on-line algorithms. In: Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 142\u2013151. SIAM (1996)"},{"key":"12_CR21","unstructured":"Happach, F.: Makespan minimization with OR-precedence constraints. arXiv preprint \narXiv:1907.08111\n\n (2019)"},{"issue":"3","key":"12_CR22","doi-asserted-by":"publisher","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). \nhttps:\/\/doi.org\/10.1137\/0211045","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"12_CR23","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/s10107-013-0651-2","volume":"145","author":"S Im","year":"2014","unstructured":"Im, S., Sviridenko, M., van der Zwaan, R.: Preemptive and non-preemptive generalized min sum set cover. Math. Program. 145(1\u20132), 377\u2013401 (2014). \nhttps:\/\/doi.org\/10.1007\/s10107-013-0651-2","journal-title":"Math. Program."},{"issue":"6","key":"12_CR24","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1016\/j.orl.2004.11.009","volume":"33","author":"B Johannes","year":"2005","unstructured":"Johannes, B.: On the complexity of scheduling unit-time jobs with OR-precedence constraints. Oper. Res. Lett. 33(6), 587\u2013596 (2005). \nhttps:\/\/doi.org\/10.1016\/j.orl.2004.11.009","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"12_CR25","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256\u2013278 (1974). \nhttps:\/\/doi.org\/10.1016\/S0022-0000(74)80044-9","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR26","doi-asserted-by":"publisher","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 767\u2013775. ACM (2002). \nhttps:\/\/doi.org\/10.1145\/509907.510017","DOI":"10.1145\/509907.510017"},{"issue":"1","key":"12_CR27","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"J. K. Lenstra","year":"1978","unstructured":"Lenstra, J.K., Rinnooy Kan, A.H.G.: Complexity of scheduling under precedence constraints. Oper. Res. 26(1), 22\u201335 (1978). \nhttps:\/\/doi.org\/10.1287\/opre.26.1.22","journal-title":"Operations Research"},{"issue":"4","key":"12_CR28","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13(4), 383\u2013390 (1975). \nhttps:\/\/doi.org\/10.1016\/0012-365X(75)90058-8","journal-title":"Discrete Math."},{"issue":"6","key":"12_CR29","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1287\/opre.51.6.981.24912","volume":"51","author":"F Margot","year":"2003","unstructured":"Margot, F., Queyranne, M., Wang, Y.: Decompositions, network flows, and a precedence constrained single-machine scheduling problem. Oper. Res. 51(6), 981\u2013992 (2003). \nhttps:\/\/doi.org\/10.1287\/opre.51.6.981.24912","journal-title":"Oper. Res."},{"key":"12_CR30","doi-asserted-by":"publisher","unstructured":"McClintock, J., Mestre, J., Wirth, A.: Precedence-constrained min sum set cover. In: 28th International Symposium on Algorithms and Computation. Leibniz International Proceedings in Informatics (LIPIcs), vol. 92, pp. 55:1\u201355:12 (2017). \nhttps:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2017.55","DOI":"10.4230\/LIPIcs.ISAAC.2017.55"},{"key":"12_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-540-30570-5_6","volume-title":"Database Theory - ICDT 2005","author":"K Munagala","year":"2004","unstructured":"Munagala, K., Babu, S., Motwani, R., Widom, J.: The pipelined set cover problem. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, pp. 83\u201398. Springer, Heidelberg (2004). \nhttps:\/\/doi.org\/10.1007\/978-3-540-30570-5_6"},{"key":"12_CR32","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/BFb0120909","volume":"13","author":"CN Potts","year":"1980","unstructured":"Potts, C.N.: An algorithm for the single machine sequencing problem with precedence constraints. Math. Program. Study 13, 78\u201387 (1980)","journal-title":"Math. Program. Study"},{"issue":"1\u20133","key":"12_CR33","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF01581271","volume":"58","author":"M Queyranne","year":"1993","unstructured":"Queyranne, M.: Structure of a simple scheduling polyhedron. Math. Program. 58(1\u20133), 263\u2013285 (1993). \nhttps:\/\/doi.org\/10.1007\/BF01581271","journal-title":"Math. Program."},{"key":"12_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/3-540-61310-2_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"AS Schulz","year":"1996","unstructured":"Schulz, A.S.: Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds. In: Cunningham, W.H., McCormick, S.T., Queyranne, M. (eds.) IPCO 1996. LNCS, vol. 1084, pp. 301\u2013315. Springer, Heidelberg (1996). \nhttps:\/\/doi.org\/10.1007\/3-540-61310-2_23"},{"key":"12_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/3-540-63248-4_11","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"AS Schulz","year":"1997","unstructured":"Schulz, A.S., Skutella, M.: Random-based scheduling new approximations and LP lower bounds. In: Rolim, J. (ed.) RANDOM 1997. LNCS, vol. 1269, pp. 119\u2013133. Springer, Heidelberg (1997). \nhttps:\/\/doi.org\/10.1007\/3-540-63248-4_11"},{"issue":"2","key":"12_CR36","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1287\/opre.23.2.283","volume":"23","author":"JB Sidney","year":"1975","unstructured":"Sidney, J.B.: Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs. Oper. Res. 23(2), 283\u2013298 (1975). \nhttps:\/\/doi.org\/10.1287\/opre.23.2.283","journal-title":"Oper. Res."},{"issue":"6","key":"12_CR37","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1016\/j.orl.2011.08.002","volume":"39","author":"M Skutella","year":"2011","unstructured":"Skutella, M., Williamson, D.P.: A note on the generalized min-sum set cover problem. Oper. Res. Lett. 39(6), 433\u2013436 (2011). \nhttps:\/\/doi.org\/10.1016\/j.orl.2011.08.002","journal-title":"Oper. Res. Lett."},{"issue":"1\u20132","key":"12_CR38","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"WE Smith","year":"1956","unstructured":"Smith, W.E.: Various optimizers for single-stage production. Nav. Res. Logist. Q. 3(1\u20132), 59\u201366 (1956). \nhttps:\/\/doi.org\/10.1002\/nav.3800030106","journal-title":"Nav. Res. Logist. Q."},{"issue":"1\u20133","key":"12_CR39","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/BF01586059","volume":"54","author":"JP Sousa","year":"1992","unstructured":"Sousa, J.P., Wolsey, L.A.: A time indexed formulation of non-preemptive single machine scheduling problems. Math. Program. 54(1\u20133), 353\u2013367 (1992). \nhttps:\/\/doi.org\/10.1007\/BF01586059","journal-title":"Math. Program."},{"issue":"1","key":"12_CR40","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0166-218X(02)00427-4","volume":"131","author":"GJ Woeginger","year":"2003","unstructured":"Woeginger, G.J.: On the approximability of average completion time scheduling under precedence constraints. Discrete Appl. Math. 131(1), 237\u2013252 (2003). \nhttps:\/\/doi.org\/10.1016\/S0166-218X(02)00427-4","journal-title":"Discrete Appl. Math."},{"key":"12_CR41","unstructured":"Wolsey, L.A.: Mixed integer programming formulations for production planning and scheduling problems. Invited Talk at the 12th International Symposium on Mathematical Programming (1985)"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-39479-0_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T08:05:47Z","timestamp":1583741147000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-39479-0_12"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030394783","9783030394790"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-39479-0_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"25 January 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Munich","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 September 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 September 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo2019.ak.in.tum.de\/index.php\/menue-waoa\/waoa-overview","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}