While many optimization problems work with a fixed number of decision variables and thus fixed-length representation possible solutions, genetic programming (GP) works on variable-length representations. A naturally occurring problem is that bloat (unnecessary growth solutions) slowing down optimization. Theoretical analyses could so far not bound required explicit assumptions the magnitude bloat.

Linear functions have gained a lot of attention in the area run time analysis evolutionary computation methods and corresponding analyses provided many effective tools for analyzing more complex problems. In this paper, we consider behavior classical (1+1) Evolutionary Algorithm linear under constraint. We show tight bounds case where both objective constraint function is given by OneMax present upper as well lower general case. also LeadingOnes fitness function.

Many important graph theoretic notions can be encoded as counting homomorphism problems, such partition functions in statistical physics, particular independent sets and colourings. In this article we study the complexity of #_pHomsToH, problem homomorphisms from an input to a H modulo prime number p. Dyer Greenhill proved dichotomy stating that tractability non-modular depends on structure target graph. intractable cases become tractable modular due common phenomenon cancellation....

We present fully polynomial approximation schemes for a broad class of Holant problems with complex edge weights, which we call polynomials. transform these into partition functions abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions the polymer models and using most significant terms cluster expansion to approximate them. Results our technique include new sampling algorithms diverse polynomials low-temperature regime...

We present fully polynomial approximation schemes for a broad class of Holant problems with complex edge weights, which we call polynomials. transform these into partition functions abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions the polymer models and using most significant terms cluster expansion to approximate them. Results our technique include new sampling algorithms diverse polynomials low-temperature regime...

Cobalt is a key ingredient of lithium-ion batteries and therefore crucial for many modern devices. To ensure ethical sourcing, consumers need way to verify provenance their cobalt-based products, including the percentage artisanally mined (ASM) cobalt. Existing frameworks supply chain traceability rely on distributed ledgers. Providing public verifiability via permissionless ledgers trivial. However, offering based confidential production details seems contradictory. Hence, existing lack...

Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between and map data, rendering preprocessing inapplicable. Furthermore, data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, number of loaded becomes major factor for run time. We study under these restrictions present new as well empirical evaluations. Our...

While many optimization problems work with a fixed number of decision variables and thus fixed-length representation possible solutions, genetic programming (GP) works on variable-length representations. A naturally occurring problem is that bloat (unnecessary growth solutions) slowing down optimization. Theoretical analyses could so far not bound required explicit assumptions the magnitude bloat. In this paper we analyze in mutation-based for two test functions ORDER MAJORITY. We overcome...

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...

Many important graph theoretic notions can be encoded as counting homomorphism problems, such partition functions in statistical physics, particular, independent sets and colourings. In this article we study the complexity of $\#_p\mathsf{H}$OMS$\mathsf{T}$O$H$, problem homomorphisms from an input to a $H$ modulo prime number $p$. Dyer Greenhill proved dichotomy stating that tractability non-modular depends on structure graph. intractable cases become tractable modular due common phenomenon...

For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation. First, the variable size representations, in particular yielding a possible bloat (i.e. growth individuals with redundant parts). Second, role and realization crossover, which is particularly central due to tree-based representation. Whereas some work on has studied effects bloat, crossover had surprisingly little share this work. We analyze simple operator combination local...

We generalize the tree doubling and Christofides algorithm, two most common approximations for TSP, to parameterized ATSP. The parameters we consider respective parameterizations are upper bounded by number of asymmetric distances in given instance, which yields algorithms efficiently compute constant factor also moderately TSP instances. As generalization derive a 2.5-approximation, where parameter is size vertex cover subgraph induced edges. Our algorithm gives 3-approximation, edges...

We study the problem of counting number homomorphisms from an input graph $G$ to a fixed (quantum) $\bar{H}$ in any finite field prime order $\mathbb{Z}_p$. The subproblem with $H$ was introduced by Faben and Jerrum [ToC'15] its complexity is subject growing series research articles, e.g. work Focke, Goldberg, Roth, Zivn\'y [SIDMA'21] Bulatov Kazeminia [STOC'22], subsequent this article's conference version. Our contribution threefold. First, we introduce quantum graphs modular...