pith. machine review for the scientific record. sign in

arxiv: 2605.11201 · v1 · submitted 2026-05-11 · 💻 cs.NE

Recognition: no theorem link

On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III

Andre Opris

Authors on Pith no claims yet

Pith reviewed 2026-05-13 00:45 UTC · model grok-4.3

classification 💻 cs.NE
keywords NSGA-IIIcrossoverruntime analysismany-objective optimizationOneJumpZeroJumpMOEA
0
0 comments X

The pith

NSGA-III with crossover optimizes the m-OJZJ function asymptotically faster than the version without crossover for any number of objectives.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper conducts a theoretical runtime analysis of the NSGA-III algorithm on the m-objective OneJumpZeroJump benchmark. It proves that including the crossover operator leads to asymptotically lower expected runtimes than the no-crossover variant, and this holds for every number of objectives in large parameter regimes. The work fills a gap by supplying the first rigorous runtime comparison that explains why crossover helps on many-objective problems. It also supplies a matching lower bound for the four-objective case when crossover is disabled.

Core claim

Our results demonstrate that NSGA-III with crossover optimizes m-OJZJ asymptotically faster than NSGA-III without crossover for any number m of objectives for huge parameter regimes.

What carries the argument

Runtime comparison of NSGA-III equipped with versus without the crossover operator on the m-OneJumpZeroJump benchmark function.

If this is right

  • Crossover enables the algorithm to combine building blocks from distant regions of the search space.
  • The observed speedup is independent of the number of objectives.
  • The benefit appears only when population size and other parameters allow distant solutions to be recombined effectively.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same structural advantage may appear on other many-objective benchmarks that contain large fitness jumps.
  • Practical NSGA-III implementations could default to crossover being enabled on problems with rugged objective landscapes.
  • Extending the analysis to other many-objective evolutionary algorithms would test whether crossover is broadly helpful.

Load-bearing premise

The runtime bounds depend on the specific structure of the m-OJZJ benchmark and on population sizes that let crossover recombine solutions lying far apart.

What would settle it

Explicit computation of the expected number of generations required by NSGA-III with and without crossover on the four-objective instance of m-OJZJ for concrete population sizes.

read the original abstract

In recent years, a theoretical understanding has rapidly advanced regarding how popular multi-objective evolutionary algorithms (MOEAs) can optimize many-objective problems. However, the benefits of using crossover in many-objective optimization are theoretically not understood, except for specifically designed benchmark functions tuned to particular crossover operators, and still lag significantly behind its practical use. In this paper, we build upon this line of research and present a theoretical runtime analysis of the widely used NSGA-III algorithm on the classical $m$-objective $m$-OneJumpZeroJump function ($m$-OJZJ for short). Our results demonstrate that NSGA-III with crossover optimizes $m$-OJZJ asymptotically faster than NSGA-III without crossover for any number $m$ of objectives for huge parameter regimes. We complement our analysis by providing a lower runtime bound on $4$-OJZJ when crossover is turned off.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper presents a runtime analysis of NSGA-III on the m-objective OneJumpZeroJump (m-OJZJ) benchmark. It derives upper runtime bounds showing that NSGA-III with crossover optimizes m-OJZJ asymptotically faster than the variant without crossover, for any number m of objectives and in large parameter regimes; a matching lower bound is supplied for the no-crossover case on the specific 4-OJZJ instance.

Significance. If the stated bounds are correct, the work supplies the first asymptotic runtime comparison establishing a benefit from crossover in many-objective optimization on a standard benchmark for arbitrary m. The direct analysis of population dynamics and selection on the explicit m-OJZJ definition, together with the provision of a lower bound for the 4-objective no-crossover case, are positive features that avoid circularity or fitted parameters.

major comments (2)
  1. [Abstract] Abstract: the claim that NSGA-III with crossover 'optimizes m-OJZJ asymptotically faster than NSGA-III without crossover for any number m of objectives' rests, for m ≠ 4, solely on an upper-bound comparison. A lower runtime bound for the no-crossover variant is provided only for 4-OJZJ; without a matching lower bound for general m, the comparison does not establish that the true runtime without crossover is asymptotically larger.
  2. [Runtime analysis without crossover] Analysis of the no-crossover variant: the upper bound derived for general m without crossover may not be tight. The manuscript should either derive a general lower bound or qualify the 'for any m' statement to reflect that the asymptotic separation is proven only when a matching lower bound exists (currently m=4).

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments correctly identify a subtlety in the strength of our claims regarding the benefit of crossover for general m. We will revise the manuscript to qualify the statements in the abstract, introduction, and conclusion to accurately reflect the proven bounds.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that NSGA-III with crossover 'optimizes m-OJZJ asymptotically faster than NSGA-III without crossover for any number m of objectives' rests, for m ≠ 4, solely on an upper-bound comparison. A lower runtime bound for the no-crossover variant is provided only for 4-OJZJ; without a matching lower bound for general m, the comparison does not establish that the true runtime without crossover is asymptotically larger.

    Authors: We agree that the abstract claim for general m relies on comparing our O( ) upper bound for the crossover variant against our O( ) upper bound for the no-crossover variant. This does not constitute a rigorous proof that the actual runtime without crossover is asymptotically worse, because the no-crossover upper bound may not be tight. We will revise the abstract (and parallel statements in the introduction and conclusion) to qualify the result: we prove that NSGA-III with crossover has an asymptotically better upper bound than the proven upper bound without crossover for any m in the large-parameter regimes, while a matching lower bound establishing the full separation is supplied only for the 4-objective case. revision: yes

  2. Referee: [Runtime analysis without crossover] Analysis of the no-crossover variant: the upper bound derived for general m without crossover may not be tight. The manuscript should either derive a general lower bound or qualify the 'for any m' statement to reflect that the asymptotic separation is proven only when a matching lower bound exists (currently m=4).

    Authors: We acknowledge that our upper bound for the no-crossover variant on general m may not be tight and that a general lower bound would be needed for a complete asymptotic comparison. Deriving such a lower bound for arbitrary m would require a substantially more technical analysis of the population dynamics and is left as future work. We will therefore qualify the 'for any m' phrasing throughout the paper, explicitly noting that the full asymptotic separation (upper bound with crossover strictly smaller than lower bound without crossover) is currently established only for m=4, while for general m the results demonstrate an improvement in the proven upper bounds. revision: yes

Circularity Check

0 steps flagged

No circularity: bounds derived by direct analysis of algorithm progress on explicit m-OJZJ definition

full rationale

The paper conducts a standard theoretical runtime analysis, proving upper bounds on expected runtime for NSGA-III with and without crossover on the explicitly defined m-OJZJ benchmark, plus a matching lower bound for the no-crossover case at m=4. These are obtained by tracking the algorithm's state transitions and progress probabilities directly from the function's structure and the NSGA-III selection/crossover mechanisms. No parameters are fitted to data and then renamed as predictions, no self-citations form the load-bearing justification for the central comparison, and no ansatz or uniqueness result is smuggled in. The asymptotic comparison for general m uses the proven upper bounds; while this does not yield a tight lower bound on the no-crossover runtime for m>4, that is a limitation of proof tightness rather than a circular reduction of the derivation to its own inputs. The analysis is self-contained against the benchmark definition.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The analysis rests on standard assumptions about the mutation and crossover operators in NSGA-III and on the explicit definition of the m-OJZJ function; no new entities are postulated and no parameters are fitted to data.

axioms (2)
  • domain assumption NSGA-III selection and diversity mechanisms behave as described in the original NSGA-III reference for the given population size regimes.
    Invoked to bound the time until the population covers the necessary objective-space regions.
  • domain assumption The m-OJZJ function has the standard jump structure with independent objectives and a single global optimum.
    Used to calculate the probability of generating the optimum via crossover or mutation.

pith-pipeline@v0.9.0 · 5445 in / 1361 out tokens · 53731 ms · 2026-05-13T00:45:28.847250+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages

  1. [1]

    Black-box complexity of par- allel search with distributed populations

    [Badkobehet al., 2015 ] Golnaz Badkobeh, Per Kristian Lehre, and Dirk Sudholt. Black-box complexity of par- allel search with distributed populations. InProceedings of the Foundations of Genetic Algorithms, FOGA 2015, pages 3–15. ACM Press,

    work page 2015

  2. [2]

    [Bi-wu Zhuet al., 2025 ] Bi-wu Zhu, Zi wen Feng, Hao Jiang, Xiao Liu, Jian zhao Wu, Wen hui Liu, Fan Ye, Yu xin Lin, Peng cheng Guo, Cong chang Xu, and Luo xing Li. A strategy combining interpretable machine learn- ing, nsga-iii optimization model and strengthening and toughing mechanism to predict microstructure for rolled az31 magnesium alloy sheets.Jou...

    work page 2025

  3. [3]

    Investigating the normalization proce- dure of NSGA-III

    [Blanket al., 2019 ] Julian Blank, Kalyanmoy Deb, and Pro- teek Chandan Roy. Investigating the normalization proce- dure of NSGA-III. InEvolutionary Multi-Criterion Opti- mization, pages 229–240. Springer,

    work page 2019

  4. [4]

    A nsga-ii and nsga-iii comparison for solving an open shop scheduling problem with resource constraints

    [Campos Ciroet al., 2016 ] Guillermo Campos Ciro, Fr´ed´eric Dugardin, Farouk Yalaoui, and Russell Kelly. A nsga-ii and nsga-iii comparison for solving an open shop scheduling problem with resource constraints. IFAC-PapersOnLine, 49(12):1272–1277,

    work page 2016

  5. [5]

    Krejca, Per Kristian Lehre, Pietro S

    [Danget al., 2017 ] Duc-Cuong Dang, Tobias Friedrich, Timo K ¨otzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton. Escaping local optima using crossover with emergent di- versity.IEEE Transactions on Evolutionary Computation, 22:484–497,

    work page 2017

  6. [6]

    A proof that using crossover can guarantee exponential speed-ups in evolutionary multi- objective optimisation

    [Danget al., 2023 ] Duc-Cuong Dang, Andre Opris, Bahare Salehi, and Dirk Sudholt. A proof that using crossover can guarantee exponential speed-ups in evolutionary multi- objective optimisation. InProceedings of the AAAI Conference on Artificial Intelligence, AAAI 2023, pages 12390–12398. AAAI Press,

    work page 2023

  7. [7]

    [Deb and Jain, 2014] Kalyanmoy Deb and Himanshu Jain. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting ap- proach, part i: Solving problems with box con- straints.IEEE Transactions on Evolutionary Computation, 18(4):577–601,

    work page 2014

  8. [8]

    Meyarivan

    [Debet al., 2002 ] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan. A fast and elitist multiob- jective genetic algorithm: NSGA-II.IEEE Transactions on Evolutionary Computation, 6(2):182–197,

    work page 2002

  9. [9]

    A first runtime analysis of the NSGA-II on a multimodal problem

    [Doerr and Qu, 2022] Benjamin Doerr and Zhongdi Qu. A first runtime analysis of the NSGA-II on a multimodal problem. InProceedings of the International Conference on Parallel Problem Solving from Nature, PPSN XVII, pages 399–412. Springer,

    work page 2022

  10. [10]

    From understanding the population dynamics of the NSGA-II to the first proven lower bounds

    [Doerr and Qu, 2023a] Benjamin Doerr and Zhongdi Qu. From understanding the population dynamics of the NSGA-II to the first proven lower bounds. InProceedings of the AAAI Conference on Artificial Intelligence, AAAI 2023, pages 12408–12416. AAAI Press,

    work page 2023

  11. [11]

    Runtime analysis for the NSGA-II: provable speed-ups from crossover

    [Doerr and Qu, 2023b] Benjamin Doerr and Zhongdi Qu. Runtime analysis for the NSGA-II: provable speed-ups from crossover. InProceedings of the AAAI Conference on Artificial Intelligence, AAAI 2023, pages 12399–12407. AAAI Press,

    work page 2023

  12. [12]

    Crossover can provably be useful in evolution- ary computation.Theoretical Computer Science, 425:17– 33,

    [Doerret al., 2012 ] Benjamin Doerr, Edda Happ, and Chris- tian Klein. Crossover can provably be useful in evolution- ary computation.Theoretical Computer Science, 425:17– 33,

    work page 2012

  13. [13]

    More effective crossover operators for the all-pairs short- est path problem.Theoretical Computer Science, 471:12– 26,

    [Doerret al., 2013 ] Benjamin Doerr, Daniel Johannsen, Timo K ¨otzing, Frank Neumann, and Madeleine Theile. More effective crossover operators for the all-pairs short- est path problem.Theoretical Computer Science, 471:12– 26,

    work page 2013

  14. [14]

    The (1 + (λ,λ)) global SEMO algorithm

    [Doerret al., 2022 ] Benjamin Doerr, Omar El Hadri, and Adrien Pinard. The (1 + (λ,λ)) global SEMO algorithm. InProceedings of the Genetic and Evolutionary Compu- tation Conference (GECCO’22), pages 520–528. ACM Press,

    work page 2022

  15. [15]

    [Doerret al., 2025 ] Benjamin Doerr, Dimitri Korkotashvili, and Martin S. Krejca. Difficulties of the nsga-ii with the many-objective leadingones problem.IEEE Transactions on Evolutionary Computation, pages 1–1,

    work page 2025

  16. [16]

    Krejca, and Milan Stankovic

    [Doerret al., 2026 ] Benjamin Doerr, Martin S. Krejca, and Milan Stankovic. Improved runtime guarantees for the SPEA2 multi-objective optimizer. InProceedings of the AAAI Conference on Artificial Intelligence, AAAI 2026, pages 36855–36863. AAAI Press,

    work page 2026

  17. [17]

    Analyzing randomized search heuristics via stochastic domination.Theoretical Computer Science, 773:115–137,

    [Doerr, 2019] Benjamin Doerr. Analyzing randomized search heuristics via stochastic domination.Theoretical Computer Science, 773:115–137,

    work page 2019

  18. [18]

    [Gaeuman and Sutton, 2025] Liam Gaeuman and An- drew M. Sutton. A fixed-parameter tractable ga for data clustering. InProceedings of the 18th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA ’25, page 49–60. ACM,

    work page 2025

  19. [19]

    Distance-based anal- ysis of crossover operators for many-objective knapsack problems

    [Ishibuchiet al., 2014 ] Hisao Ishibuchi, Yuki Tanigaki, Hi- royuki Masuda, and Yusuke Nojima. Distance-based anal- ysis of crossover operators for many-objective knapsack problems. InProseecings of the Parallel Problem Solving from Nature, PPSN XIII, pages 600–610,

    work page 2014

  20. [20]

    On the analysis of evolutionary algorithms—a proof that crossover really can help.Algorithmica, 34(1):47–66,

    [Jansen and Wegener, 2002] Thomas Jansen and Ingo We- gener. On the analysis of evolutionary algorithms—a proof that crossover really can help.Algorithmica, 34(1):47–66,

    work page 2002

  21. [21]

    Real royal road functions—where crossover prov- ably is essential.Discrete Applied Mathematics, 149:111– 125,

    [Jansen and Wegener, 2005] Thomas Jansen and Ingo We- gener. Real royal road functions—where crossover prov- ably is essential.Discrete Applied Mathematics, 149:111– 125,

    work page 2005

  22. [22]

    How crossover helps in pseudo-boolean optimization

    [K¨otzinget al., 2011 ] Timo K ¨otzing, Dirk Sudholt, and Madeleine Theile. How crossover helps in pseudo-boolean optimization. InProceedings of the Genetic and Evo- lutionary Computation Conference (GECCO’11), pages 989–996. ACM Press,

    work page 2011

  23. [23]

    Running time analysis of multiob- jective evolutionary algorithms on pseudo-boolean func- tions.IEEE Transactions on Evolutionary Computation, 8(2):170–182,

    [Laumannset al., 2004 ] Marco Laumanns, Lothar Thiele, and Eckart Zitzler. Running time analysis of multiob- jective evolutionary algorithms on pseudo-boolean func- tions.IEEE Transactions on Evolutionary Computation, 8(2):170–182,

    work page 2004

  24. [24]

    van den Maagdenberg, Michael T.M

    [Luukkonenet al., 2023 ] Sohvi Luukkonen, Helle W. van den Maagdenberg, Michael T.M. Emmerich, and Ger- ard J.P. van Westen. Artificial intelligence in multi- objective drug design.Current Opinion in Structural Biol- ogy, 79:102537,

    work page 2023

  25. [25]

    Parent selection mechanisms in elitist crossover-based al- gorithms,

    [Opris and Antipov, 2026] Andre Opris and Denis Antipov. Parent selection mechanisms in elitist crossover-based al- gorithms,

    work page 2026

  26. [26]

    Runtime analyses of NSGA- III on many-objective problems

    [Opriset al., 2024a ] Andre Opris, Duc-Cuong Dang, Frank Neumann, and Dirk Sudholt. Runtime analyses of NSGA- III on many-objective problems. InProceedings of the Ge- netic and Evolutionary Computation Conference, GECCO 2024, page 1596–1604. ACM Press,

    work page 2024

  27. [27]

    A royal road function for permutation spaces: an example where order crossover is provably es- sential

    [Opriset al., 2025 ] Andre Opris, Sebastian Sonntag, and Dirk Sudholt. A royal road function for permutation spaces: an example where order crossover is provably es- sential. InProceedings of the Genetic and Evolutionary Computation Conference, GECCO ’25, page 1631–1640. ACM,

    work page 2025

  28. [28]

    A first runtime analysis of NSGA-III on a many-objective multimodal problem: Provable exponential speedup via stochastic population update

    [Opris, 2025a] Andre Opris. A first runtime analysis of NSGA-III on a many-objective multimodal problem: Provable exponential speedup via stochastic population update. InProceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, pages 8903–8911. ijcai.org,

    work page 2025

  29. [29]

    [Opris, 2025c] Andre Opris

    ACM. [Opris, 2025c] Andre Opris. A many objective problem where crossover is provably indispensable. InProceedings of the AAAI Conference on Artificial Intelligence, AAAI 2025, pages 27108–27116. AAAI Press,

    work page 2025

  30. [30]

    Towards a rigorous understand- ing of the population dynamics of the NSGA-III: Tight runtime bounds

    [Opris, 2026b] Andre Opris. Towards a rigorous understand- ing of the population dynamics of the NSGA-III: Tight runtime bounds. InProceedings of the AAAI Confer- ence on Artificial Intelligence, AAAI 2026, pages 37125– 37133. AAAI Press,

    work page 2026

  31. [31]

    Pavai and T

    [Pavai and Geetha, 2016] G. Pavai and T. V . Geetha. A sur- vey on crossover operators.ACM Comput. Surv., 49(4), December

    work page 2016

  32. [32]

    An analysis on recombination in multi-objective evolu- tionary optimization.Artificial Intelligence, 204:99–119,

    [Qianet al., 2013 ] Chao Qian, Yang Yu, and Zhi-Hua Zhou. An analysis on recombination in multi-objective evolu- tionary optimization.Artificial Intelligence, 204:99–119,

    work page 2013

  33. [33]

    Subset selection by pareto optimization with recombina- tion

    [Qianet al., 2020 ] Chao Qian, Chao Bian, and Chao Feng. Subset selection by pareto optimization with recombina- tion. InProceedings of the AAAI Conference on Artificial Intelligence, AAAI 2020, pages 2408–2415. AAAI Press,

    work page 2020

  34. [34]

    [Rashmiet al., 2025 ] Sharma Rashmi, Jesubalan Naveen G., and Anurag S. Rathore. Integrating ensemble nsga-ii for multi-objective process optimization: Refolding of proin- sulin as a case study.Biotechnology and Bioengineering,

    work page 2025

  35. [35]

    A first running time analysis of the strength pareto evolutionary algorithm 2 (spea2)

    [Renet al., 2024 ] Shengjie Ren, Chao Bian, Miqing Li, and Chao Qian. A first running time analysis of the strength pareto evolutionary algorithm 2 (spea2). InProceedings of the International Conference on Parallel Problem Solving from Nature (PPSN ’24), LNCS, page to appear. Springer,

    work page 2024

  36. [36]

    Ensembled crossover based evolutionary algorithm for single and multi-objective optimization

    [Sharmaet al., 2021 ] Shreya Sharma, Julian Blank, Kalyan- moy Deb, and Bijaya Ketan Panigrahi. Ensembled crossover based evolutionary algorithm for single and multi-objective optimization. In2021 IEEE Congress on Evolutionary Computation (CEC), pages 1439–1446,

    work page 2021

  37. [37]

    Evolving populations of solved subgraphs with crossover and constraint repair

    [Sutton and Lee, 2024] Andrew Sutton and Jiwon Lee. Evolving populations of solved subgraphs with crossover and constraint repair. InProceedings of the Interna- tional Conference on Parallel Problem Solving from Na- ture (PPSN ’24), page 133–148. Springer,

    work page 2024

  38. [38]

    A hybrid multi-objective optimization approach with NSGA-II for feature selection.Decision Analytics Jour- nal, 14:100550,

    [Vijai and P., 2025] Praveen Vijai and Bagavathi Sivakumar P. A hybrid multi-objective optimization approach with NSGA-II for feature selection.Decision Analytics Jour- nal, 14:100550,

    work page 2025

  39. [39]

    A mathematical runtime analysis of the non-dominated sorting genetic algorithm III (NSGA-III)

    [Wietheger and Doerr, 2023] Simon Wietheger and Ben- jamin Doerr. A mathematical runtime analysis of the non-dominated sorting genetic algorithm III (NSGA-III). InProceedings of the International Joint Conference on Artificial Intelligence, IJCAI 2023, pages 5657–5665. ij- cai.org,

    work page 2023

  40. [40]

    Near-tight runtime guarantees for many- objective evolutionary algorithms

    [Wietheger and Doerr, 2024] Simon Wietheger and Ben- jamin Doerr. Near-tight runtime guarantees for many- objective evolutionary algorithms. InProceedings of the International Conference on Parallel Problem Solving from Nature, PPSN XVIII, pages 153–168,

    work page 2024

  41. [41]

    Runtime analysis of the SMS-EMOA for many-objective optimization

    [Zheng and Doerr, 2024] Weijie Zheng and Benjamin Doerr. Runtime analysis of the SMS-EMOA for many-objective optimization. InProceedings of the AAAI Conference on Artificial Intelligence, AAAI 2024, pages 20874–20882. AAAI Press,

    work page 2024

  42. [42]

    A first mathematical runtime analysis of the non- dominated sorting genetic algorithm II (NSGA-II)

    [Zhenget al., 2022 ] Weijie Zheng, Yufei Liu, and Benjamin Doerr. A first mathematical runtime analysis of the non- dominated sorting genetic algorithm II (NSGA-II). InPro- ceedings of the AAAI Conference on Artificial Intelligence, AAAI 2022, pages 10408–10416. AAAI Press,

    work page 2022

  43. [43]

    By applying a union bound on allµ individuals, the probability is at moste −Ω(µn) that there exists no individualxwithk≤ |x| 1 ≤n−kfor allj∈[m/2]after initialization

    The probability is at least1−e −Ω(n) thatk≤ |x| 1 ≤n−k. By applying a union bound on allµ individuals, the probability is at moste −Ω(µn) that there exists no individualxwithk≤ |x| 1 ≤n−kfor allj∈[m/2]after initialization. Sinceµ= Ω(n), this case is proven. Ifm≥4, we still can estimate the probability thatk≤ |x j|1 ≤2n/m−kfor a given blockj∈[m/2]by2/3from...

    work page 2015

  44. [44]

    We divide the run into two phases, where the second phase only applies ifγ >288n

    m/2, which impliesc t(v)≤γ≤ ⌊µ/(2|S|)⌋ ≤ ⌊µ/(2(1 + 2n/m)m/2)⌋. We divide the run into two phases, where the second phase only applies ifγ >288n. Phase 1:We havec t(v)≥ν:= min{γ,288n}. Forj∈[ν−1]letW j be a random variable that counts the number of generationstwithc t(v) =j. Then the number of generations until the cover number ofvis at leastνis at mostW:=...

    work page 2015