Abstract: This paper presents a methodology based oil genetic algorithms, which finds feasible and reasonably adequate Solutions to problems of robust design in multivariate systems. We use a genetic algorithm to determine the appropriate control factor levels for simultaneously optimizing all of the responses of the system, considering the noise factors which affect it. The algorithm is guided by a desirability function which works with only one fitness function although the system May have many responses. We validated the methodology using data obtained from a real system and also from a process simulator, considering univariate and multivariate systems. In all cases, the methodology delivered feasible solutions, which accomplished the goals of robust design: obtain responses very close to the target values of each of them, and with minimum variability. Regarding the adjustment of the mean of each response to the target value, the algorithm performed very well. However, only in some of the multivariate cases, the algorithm was able to significantly reduce the variability of the responses.

Abstract: Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded in a plane is upper bounded by the hull number of a corresponding planar 4-regular graph in cycle convexity. In this paper, we go further in the study of this new graph convexity and we study the interval number of a graph in cycle convexity. This parameter is, alongside the hull number, one of the most studied parameters in the literature about graph convexities. Precisely, given a graph G, its interval number in cycle convexity, denoted by in(cc)(G), is the minimum cardinality of a set S subset of V (G) such that every vertex w is an element of E V (G) \ S has two distinct neighbors u, v is an element of S such that u and v lie in same connected component of G[S], i.e. the subgraph of G induced by the vertices in S. In this work, first we provide bounds on in(cc) (G) and its relations to other graph convexity parameters, and explore its behaviour on grids. Then, we present some hardness results by showing that deciding whetherin(cc) (G) <= k is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[2]-hard in bipartite graphs when k is the parameter. As a consequence, we obtain that in(cc) (G) cannot be approximated up to a constant factor in the classes of split graphs and bipartite graphs (unless P = NP). On the positive side, we present polynomial-time algorithms to compute in(cc) (G) for outerplanar graphs, cobipartite graphs and interval graphs. We also present fixed-parameter tractable (FPT) algorithms to compute it for (q, q – 4)-graphs when q is the parameter and for general graphs G when parameterized either by the treewidth or the neighborhood diversity of G. Some of our hardness results and positive results are not known to hold for related graph convexities and domination problems. We hope that the design of our new reductions and polynomial-time algorithms can be helpful in order to advance in the study of related graph problems.

Abstract: Multi-band elastic optical networks are a promising alternative to meet the bandwidth demand of the ever-growing Internet traffic. In this letter, we propose a family of band allocation algorithms for multi-band elastic optical networks. Employing simulation, we evaluate the blocking performance of 3 algorithms of such a family and compare their performance with the only heuristic proposed to date. Results show that the three new algorithms outperform the previous proposal, with up to one order of magnitude improvement. We expect these results to help advance the area of dynamic resource allocation in multi-band elastic optical networks.

Abstract: In a previous article, we presented a genetic algorithm (GA), which finds solutions to problems of robust design in multivariate systems. Based on that GA, we developed a new GA that uses a new desirability function, based on the aggregation of the observed variance of the responses and the squared deviation between the mean of each response and its corresponding target value. Additionally, we also changed the crossover operator from a one-point to a uniform one. We used three different case studies to evaluate the performance of the new GA and also to compare it with the original one. The first case study involved using data from a univariate real system, and the other two employed data obtained from multivariate process simulators. In each of the case studies, the new GA delivered good solutions, which simultaneously adjusted the mean of each response to its corresponding target value. This performance was similar to the one of the original GA. Regarding variability reduction, the new GA worked much better than the original one. In all the case studies, the new GA delivered solutions that simultaneously decreased the standard deviation of each response to almost the minimum possible value. Thus, we conclude that the new GA performs better than the original one, especially regarding variance reduction, which was the main problem exhibited by the original GA.

Abstract: We are interested in the scheduling problem where there are several different resources that determine the speed at which a job runs and we pay depending on the amount of each resource that we use. This work is an extension of the resource dependent job processing time problem and the energy aware scheduling problems. We develop a new constant factor approximation algorithm for resource cost aware scheduling problems: the objective is to minimize the sum of the total cost of resources and the total weighted completion time in the one machine non-preemptive setting, allowing for arbitrary precedence constraints and release dates. Our algorithm handles general job-dependent resource cost functions. We also analyze the practical performance of our algorithms, showing that it is significantly superior to the theoretical bounds and in fact it is very close to optimal. The analysis is done using simulations and real instances, which are left publicly available for future benchmarks. We also present additional heuristic improvements and we study their performance in other settings. (C) 2018 Elsevier B.V. All rights reserved.

Abstract: Ensemble learning has gained considerable attention in different learning tasks including regression, classification, and clustering problems. One of the drawbacks of the ensemble is the high computational cost of training stages. Resampling local negative correlation (RLNC) is a technique that combines two well-known methods to generate ensemble diversity-resampling and error negative correlation-and a fine-grain parallel approach that allows us to achieve a satisfactory balance between accuracy and efficiency. In this paper, we introduce a structure of the virtual machine aimed to test diverse selection strategies of parameters in neural ensemble designs, such as RLNC. We assess the parallel performance of this approach on a virtual machine cluster based on the full virtualization paradigm, using speedup and efficiency as performance metrics, for different numbers of processors and training data sizes.

Abstract: Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by using this compiler, every linear-time algorithm for deciding the membership to some fixed graph class can be translated into a dMAM(O(log n)) protocol for this class, that is, a distributed interactive protocol with O(log n)-bit proof size in n-node graphs, and three interactions between the (centralized) computationally-unbounded but non-trustable prover Merlin, and the (decentralized) randomized computationally-limited verifier Arthur. As a corol-lary, there is a dMAM(O(log n)) protocol for recognizing the class of planar graphs, as well as for recognizing the class of graphs with bounded genus.We show that there exists a distributed interactive protocol for recognizing the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of O(log n) bits. This result also holds for the class of graphs with bounded non-orientable genus, that is, graphs that can be embedded on a non-orientable surface of bounded genus. The interactive protocols described in this paper are actually proof-labeling schemes, i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schn be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent proof-labeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded non-orientable genus.

Abstract: A Maximal Independent Set (MIS) is an inclusion maximal set of pairwise non-adjacent vertices. The computation of an MIS is one of the core problems in distributed computing. In this article, we introduce and analyze a finite-state distributed randomized algorithm for computing a Maximal Independent Set (MIS) on arbitrary undirected graphs. Our algorithm is self-stabilizing (reaches a correct output on any initial configuration) and can be implemented on systems with very scarce conditions. We analyze the convergence time of the proposed algorithm, showing that in many cases the algorithm converges in logarithmic time with high probability.

Abstract: Mine planning optimization aims at maximizing the profit obtained from extracting valuable ore. Beyond its theoretical complexity-the open-pit mining problem with capacity constraints reduces to a knapsack problem with precedence constraints, which is NP-hard-practical instances of the problem usually involve a large to very large number of decision variables, typically of the order of millions for large mines. Additionally, any comprehensive approach to mine planning ought to consider the underlying geostatistical uncertainty as only limited information obtained from drill hole samples of the mineral is initially available. In this regard, as blocks are extracted sequentially, information about the ore grades of blocks yet to be extracted changes based on the blocks that have already been mined. Thus, the problem lies in the class of multi-period large scale stochastic optimization problems with decision-dependent information uncertainty. Such problems are exceedingly hard to solve, so approximations are required. This paper presents an adaptive optimization scheme for multi-period production scheduling in open-pit mining under geological uncertainty that allows us to solve practical instances of the problem. Our approach is based on a rolling-horizon adaptive optimization framework that learns from new information that becomes available as blocks are mined. By considering the evolution of geostatistical uncertainty, the proposed optimization framework produces an operational policy that reduces the risk of the production schedule. Our numerical tests with mines of moderate sizes show that our rolling horizon adaptive policy gives consistently better results than a non-adaptive stochastic optimization formulation, for a range of realistic problem instances.

Abstract: Let P(G,X) be a property associating a boolean value to each pair (G,X) where G is a graph and X is a vertex subset. Assume that P is expressible in counting monadic second order logic (CMSO) and let t be an integer constant. We consider the following optimization problem: given an input graph G=(V,E), find subsets XFV such that the treewidth of G[F] is at most t, property P(G[F],X) is true and X is of maximum size under these conditions. The problem generalizes many classical algorithmic questions, e.g., Longest Induced Path, Maximum Induced Forest, IndependentH-Packing, etc. Fomin et al. (SIAM J Comput 44(1):54-87, 2015) proved that the problem is polynomial on the class of graph Gpoly, i.e. the graphs having at most poly(n) minimal separators for some polynomial poly. Here we consider the class Gpoly+kv, formed by graphs of Gpoly to which we add a set of at most k vertices with arbitrary adjacencies, called modulator. We prove that the generic optimization problem is fixed parameter tractable on Gpoly+kv, with parameter k, if the modulator is also part of the input.