{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:28:36Z","timestamp":1759847316002},"reference-count":16,"publisher":"Elsevier BV","issue":"5","license":[{"start":{"date-parts":[[1999,12,1]],"date-time":"1999-12-01T00:00:00Z","timestamp":944006400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research Letters"],"published-print":{"date-parts":[[1999,12]]},"DOI":"10.1016\/s0167-6377(99)00056-5","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T13:07:44Z","timestamp":1027602464000},"page":"199-204","source":"Crossref","is-referenced-by-count":60,"title":["A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine"],"prefix":"10.1016","volume":"25","author":[{"given":"Fabi\u00e1n A.","family":"Chudak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dorit S.","family":"Hochbaum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0167-6377(99)00056-5_BIB1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0166-218X(90)90089-U","article-title":"The permutahedron of series\u2013parallel posets","volume":"28","author":"Von Arnim","year":"1990","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0167-6377(99)00056-5_BIB2","doi-asserted-by":"crossref","unstructured":"C. Chekuri, R. Motwani, Precedence constrained scheduling to minimize weighted completion time on a single machine, Discrete Appl. Math., to appear.","DOI":"10.1016\/S0166-218X(98)00143-7"},{"key":"10.1016\/S0167-6377(99)00056-5_BIB3","doi-asserted-by":"crossref","unstructured":"D. Coppersmith, S. Winograd, Matrix computations via arithmetic progressions, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 1\u20136.","DOI":"10.1145\/28395.28396"},{"key":"10.1016\/S0167-6377(99)00056-5_BIB4","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","article-title":"A new approach for the maximum flow problem","volume":"35","author":"Goldberg","year":"1988","journal-title":"J. ACM"},{"key":"10.1016\/S0167-6377(99)00056-5_BIB5","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","article-title":"Optimization and approximation in deterministic sequencing and scheduling: a survey","volume":"5","author":"Graham","year":"1979","journal-title":"Ann. Discrete Math."},{"key":"10.1016\/S0167-6377(99)00056-5_BIB6","doi-asserted-by":"crossref","unstructured":"L.A. Hall, A.S. Schulz, D.B. Shmoys, J. Wein, Scheduling to minimize average completion time: off-line and on-line approximation algorithms, Math. Oper. Res., to appear.","DOI":"10.1287\/moor.22.3.513"},{"key":"10.1016\/S0167-6377(99)00056-5_BIB7","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/BF01585160","article-title":"Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality","volume":"62","author":"Hochbaum","year":"1993","journal-title":"Math. Programming"},{"key":"10.1016\/S0167-6377(99)00056-5_BIB8","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0167-5060(08)70323-6","article-title":"Sequencing jobs to minimize total weighted completion time subject to precedence constraints","volume":"2","author":"Lawler","year":"1978","journal-title":"Ann. Discrete Math."},{"key":"10.1016\/S0167-6377(99)00056-5_BIB9","unstructured":"F. Margot, M. Queyranne, Y. Wang, Decompositions, network flows and a precedence constrained single machine problem, Working paper, 1997."},{"key":"10.1016\/S0167-6377(99)00056-5_BIB10","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/BFb0120909","article-title":"An algorithm for the single machine sequencing problem with precedence constraints","volume":"13","author":"Potts","year":"1980","journal-title":"Math. Programming Stud."},{"key":"10.1016\/S0167-6377(99)00056-5_BIB11","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF01581271","article-title":"Structure of a simple scheduling polyhedron","volume":"58","author":"Queyranne","year":"1993","journal-title":"Math. Programming"},{"key":"10.1016\/S0167-6377(99)00056-5_BIB12","unstructured":"M. Queyranne, A.S. Schulz, Polyhedral approaches to machine scheduling, Report No 408\/1994, Fachbereich Mathematik, Technische Universitt Berlin, 1994."},{"key":"10.1016\/S0167-6377(99)00056-5_BIB13","doi-asserted-by":"crossref","unstructured":"A.S. Schulz, private communication, June 1997.","DOI":"10.1080\/105846097199579"},{"key":"10.1016\/S0167-6377(99)00056-5_BIB14","doi-asserted-by":"crossref","unstructured":"P.M. Vaidya, A new algorithm for minimizing convex functions over convex sets, Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 338\u2013343.","DOI":"10.1109\/SFCS.1989.63500"},{"key":"10.1016\/S0167-6377(99)00056-5_BIB15","doi-asserted-by":"crossref","unstructured":"P.M. Vaidya, Speeding-up linear programming using fast matrix multiplication, Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 332\u2013337.","DOI":"10.1109\/SFCS.1989.63499"},{"key":"10.1016\/S0167-6377(99)00056-5_BIB16","unstructured":"L.A. Wolsey, Formulating single machine scheduling problems with precedence constraints, in: J.J. Gabsewicz, J.F. Richard, L.A. Wolsey (Eds.), Economic Decision Making: Games, Econometrics and Optimisation, Contributions in Honour of Jacques Dreze, North-Holland, Amsterdam, 1990, pp. 473\u2013484."}],"container-title":["Operations Research Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167637799000565?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167637799000565?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T14:55:32Z","timestamp":1578495332000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0167637799000565"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,12]]},"references-count":16,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1999,12]]}},"alternative-id":["S0167637799000565"],"URL":"https:\/\/doi.org\/10.1016\/s0167-6377(99)00056-5","relation":{},"ISSN":["0167-6377"],"issn-type":[{"value":"0167-6377","type":"print"}],"subject":[],"published":{"date-parts":[[1999,12]]}}}