Chance constraints are frequently used to limit the probability of constraint violations in real-world optimization problems where the constraints involve stochastic components. We study chance-constrained submodular optimization problems, which capture a wide range of optimization problems with stochastic constraints. Previous studies considered submodular problems with stochastic knapsack constraints in the case where uncertainties are the same for each item that can be selected. However, uncertainty levels are usually variable with respect to the different stochastic components in real-world scenarios, and rigorous analysis for this setting is missing in the context of submodular optimization. This paper provides the first such analysis for this case, where the weights of items have the same expectation but different dispersion. We present greedy algorithms that can obtain a high-quality solution, i.e., a constant approximation ratio to the given optimal solution from the deterministic setting. In the experiments, we demonstrate that the algorithms perform effectively on several chance-constrained instances of the maximum coverage problem and the influence maximization problem.

Phylogenetic trees are unable to represent the evolutionary process for a collection of species if reticulation events happened, and a generalized model named phylogenetic network was introduced consequently. However, the representation of the evolutionary process for one gene is actually a phylogenetic tree that is ‘`contained’' in the phylogenetic network for the considered species containing the gene. Thus a fundamental computational problem named Tree Containment problem arises, which asks whether a phylogenetic tree is contained in a phylogenetic network. The previous research on the problem mainly focused on its rooted version of which the considered tree and network are rooted, and several algorithms were proposed when the considered network is binary or structure-restricted. There is almost no algorithm for its unrooted version except the recent fixed-parameter algorithm with runtime$O(4^kn^2)$, where k and n are the reticulation number and size of the considered unrooted binary phylogenetic network$N$, respectively. As the runtime is a little expensive when considering big values of k, we aim to improve it and successfully propose a fixed-parameter algorithm with runtime$O(2.594^kn^2)$in the paper. Additionally, we experimentally show its effectiveness on biological data and simulated data.

The Minimum Spanning Tree problem is a well-known combinatorial optimization problem, which has attracted much attention from the researchers in the field of evolutionary computing. Within the paper, a constrained version of the problem named Depth Restricted (1-2)-Minimum Spanning Tree problem is considered in the context of evolutionary algorithms, which had been shown to be NP-hard. We separately investigate the expected time (i.e., the expected number of fitness evaluations) of the (1+1) EA, the Multi-Objective Evolutionary Algorithm and its two variants adapted to the constrained version, to obtain an approximate solution with ratio 2 or 3/2 with respect to several different fitness functions. In addition, we observe a close connection between the constrained version and the Set Cover problem, and present a simple evolutionary algorithm for the 3-Set Cover problem. Based on the approximate solution returned by our evolutionary algorithm for the 3-Set Cover problem, an approximate solution with ratio better than 3/2 for the constrained version can be constructed.

Randomized search heuristics such as evolutionary algorithms are frequently applied to dynamic combinatorial optimization problems. Within this paper, we present a dynamic model of the classic Weighted Vertex Cover problem and analyze the performances of the two well-studied algorithms Randomized Local Search and (1+1) EA adapted to it, to contribute to the theoretical understanding of evolutionary computing for problems with dynamic changes. In our investigations, we use an edge-based representation based on the dual formulation of the problem and study the expected runtimes that the two algorithms require to maintain a 2-approximate solution when the given weighted graph is modified by an edge-editing or weight-editing operation. Considering the weights on the vertices may be exponentially large with respect to the size of the graph, the step size adaption strategy is incorporated. Our results show that both algorithms can recompute 2-approximate solutions for the studied dynamic changes efficiently

The investigations of linear pseudo-Boolean functions play a central role in the area of runtime analysis of evolutionary computing techniques. Having an additional linear constraint on a linear function is equivalent to the NP-hard knapsack problem and special problem classes thereof have been investigated in recent works. In this paper, we extend these studies to problems with dynamic constraints and investigate the runtime of different evolutionary algorithms to recompute an optimal solution when the constraint bound changes by a certain amount. We study the classical (1+1) EA and population-based algorithms and show that they recompute an optimal solution very efficiently. Furthermore, we show that a variant of the (1+(λ, λ)) GA can recompute the optimal solution more efficiently in some cases.

A rigorous runtime analysis of evolutionary multi-objective optimization for the classical vertex cover problem in the context of parameterized complexity analysis has been presented by Kratsch and Neumann [ 1 ]. In this paper, we extend the analysis to the weighted vertex cover problem and provide a fixed parameter evolutionary algorithm with respect to OPT , the cost of the optimal solution for the problem. Moreover, using a diversity mechanism, we present a multi-objective evolutionary algorithm that finds a \(2-\) approximation in expected polynomial time. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.