## Crynodeb

Many production-grade algorithms benefit from combining an asymptotically efficient algorithm for solving big problem instances, by splitting them into smaller ones, and an asymptotically inefficient algorithm with a very small implementation constant for solving small subproblems. A well-known example is stable sorting, where mergesort is often combined with insertion sort to achieve a constant but noticeable speed-up.

We apply this idea to non-dominated sorting. Namely, we combine the divide-and-conquer algorithm, which has the currently best known asymptotic runtime of O(N(log N)^M−1), with the Best Order Sort algorithm, which has the runtime of O(N^2M) but demonstrates the best practical performance out of quadratic algorithms.

Empirical evaluation shows that the hybrid's running time is typically not worse than of both original algorithms, while for large numbers of points it outperforms them by at least 20%. For smaller numbers of objectives, the speedup can be as large as four times.

We apply this idea to non-dominated sorting. Namely, we combine the divide-and-conquer algorithm, which has the currently best known asymptotic runtime of O(N(log N)^M−1), with the Best Order Sort algorithm, which has the runtime of O(N^2M) but demonstrates the best practical performance out of quadratic algorithms.

Empirical evaluation shows that the hybrid's running time is typically not worse than of both original algorithms, while for large numbers of points it outperforms them by at least 20%. For smaller numbers of objectives, the speedup can be as large as four times.

Iaith wreiddiol | Saesneg |
---|---|

Teitl | GECCO '17 |

Is-deitl | Proceedings of the Genetic and Evolutionary Computation Conference Companion |

Cyhoeddwr | Association for Computing Machinery |

Tudalennau | 153-154 |

Nifer y tudalennau | 2 |

ISBN (Argraffiad) | 978-1-4503-4939-0 |

Dynodwyr Gwrthrych Digidol (DOIs) | |

Statws | Cyhoeddwyd - 15 Gorff 2017 |

Cyhoeddwyd yn allanol | Ie |

Digwyddiad | GECCO 2017: The Genetic and Evolutionary Computation Conference - Hyd: 15 Gorff 2017 → 19 Gorff 2017 |

### Cynhadledd

Cynhadledd | GECCO 2017 |
---|---|

Cyfnod | 15 Gorff 2017 → 19 Gorff 2017 |