| Article ID: | iaor200697 |
| Country: | Germany |
| Volume: | 9 |
| Issue: | 3 |
| Start Page Number: | 313 |
| End Page Number: | 323 |
| Publication Date: | May 2005 |
| Journal: | Journal of Combinatorial Optimization |
| Authors: | Crama Y., Klundert Joris van de, Brauner N., Grigoriev A. |
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.