@inproceedings{afrati_approximation_1999,
	title = {Approximation schemes for minimizing average weighted completion time with release dates},
	doi = {10.1109/SFFCS.1999.814574},
	abstract = {We consider the problem of scheduling n jobs with release dates on
m machines so as to minimize their average weighted completion time. We
present the first known polynomial time approximation schemes for
several variants of this problem. Our results include PTASs for the case
of identical parallel machines and a constant number of unrelated
machines with and without preemption allowed. Our schemes are efficient:
for all variants the running time for α(1+ε) approximation
is of the form f(1/ε, m)poly(n)},
	booktitle = {Foundations of {Computer} {Science}, 1999. 40th {Annual} {Symposium} on},
	author = {Afrati, F. and Bampis, E. and Chekuri, C. and Karger, D. and Kenyon, C. and Khanna, S. and Milis, I. and Queyranne, M. and Skutella, M. and Stein, C. and Sviridenko, M.},
	year = {1999},
	keywords = {average weighted completion time, computational complexity, minimizing average weighted completion time, parallel machines, polynomial time approximation},
	pages = {32--43}
}

{"_id":"zQX8iPmJp4Qdb6mse","bibbaseid":"afrati-bampis-chekuri-karger-kenyon-khanna-milis-queyranne-etal-approximationschemesforminimizingaverageweightedcompletiontimewithreleasedates-1999","downloads":0,"creationDate":"2016-12-19T20:50:58.830Z","title":"Approximation schemes for minimizing average weighted completion time with release dates","author_short":["Afrati, F.","Bampis, E.","Chekuri, C.","Karger, D.","Kenyon, C.","Khanna, S.","Milis, I.","Queyranne, M.","Skutella, M.","Stein, C.","Sviridenko, M."],"year":1999,"bibtype":"inproceedings","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"Approximation schemes for minimizing average weighted completion time with release dates","doi":"10.1109/SFFCS.1999.814574","abstract":"We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation schemes for several variants of this problem. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our schemes are efficient: for all variants the running time for α(1+ε) approximation is of the form f(1/ε, m)poly(n)","booktitle":"Foundations of Computer Science, 1999. 40th Annual Symposium on","author":[{"propositions":[],"lastnames":["Afrati"],"firstnames":["F."],"suffixes":[]},{"propositions":[],"lastnames":["Bampis"],"firstnames":["E."],"suffixes":[]},{"propositions":[],"lastnames":["Chekuri"],"firstnames":["C."],"suffixes":[]},{"propositions":[],"lastnames":["Karger"],"firstnames":["D."],"suffixes":[]},{"propositions":[],"lastnames":["Kenyon"],"firstnames":["C."],"suffixes":[]},{"propositions":[],"lastnames":["Khanna"],"firstnames":["S."],"suffixes":[]},{"propositions":[],"lastnames":["Milis"],"firstnames":["I."],"suffixes":[]},{"propositions":[],"lastnames":["Queyranne"],"firstnames":["M."],"suffixes":[]},{"propositions":[],"lastnames":["Skutella"],"firstnames":["M."],"suffixes":[]},{"propositions":[],"lastnames":["Stein"],"firstnames":["C."],"suffixes":[]},{"propositions":[],"lastnames":["Sviridenko"],"firstnames":["M."],"suffixes":[]}],"year":"1999","keywords":"average weighted completion time, computational complexity, minimizing average weighted completion time, parallel machines, polynomial time approximation","pages":"32--43","bibtex":"@inproceedings{afrati_approximation_1999,\n\ttitle = {Approximation schemes for minimizing average weighted completion time with release dates},\n\tdoi = {10.1109/SFFCS.1999.814574},\n\tabstract = {We consider the problem of scheduling n jobs with release dates on\nm machines so as to minimize their average weighted completion time. We\npresent the first known polynomial time approximation schemes for\nseveral variants of this problem. Our results include PTASs for the case\nof identical parallel machines and a constant number of unrelated\nmachines with and without preemption allowed. Our schemes are efficient:\nfor all variants the running time for α(1+ε) approximation\nis of the form f(1/ε, m)poly(n)},\n\tbooktitle = {Foundations of {Computer} {Science}, 1999. 40th {Annual} {Symposium} on},\n\tauthor = {Afrati, F. and Bampis, E. and Chekuri, C. and Karger, D. and Kenyon, C. and Khanna, S. and Milis, I. and Queyranne, M. and Skutella, M. and Stein, C. and Sviridenko, M.},\n\tyear = {1999},\n\tkeywords = {average weighted completion time, computational complexity, minimizing average weighted completion time, parallel machines, polynomial time approximation},\n\tpages = {32--43}\n}\n\n","author_short":["Afrati, F.","Bampis, E.","Chekuri, C.","Karger, D.","Kenyon, C.","Khanna, S.","Milis, I.","Queyranne, M.","Skutella, M.","Stein, C.","Sviridenko, M."],"key":"afrati_approximation_1999","id":"afrati_approximation_1999","bibbaseid":"afrati-bampis-chekuri-karger-kenyon-khanna-milis-queyranne-etal-approximationschemesforminimizingaverageweightedcompletiontimewithreleasedates-1999","role":"author","urls":{},"keyword":["average weighted completion time","computational complexity","minimizing average weighted completion time","parallel machines","polynomial time approximation"],"downloads":0,"html":""},"search_terms":["approximation","schemes","minimizing","average","weighted","completion","time","release","dates","afrati","bampis","chekuri","karger","kenyon","khanna","milis","queyranne","skutella","stein","sviridenko"],"keywords":["average weighted completion time","computational complexity","minimizing average weighted completion time","parallel machines","polynomial time approximation"],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}