The Non-dominated Sorting Genetic Algorithm-II (NSGA-II) is one of the most prominent algorithms to solve multi-objective optimization problems. Recently, first mathematical runtime guarantees have been obtained for this algorithm, however only synthetic benchmark In work, we give proven performance a classic problem, NP-complete bi-objective minimum spanning tree problem. More specifically, show that NSGA-II with population size N >= 4((n-1) wmax + 1) computes all extremal points Pareto...

The Non-dominated Sorting Genetic Algorithm II (NSGA-II) is the most prominent multi-objective evolutionary algorithm for real-world applications. While it performs evidently well on bi-objective optimization problems, empirical studies suggest that less effective when applied to problems with more than two objectives. A recent mathematical runtime analysis confirmed this observation by proving NGSA-II an exponential number of iterations misses a constant factor Pareto front simple...

The Non-dominated Sorting Genetic Algorithm II (NSGA-II) is the most prominent multi-objective evolutionary algorithm for realworld applications.While it performs evidently well on bi-objective optimization problems, empirical studies suggest that less effective when applied to problems with more than two objectives.A recent mathematical runtime analysis confirmed this observation by proving NGSA-II an exponential number of iterations misses a constant factor Pareto front simple -objective...

In order to understand better how and why crossover can benefit optimization, we consider pseudo-Boolean functions with an upper bound B on the number of 1s allowed in bit string (cardinality constraint). We natural translation OneMax test function, a linear function where bits have weight 1 + ε remaining 1. The literature gives Θ(n2) for (1+1) EA this function.

To understand better how and why crossover can benefit constrained optimization, we consider pseudo-Boolean functions with an upper bound B on the number of 1-bits allowed in length- n bit string (i.e., a cardinality constraint). We investigate natural translation OneMax test function to this setting, linear where bits have weight 1+ 1/ remaining 1. Friedrich et al. [TCS 2020] gave Θ ( 2 ) for expected running time (1+1) EA function. Part difficulty when optimizing problem lies having...

We study the complexity-theoretic boundaries of tractability for three classical problems in context Hierarchical Task Network Planning: validation a provided plan, whether an executable plan exists, and given state can be reached by some plan. show that all solved polynomial time on primitive task networks constant partial order width (and generalization thereof), whereas latter two this holds only under provably necessary restriction to space. Next, we obtain algorithmic meta-theorem along...

Despite significant progress in the field of mathematical runtime analysis multi-objective evolutionary algorithms (MOEAs), performance MOEAs on discrete many-objective problems is little understood. In particular, few existing bounds for SEMO, global and SMS-EMOA classic benchmarks are all roughly quadratic size Pareto front. this work, we prove near-tight guarantees these three four most common benchmark OneMinMax, CountingOnesCountingZeros, LeadingOnesTrailingZeros, OneJumpZeroJump,...

A crucial challenge arising in the design of large-scale logistical networks is to optimize parcel sortation for routing. We study this problem under recent graph-theoretic formalization Van Dyk, Klause, Koenemann and Megow (IPCO 2024). The asks - given an input digraph D (the fulfillment network) together with a set commodities represented as source-sink tuples minimum-outdegree subgraph H transitive closure that contains route each commodities. Given underlying motivation, we two variants...

Recently, the first mathematical runtime guarantees have been obtained for NSGA-II, one of most prominent multi-objective optimization algorithms, however only synthetic benchmark problems.In this work, we give proven performance a classic problem, NP-complete bi-objective minimum spanning tree problem.More specifically, show that NSGA-II with population size ≥ 4(( -1) max + 1) computes all extremal points Pareto front in an expected number ( 2 log( )) iterations, where is vertices, edges,...

The Non-dominated Sorting Genetic Algorithm-II (NSGA-II) is one of the most prominent algorithms to solve multi-objective optimization problems. Recently, first mathematical runtime guarantees have been obtained for this algorithm, however only synthetic benchmark In work, we give proven performance a classic problem, NP-complete bi-objective minimum spanning tree problem. More specifically, show that NSGA-II with population size $N \ge 4((n-1) w_{\max} + 1)$ computes all extremal points...

We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design for FPT graph problems. An oracle with $f$ an problem $\Pi$ on a $G$ parameter $k$ preprocesses in time $O(g(f,k) \cdot \textsf{poly}(n))$. When queried set $F$ of at most edges $G$, the reports answer $\Pi$-with same $k$-on $G-F$, i.e., deprived $F$. The should queries that is significantly faster than merely running best-known algorithm $G-F$ scratch. mainly $k$-Path $k$-Vertex Cover...

The study of algorithmic fairness received growing attention recently. This stems from the awareness that bias in input data for machine learning systems may result discriminatory outputs. For clustering tasks, one most central notions is formalization by Chierichetti, Kumar, Lattanzi, and Vassilvitskii [NeurIPS 2017]. A said to be fair, if each cluster has same distribution manifestations a sensitive attribute as whole set. motivated various applications where objects clustered have...

Traditional navigation services find the fastest route for a single driver. Though always using seems desirable every individual, selfish behavior can have undesirable effects such as higher energy consumption and avoidable congestion, even leading to overall individual travel times. In contrast, strategic routing aims at optimizing traffic all agents regarding global optimization goal. We introduce framework formalize real-world scenarios algorithmic problems study one of them, which we...

We study learning of indexed families from positive data where a learner can freely choose hypothesis space (with uniformly decidable membership) comprising at least the languages to be learned. This abstracts very universal task which found in many areas, for example (subsets of) regular or natural languages. are interested various restrictions on learning, such as consistency, conservativeness set-drivenness, exemplifying restrictions. Building previous results literature, we provide...

In language learning in the limit, most common type of hypothesis is to give an enumerator for a language. This so-called $W$-index allows naming arbitrary computably enumerable languages, with drawback that even membership problem undecidable. this paper we use different system which decidable namely programs characteristic functions (called $C$-indices). These indices have it now not whether given legal $C$-index. first analysis $C$-indices, structured account power various restrictions...

Modeling tools are commonly adopted in classrooms. However, complex state-based behavioral models still pose a challenge for students to understand and validate, mostly because of the intricate semantics these models. We investigated this developed dedicated tool support form validation framework based on YAKINDU Statechart Tools. Our simulates environments that interact with code generated from statecharts as means animate various open-ended scenarios predefined test cases students' This...

The Non-dominated Sorting Genetic Algorithm II (NSGA-II) is the most prominent multi-objective evolutionary algorithm for real-world applications. While it performs evidently well on bi-objective optimization problems, empirical studies suggest that less effective when applied to problems with more than two objectives. A recent mathematical runtime analysis confirmed this observation by proving NGSA-II an exponential number of iterations misses a constant factor Pareto front simple...