Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times
- Submitting institution
-
The University of Leeds
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- UOA11-1290
- Type
- D - Journal article
- DOI
-
10.1007/s10107-014-0814-9
- Title of journal
- Mathematical Programming
- Article number
- -
- First page
- 495
- Volume
- 153
- Issue
- 2
- ISSN
- 0025-5610
- Open access status
- Out of scope for open access requirements
- Month of publication
- September
- Year of publication
- 2014
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
A - AC (Algorithms and Complexity)
- Citation count
- 11
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- An outcome of the EPSRC funded interdisciplinary project EP/J019755/1 on linking Submodular Optimisation and Scheduling with Controllable Processing times, proposing a fundamental methodology for the continuous resource-allocation problem with submodular constraints. It advances the existing toolkit of Submodular Optimisation techniques based on decomposition: the famous algorithms by Fujishige’1980 and Groenvelt’1991. The significance of the new approach is demonstrated by applying it to three scheduling problems, which have been studied since the 1980s yielding faster algorithms than the best previously known. The follow-up paper (IJOC’2016: 10.1287/ijoc.2015.0660) provides another example of its successful application.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
