Search

Router nodes placement (RNP) is an important issue in the design and implementation of wireless mesh networks (WMN). This is known as an P-hard problem, which cannot be solved using conventional algorithms. Consequently, approximate optimization strategies are commonly used to solve this problem. With heavy node density and wide-area WMNs, solving the RNP problem using approximation algorithms often faces many difficulties, therefore, a more effective solution is necessary. This motivated us to conduct this work. We propose a new method for solving the RNP problem using reinforcement learning (RL). The RNP problem is modeled as an RL model with environment, agent, action, and reward are equivalent to the network system, routers, coordinate adjustment, and connectivity of the RNP problem, respectively. To the best of our knowledge, this is the first study that applies RL to solve the RNP problem. The experimental results showed that the proposed method increased the network connectivity by up to 22.73% compared to the most recent methods. [ABSTRACT FROM AUTHOR]

In solving the whole process of interaction between soft rock and yielding support in high-stress environments in tunnels using mechanical analysis methods, it is challenging to simultaneously satisfy both displacement coordination and static equilibrium at the contact surface between the rock and the support structure. This paper, based on the mechanical analysis of rock and rigid support, considers the impact of the circumferential installation of yielding elements on radial displacement, and proposes displacement approximation and support force approximation methods using displacement coordination and static equilibrium as approximation conditions. The study fits curves of numerical simulation results and laboratory test results of yielding elements, and attempts to directly use the laboratory test data set of yielding elements as computational data. By calculating two circular tunnel examples and comparing the effects of the trisection method, bisection method, and substitution method on the convergence of the displacement approximation method, the effectiveness of the methods proposed in this paper is verified. The research results show that the two approximation algorithms proposed in this paper have good accuracy and reliability in calculating the relative displacement of rock and yielding support structure contact surfaces, and the support force of yielding support. The bisection method outperforms the trisection and substitution methods in terms of stability and convergence. However, there are certain limitations in this study, such as the effectiveness of the algorithm may be influenced by geological conditions; the complexity of actual geological conditions may exceed the assumptions of the current rock-support mechanical analysis model. [ABSTRACT FROM AUTHOR]

We present improved algorithms for the Steiner tree problem with the minimum number of Steiner points and bounded edge length. Given n terminal points in a 2D Euclidean plane and an edge length bound, the problem asks to construct a spanning tree of n terminal points with minimal Steiner points such that every edge length of the spanning tree is within the given bound. This problem is known to be NP-hard and has practical applications such as relay node placements in wireless networks, wavelength-division multiplexing(WDM) optimal network design, and VLSI design. The best-known deterministic approximation algorithm has O(n3) running time with an approximation ratio of 3. This paper proposes an efficient approximation algorithm using the Voronoi diagram that guarantees an approximation ratio of 3 in O(n log n) time. We also present the first exact algorithm to find an optimal Steiner tree for given three terminal points in constant time. Using this exact algorithm, we improve the 3-approximation algorithm with better performance regarding the number of required Steiner points in O(n log n) time. [ABSTRACT FROM AUTHOR]

In the engineering and economic management fields, optimisation models frequently involve different decision-making levels. These are known as multi-level optimisation problems. Because the decision-making process of such problems are hierarchical, they are also called a hierarchical optimisation problems. When the problem involves only two-level decision-making, the corresponding optimisation model is referred to as a bilevel programming problem(BLPP). To address the complex nonlinear bilevel programming problem, in this study, we design an evolutionary algorithm embedded with a surrogate model-that it is a approximation method and correlation coefficients. First, the isodata method is used to group the initial population, and the correlation coefficients of the individuals in each group are determined based on the rank of the leader and follower objective functions. Second, for the offspring individuals produced by the evolutionary operator, the surrogate model is used to approximate the solution of the follower's programming problem, during which the points in the population are screened by combining the correlation coefficients. Finally, a new crossover operator is designed by the spherical search method, which diversifies the generated offspring. The simulation experimental results demonstrate that the proposed algorithm can effectively obtain an optimal solution. [ABSTRACT FROM AUTHOR]

Single-cell genome sequencing provides a highly granular view of biological systems but is affected by high error rates, allelic amplification bias, and uneven genome coverage. This creates a need for data-specific computational methods, for purposes such as for cell lineage tree inference. The objective of cell lineage tree reconstruction is to infer the evolutionary process that generated a set of observed cell genomes. Lineage trees may enable a better understanding of tumor formation and growth, as well as of organ development for healthy body cells. We describe a method, Scelestial, for lineage tree reconstruction from single-cell data, which is based on an approximation algorithm for the Steiner tree problem and is a generalization of the neighbor-joining method. We adapt the algorithm to efficiently select a limited subset of potential sequences as internal nodes, in the presence of missing values, and to minimize cost by lineage tree-based missing value imputation. In a comparison against seven state-of-the-art single-cell lineage tree reconstruction algorithms—BitPhylogeny, OncoNEM, SCITE, SiFit, SASC, SCIPhI, and SiCloneFit—on simulated and real single-cell tumor samples, Scelestial performed best at reconstructing trees in terms of accuracy and run time. Scelestial has been implemented in C++. It is also available as an R package named RScelestial. Author summary: Reconstructing the evolutionary history from the genome sequences of single cells can provide a detailed understanding of evolutionary events and changes on a very fine-grained scale, for instance in the development of organs and cancer. Due to the increasing sizes of single-cell datasets, scalable and accurate methods are required. In this work we describe Scelestial, a software implementing an adapted Steiner tree approximation algorithm for evolutionary tree reconstruction from the analysis of single-cell datasets. The Steiner tree approximation algorithm, unlike other heuristics and sampling-based methods (e. g. Markov chain Monte Carlo), provides guarantees of its performance. A comparison of Scelestial with state of the art methods showed that it performed favourably in terms of quality of the inferred trees as well as speed across a large number of simulated data sets, and produced the most plausible evolutionary scenarios on single cell data sets from cancer patients. Taken together, our results show that Scelestial provides a valuable addition to current single cell lineage inference techniques. [ABSTRACT FROM AUTHOR]

Selecting a cohort from a set of candidates is a common task within and beyond academia. Admitting students, awarding grants, and choosing speakers for a conference are situations where human biases may affect the selection of any particular candidate, and, thereby the composition of the final cohort. In this paper, we propose a new algorithm, entrofy, designed to be part of a human-in-the-loop decision making strategy aimed at making cohort selection as just, transparent, and accountable as possible. We suggest embedding entrofy in a two-step selection procedure. During a merit review, the committee selects all applicants, submissions, or other entities that meet their merit-based criteria. This often yields a cohort larger than the admissible number. In the second stage, the target cohort can be chosen from this meritorious pool via a new algorithm and software tool called entrofy. entrofy optimizes differences across an assignable set of categories selected by the human committee. Criteria could include academic discipline, home country, experience with certain technologies, or other quantifiable characteristics. The entrofy algorithm then yields the approximation of pre-defined target proportions for each category by solving the tie-breaking problem with provable performance guarantees. We show how entrofy selects cohorts according to pre-determined characteristics in simulated sets of applications and demonstrate its use in a case study of Astro Hack Week. This two stage candidate and cohort selection process allows human judgment and debate to guide the assessment of candidates' merit in step 1. Then the human committee defines relevant diversity criteria which will be used as computational parameters in entrofy. Once the parameters are defined, the set of candidates who meet the minimum threshold for merit are passed through the entrofy cohort selection procedure in step 2 which yields a cohort of a composition as close as possible to the computational parameters defined by the committee. This process has the benefit of separating the meritorious assessment of candidates from certain elements of their diversity and from some considerations around cohort composition. It also increases the transparency and auditability of the process, which enables, but does not guarantee, fairness. Splitting merit and diversity considerations into their own assessment stages makes it easier to explain why a given candidate was selected or rejected, though it does not eliminate the possibility of objectionable bias. [ABSTRACT FROM AUTHOR]

The gradient vector flow (GVF) is an effective external force to deform the active contours. However, it suffers from high computational cost. For efficiency, the virtual electric field (VEF) model has been proposed, which can be implemented in real time thanks to fast Fourier transform (FFT). The VEF model has large capture range and low computation cost, but it has the limitations of sensitivity to noise and leakage on weak edge. The recently proposed CONVEF (Convolutional Virtual Electric Field) model takes the VEF model as a convolutional operation and employed another convolution kernel to overcome the drawbacks of the VEF model. In this paper, we employ an edge stopping function similar to that in the anisotropic diffusion to further improve the CONVEF model, and the proposed model is referred to as MCONVEF (Modified CONVEF) model. In addition, a piecewise constant approximation algorithm is borrowed to accelerate the calculation of the MCONVEF model. The proposed MCONVEF model is compared with the GVF and VEF models, and the experimental results are presented to demonstrate its superiority in terms of noise robustness, weak edge preserving and deep concavity convergence. [ABSTRACT FROM AUTHOR]

Approximation algorithms with linear complexities are required in the treatments of big data, however, present algorithms cannot output the diameter of a set of points with arbitrary accuracy and near-linear complexity. By introducing the partition technique, we introduce a very simple approximation algorithm with arbitrary accuracy ε and a complexity of O(N + ε−1 log ε−1) for the cases that all points are located in an Euclidean plane. The error bounds are proved strictly, and are verified by numerical tests. This complexity is better than existing algorithms, and the present algorithm is also very simple to be implemented in applications. [ABSTRACT FROM AUTHOR]

For the full-bridge LLC converter, it is necessary to establish a large signal model with low-complexity and high-precision when the current of filter inductor works under the continuous conduction mode (CCM) situation. In terms of low complexity, peak values of resonant state variables and average values of slow state variables are taken as the measured indexes between models and actual converter. Models based on the first harmonic approximation (FHA) are studied in depth because they have lower complexity than the existing models. From prospective of high precision, deficiencies of typical FHA model are explained in the light of harmonic generation mechanism of primary current and influence of Fourier series on the typical equivalent circuit. Therefore, transient process of each metallic oxide semiconductor field effect transistor (MOSFET) and its related fast recovery diode, transient process of Schottky rectifier diodes, piecewise equivalent circuit, appropriate selection of variables, and simplified modified dynamic equations are all considered. Furthermore, the unified proposed model is achieved according to the equivalent principle of indexes between aforementioned improved analyses and proposed model. Numerical results of typical FHA model and proposed model are given in accordance with the key indexes. Then, corresponding experimental results are also presented. Differences of indexes between the two models and the actual converter are compared respectively. Though complexity of proposed model is the same as that of typical FHA model, precision of proposed model is higher than that of typical FHA model. [ABSTRACT FROM AUTHOR]

Finding optimal markers for microorganisms important in the medical, agricultural, environmental or ecological fields is of great importance. Thousands of complete microbial genomes now available allow us, for the first time, to exhaustively identify marker proteins for groups of microbial organisms. In this work, we model the biological task as the well-known mathematical “hitting set” problem, solving it based on both greedy and randomized approximation algorithms. We identify unique markers for 17 phenotypic and taxonomic microbial groups, including proteins related to the nitrite reductase enzyme as markers for the non-anammox nitrifying bacteria group, and two transcription regulation proteins, nusG and yhiF, as markers for the Archaea and Escherichia/Shigella taxonomic groups, respectively. Additionally, we identify marker proteins for three subtypes of pathogenic E. coli, which previously had no known optimal markers. Practically, depending on the completeness of the database this algorithm can be used for identification of marker genes for any microbial group, these marker genes may be prime candidates for the understanding of the genetic basis of the group's phenotype or to help discover novel functions which are uniquely shared among a group of microbes. We show that our method is both theoretically and practically efficient, while establishing an upper bound on its time complexity and approximation ratio; thus, it promises to remain efficient and permit the identification of marker proteins that are specific to phenotypic or taxonomic groups, even as more and more bacterial genomes are being sequenced. [ABSTRACT FROM AUTHOR]

The prediction of protein complexes from protein-protein interactions (PPIs) is a well-studied problem in bioinformatics. However, the currently available PPI data is not enough to describe all known protein complexes. In this paper, we express the problem of determining the minimum number of (additional) required protein-protein interactions as a graph theoretic problem under the constraint that each complex constitutes a connected component in a PPI network. For this problem, we develop two computational methods: one is based on integer linear programming (ILPMinPPI) and the other one is based on an existing greedy-type approximation algorithm (GreedyMinPPI) originally developed in the context of communication and social networks. Since the former method is only applicable to datasets of small size, we apply the latter method to a combination of the CYC2008 protein complex dataset and each of eight PPI datasets (STRING, MINT, BioGRID, IntAct, DIP, BIND, WI-PHI, iRefIndex). The results show that the minimum number of additional required PPIs ranges from 51 (STRING) to 964 (BIND), and that even the four best PPI databases, STRING (51), BioGRID (67), WI-PHI (93) and iRefIndex (85), do not include enough PPIs to form all CYC2008 protein complexes. We also demonstrate that the proposed problem framework and our solutions can enhance the prediction accuracy of existing PPI prediction methods. ILPMinPPI can be freely downloaded from . [ABSTRACT FROM AUTHOR]

Best investment in the road infrastructure or the network design is perceived as a fundamental and benchmark problem in transportation. Given a set of candidate road projects with associated costs, finding the best subset with respect to a limited budget is known as a bilevel Discrete Network Design Problem (DNDP) of NP-hard computationally complexity. We engage with the complexity with a hybrid exact-heuristic methodology based on a two-stage relaxation as follows: (i) the bilevel feature is relaxed to a single-level problem by taking the network performance function of the upper level into the user equilibrium traffic assignment problem (UE-TAP) in the lower level as a constraint. It results in a mixed-integer nonlinear programming (MINLP) problem which is then solved using the Outer Approximation (OA) algorithm (ii) we further relax the multi-commodity UE-TAP to a single-commodity MILP problem, that is, the multiple OD pairs are aggregated to a single OD pair. This methodology has two main advantages: (i) the method is proven to be highly efficient to solve the DNDP for a large-sized network of Winnipeg, Canada. The results suggest that within a limited number of iterations (as termination criterion), global optimum solutions are quickly reached in most of the cases; otherwise, good solutions (close to global optimum solutions) are found in early iterations. Comparative analysis of the networks of Gao and Sioux-Falls shows that for such a non-exact method the global optimum solutions are found in fewer iterations than those found in some analytically exact algorithms in the literature. (ii) Integration of the objective function among the constraints provides a commensurate capability to tackle the multi-objective (or multi-criteria) DNDP as well. [ABSTRACT FROM AUTHOR]

Memory-related activity in the Dentate Gyrus (DG) is characterized by sparsity. Memory representations are seen as activated neuronal populations of granule cells, the main encoding cells in DG, which are estimated to engage 2–4% of the total population. This sparsity is assumed to enhance the ability of DG to perform pattern separation, one of the most valuable contributions of DG during memory formation. In this work, we investigate how features of the DG such as its excitatory and inhibitory connectivity diagram can be used to develop theoretical algorithms performing Sparse Approximation, a widely used strategy in the Signal Processing field. Sparse approximation stands for the algorithmic identification of few components from a dictionary that approximate a certain signal. The ability of DG to achieve pattern separation by sparsifing its representations is exploited here to improve the performance of the state of the art sparse approximation algorithm “Iterative Soft Thresholding” (IST) by adding new algorithmic features inspired by the DG circuitry. Lateral inhibition of granule cells, either direct or indirect, via mossy cells, is shown to enhance the performance of the IST. Apart from revealing the potential of DG-inspired theoretical algorithms, this work presents new insights regarding the function of particular cell types in the pattern separation task of the DG. [ABSTRACT FROM AUTHOR]

Outbreaks of coral diseases are one of the greatest threats to reef corals in the Caribbean, yet the mechanisms that lead to coral diseases are still largely unknown. Here we examined the spatial-temporal dynamics of white-pox disease on Acropora palmata coral colonies of known genotypes. We took a Bayesian approach, using Integrated Nested Laplace Approximation algorithms, to examine which covariates influenced the presence of white-pox disease over seven years. We showed that colony size, genetic susceptibility of the coral host, and high-water temperatures were the primary tested variables that were positively associated with the presence of white-pox disease on A. palmata colonies. Our study also showed that neither distance from previously diseased individuals, nor colony location, influenced the dynamics of white-pox disease. These results suggest that white-pox disease was most likely a consequence of anomalously high water temperatures that selectively compromised the oldest colonies and the most susceptible coral genotypes. [ABSTRACT FROM AUTHOR]