Linear functions have gained a lot of attention in the area of run time analysis of evolutionary computation methods and the corresponding analyses have provided many effective tools for analyzing more complex problems. In this paper, we consider the behavior of the classical (1+1) Evolutionary Algorithm for linear functions under linear constraint. We show tight bounds in the case where both the objective and the constraint function is given by the OneMax function and present upper bounds as well as lower bounds for the general case. We also consider the LeadingOnes fitness function.
Given a public transportation network of stations and connections, we want to find a minimum subset of stations such that each connection runs through a selected station. Although this problem is NP-hard in general, real-world instances are regularly solved almost completely by a set of simple reduction rules. To explain this behavior, we view transportation networks as hitting set instances and identify two characteristic properties, locality and heterogeneity. We then devise a randomized model to generate hitting set instances with adjustable properties. While the heterogeneity does influence the effectiveness of the reduction rules, the generated instances show that locality is the significant factor. Beyond that, we prove that the effectiveness of the reduction rules is independent of the underlying graph structure. Finally, we show that high locality is also prevalent in instances from other domains, facilitating a fast computation of minimum hitting sets.
Multi-column dependencies in relational databases come associated with two different computational tasks. The detection problem is to decide whether a dependency of a certain type and size holds in a given database, the discovery problem asks to enumerate all valid dependencies of that type. We settle the complexity of both of these problems for unique column combinations (UCCs), functional dependencies (FDs), and inclusion dependencies (INDs). We show that the detection of UCCs and FDs is W[2]-complete when parameterized by the solution size. The discovery of inclusion-wise minimal UCCs is proven to be equivalent under parsimonious reductions to the transversal hypergraph problem of enumerating the minimal hitting sets of a hypergraph. The discovery of FDs is equivalent to the simultaneous enumeration of the hitting sets of multiple input hypergraphs. We further identify the detection of INDs as one of the first natural W[3]-complete problems. The discovery of maximal INDs is shown to be equivalent to enumerating the maximal satisfying assignments of antimonotone, 3-normalized Boolean formulas.
We design f-edge fault-tolerant diameter oracles (f-FDO, or simply FDO if f = 1). For a given directed or undirected and possibly edge-weighted graph G with n vertices and m edges and a positive integer f, we preprocess the graph and construct a data structure that, when queried with a set F of edges, where |F| ⩽ f, returns the diameter of G-F. An f-FDO has stretch σ ⩾ 1 if the returned value D^ satisfies diam(G-F) ⩽ D^ ⩽ σ diam(G-F).
For the case of a single edge failure (f = 1) in an unweighted directed graph, there exists an approximate FDO by Henzinger et al. [ITCS 2017] with stretch (1+e), constant query time, space O(m), and a combinatorial preprocessing time of O(mn + n^{1.5} √{Dm/e}), where D is the diameter.
We present an FDO for directed graphs with the same stretch, query time, and space. It has a preprocessing time of O(mn + n²/e), which is better for constant e > 0. The preprocessing time nearly matches a conditional lower bound for combinatorial algorithms, also by Henzinger et al. With fast matrix multiplication, we achieve a preprocessing time of O(n^{2.5794} + n²/e). We further prove an information-theoretic lower bound showing that any FDO with stretch better than 3/2 requires Ω(m) bits of space. Thus, for constant 0 < e < 3/2, our combinatorial (1+e)-approximate FDO is near-optimal in all parameters.
In the case of multiple edge failures (f > 1) in undirected graphs with non-negative edge weights, we give an f-FDO with stretch (f+2), query time O(f²log²{n}), O(fn) space, and preprocessing time O(fm). We complement this with a lower bound excluding any finite stretch in o(fn) space.
Many real-world networks have polylogarithmic diameter. We show that for those graphs and up to f = o(log n/ log log n) failures one can swap approximation for query time and space. We present an exact combinatorial f-FDO with preprocessing time mn^{1+o(1)}, query time n^o(1), and space n^{2+o(1)}. When using fast matrix multiplication instead, the preprocessing time can be improved to n^{ω+o(1)}, where ω < 2.373 is the matrix multiplication exponent.
Island models in evolutionary computation solve problems by a careful interplay of independently running evolutionary algorithms on the island and an exchange of good solutions between the islands. In this work, we conduct rigorous run time analyses for such island models trying to simultaneously obtain good run times and low communication effort.
Despite extensive research on distance oracles, there are still large gaps between the best constructions for spanners and distance oracles. Notably, there exist sparse spanners with a multiplicative stretch of $1+\varepsilon$ plus some additive stretch. A fundamental open problem is whether such a bound is achievable for distance oracles as well. Specifically, can we construct a distance oracle with multiplicative stretch better than 2, along with some additive stretch, while maintaining subquadratic space complexity? This question remains a crucial area of investigation, and finding a positive answer would be a significant step forward for distance oracles. Indeed, such oracles have been constructed for sparse graphs. However, in the more general case of dense graphs, it is currently unknown whether such oracles exist. In this paper, we contribute to the field by presenting the first distance oracles that achieve a multiplicative stretch of $1+\varepsilon$ along with a small additive stretch while maintaining subquadratic space complexity. Our results represent an advancement particularly for constructing efficient distance oracles for dense graphs. In addition, we present a whole family of oracles that, for any positive integer $k$, achieve a multiplicative stretch of $2k-1+\varepsilon$ using $o(n^{1+1/k})$ space.
'/%3e%3c/defs%3e%3cpath fill='%23012169' d='M0 0h10080v5040H0z'/%3e%3cpath stroke='%23fff' stroke-width='.6' d='m0 0 6 3m0-3L0 3' clip-path='url(%23b)' transform='scale(840)'/%3e%3cpath stroke='%23e4002b' stroke-width='.4' d='m0 0 6 3m0-3L0 3' clip-path='url(%23c)' transform='scale(840)'/%3e%3cpath stroke='%23fff' stroke-width='840' d='M2520 0v2520M0 1260h5040'/%3e%3cpath stroke='%23e4002b' stroke-width='504' d='M2520 0v2520M0 1260h5040'/%3e%3cg fill='%23fff'%3e%3cuse xlink:href='%23d' x='2520' y='3780'/%3e%3cuse xlink:href='%23a' x='7560' y='4200'/%3e%3cuse xlink:href='%23a' x='6300' y='2205'/%3e%3cuse xlink:href='%23a' x='7560' y='840'/%3e%3cuse xlink:href='%23a' x='8680' y='1869'/%3e%3cuse xlink:href='%23e' x='8064' y='2730'/%3e%3c/g%3e%3c/svg%3e)