Single machine scheduling with scenarios. Mastrolilli, M., Mutsanas, N., & Svensson, O. Theoretical Computer Science. ![Single machine scheduling with scenarios [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex In the field of robust optimization, the goal is to provide solutions to combinatorial problems that hedge against variations of the numerical parameters. This constitutes an effort to design algorithms that are applicable in the presence of uncertainty in the definition of the instance. We study the single machine scheduling problem with the objective to minimize the weighted sum of completion times. We model uncertainty by replacing the vector of numerical values in the description of the instance by a set of possible vectors, called scenarios. The goal is to find a schedule of minimum value in the worst-case scenario. We first show that the general problem cannot be approximated within O ( log 1 − ε n ) for any ε > 0 , unless NP has quasi-polynomial algorithms. We then study more tractable special cases and obtain an LP based 2 -approximation algorithm for the unweighted case. We show that our analysis is tight by providing a matching lower bound on the integrality gap of the LP. Moreover, we prove that the unweighted version is NP-hard to approximate within a factor less than 6 / 5 . We conclude by presenting a polynomial time algorithm based on dynamic programming for the case when the number of scenarios and the values of the instance are bounded by some constant.
@article{mastrolilli_single_????,
title = {Single machine scheduling with scenarios},
issn = {0304-3975},
url = {http://www.sciencedirect.com/science/article/pii/S0304397512010857},
doi = {10.1016/j.tcs.2012.12.006},
abstract = {In the field of robust optimization, the goal is to provide solutions to combinatorial problems that hedge against variations of the numerical parameters. This constitutes an effort to design algorithms that are applicable in the presence of uncertainty in the definition of the instance. We study the single machine scheduling problem with the objective to minimize the weighted sum of completion times. We model uncertainty by replacing the vector of numerical values in the description of the instance by a set of possible vectors, called scenarios. The goal is to find a schedule of minimum value in the worst-case scenario. We first show that the general problem cannot be approximated within O ( log 1 − ε n ) for any ε \> 0 , unless NP has quasi-polynomial algorithms. We then study more tractable special cases and obtain an LP based 2 -approximation algorithm for the unweighted case. We show that our analysis is tight by providing a matching lower bound on the integrality gap of the LP. Moreover, we prove that the unweighted version is NP-hard to approximate within a factor less than 6 / 5 . We conclude by presenting a polynomial time algorithm based on dynamic programming for the case when the number of scenarios and the values of the instance are bounded by some constant.},
urldate = {2013-01-15TZ},
journal = {Theoretical Computer Science},
author = {Mastrolilli, Monaldo and Mutsanas, Nikolaus and Svensson, Ola},
keywords = {Inapproximability, Robust optimization, approximation algorithms, scheduling}
}
Downloads: 0
{"_id":"hHxT5mpLepvHJ3Caf","bibbaseid":"mastrolilli-mutsanas-svensson-singlemachineschedulingwithscenarios","downloads":0,"creationDate":"2016-12-19T20:50:58.461Z","title":"Single machine scheduling with scenarios","author_short":["Mastrolilli, M.","Mutsanas, N.","Svensson, O."],"year":null,"bibtype":"article","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"article","type":"article","title":"Single machine scheduling with scenarios","issn":"0304-3975","url":"http://www.sciencedirect.com/science/article/pii/S0304397512010857","doi":"10.1016/j.tcs.2012.12.006","abstract":"In the field of robust optimization, the goal is to provide solutions to combinatorial problems that hedge against variations of the numerical parameters. This constitutes an effort to design algorithms that are applicable in the presence of uncertainty in the definition of the instance. We study the single machine scheduling problem with the objective to minimize the weighted sum of completion times. We model uncertainty by replacing the vector of numerical values in the description of the instance by a set of possible vectors, called scenarios. The goal is to find a schedule of minimum value in the worst-case scenario. We first show that the general problem cannot be approximated within O ( log 1 − ε n ) for any ε > 0 , unless NP has quasi-polynomial algorithms. We then study more tractable special cases and obtain an LP based 2 -approximation algorithm for the unweighted case. We show that our analysis is tight by providing a matching lower bound on the integrality gap of the LP. Moreover, we prove that the unweighted version is NP-hard to approximate within a factor less than 6 / 5 . We conclude by presenting a polynomial time algorithm based on dynamic programming for the case when the number of scenarios and the values of the instance are bounded by some constant.","urldate":"2013-01-15TZ","journal":"Theoretical Computer Science","author":[{"propositions":[],"lastnames":["Mastrolilli"],"firstnames":["Monaldo"],"suffixes":[]},{"propositions":[],"lastnames":["Mutsanas"],"firstnames":["Nikolaus"],"suffixes":[]},{"propositions":[],"lastnames":["Svensson"],"firstnames":["Ola"],"suffixes":[]}],"keywords":"Inapproximability, Robust optimization, approximation algorithms, scheduling","bibtex":"@article{mastrolilli_single_????,\n\ttitle = {Single machine scheduling with scenarios},\n\tissn = {0304-3975},\n\turl = {http://www.sciencedirect.com/science/article/pii/S0304397512010857},\n\tdoi = {10.1016/j.tcs.2012.12.006},\n\tabstract = {In the field of robust optimization, the goal is to provide solutions to combinatorial problems that hedge against variations of the numerical parameters. This constitutes an effort to design algorithms that are applicable in the presence of uncertainty in the definition of the instance. We study the single machine scheduling problem with the objective to minimize the weighted sum of completion times. We model uncertainty by replacing the vector of numerical values in the description of the instance by a set of possible vectors, called scenarios. The goal is to find a schedule of minimum value in the worst-case scenario. We first show that the general problem cannot be approximated within O ( log 1 − ε n ) for any ε \\> 0 , unless NP has quasi-polynomial algorithms. We then study more tractable special cases and obtain an LP based 2 -approximation algorithm for the unweighted case. We show that our analysis is tight by providing a matching lower bound on the integrality gap of the LP. Moreover, we prove that the unweighted version is NP-hard to approximate within a factor less than 6 / 5 . We conclude by presenting a polynomial time algorithm based on dynamic programming for the case when the number of scenarios and the values of the instance are bounded by some constant.},\n\turldate = {2013-01-15TZ},\n\tjournal = {Theoretical Computer Science},\n\tauthor = {Mastrolilli, Monaldo and Mutsanas, Nikolaus and Svensson, Ola},\n\tkeywords = {Inapproximability, Robust optimization, approximation algorithms, scheduling}\n}\n\n","author_short":["Mastrolilli, M.","Mutsanas, N.","Svensson, O."],"key":"mastrolilli_single_????","id":"mastrolilli_single_????","bibbaseid":"mastrolilli-mutsanas-svensson-singlemachineschedulingwithscenarios","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/S0304397512010857"},"keyword":["Inapproximability","Robust optimization","approximation algorithms","scheduling"],"downloads":0,"html":""},"search_terms":["single","machine","scheduling","scenarios","mastrolilli","mutsanas","svensson"],"keywords":["inapproximability","robust optimization","approximation algorithms","scheduling"],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}