Concentrated hitting times of randomized search heuristics with variable drift
- Submitting institution
-
The University of Birmingham
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 42925915
- Type
- E - Conference contribution
- DOI
-
10.1007/978-3-319-13075-0_54
- Title of conference / published proceedings
- Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings
- First page
- 686
- Volume
- 8889
- Issue
- -
- ISSN
- 0302-9743
- Open access status
- Out of scope for open access requirements
- Month of publication
- November
- 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
-
1
- Research group(s)
-
-
- Citation count
- 28
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The last decade of research in time-complexity analysis of randomised search heuristics shows that most runtime bounds were obtained using a small number of analytical techniques, with drift analysis the most important. Almost every paper in the field uses a drift theorem. This paper introduced a new drift theorem which is both general and precise. Virtually all existing drift theorems are special cases of this theorem. It provides bounds on the expectation and concentration of runtime, and has been widely applied by the community. The paper won the best paper award at ISAAC'2014, a major algorithms conference.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
