@article{e7d185f2393e4dcba8962ed21df051e0,
title = "A framework for the complexity of high-multiplicity scheduling problems",
abstract = "The purpose of this note is to propose a complexity framework for the analysis of high multiplicity scheduling problems. Part of this framework relies on earlier work aiming at the definition of output-sensitive complexity measures for the analysis of algorithms which produce {"}large{"} outputs. However, different classes emerge according as we look at schedules as sets of starting times, or as related single-valued mappings.",
keywords = "Computational complexity, Design of algorithms, High multiplicity, Scheduling",
author = "N. Brauner and Y. Crama and A. Grigoriev and {Van De Klundert}, J.",
note = "Funding Information: The second author acknowledges the partial financial support of ONR (grant N00014-92-J-1375), NSF (grant DMS-98-06389), and research grants from the Natural Sciences and Engineering Research Council of Canada (NSERC). The fourth acknowledges support from the EU project APPOL (IST-1999-14084). Funding Information: This research was carried out while the first author was visiting the University of Li{\`e}ge in the framework of a postdoctoral project supported by the European Network DONET (contract number ERB TMRX-CT98-0202).",
year = "2005",
month = may,
doi = "10.1007/s10878-005-1414-7",
language = "English",
volume = "9",
pages = "313--323",
journal = "Journal of Combinatorial Optimization",
issn = "1382-6905",
publisher = "Springer Netherlands",
number = "3",
}