We present an improved optimal parallel algorithm with time complexity O(log(3) n) for computing a maximal matching in a graph. The improvement is made on the recent result of Kelsen which requires O(log(4) n) time fo...
详细信息
We present an improved optimal parallel algorithm with time complexity O(log(3) n) for computing a maximal matching in a graph. The improvement is made on the recent result of Kelsen which requires O(log(4) n) time for computing a maximal matching. Our parallel algorithm is designed on the EREW PRAM model.
A function is unimodal if it strictly increases to a unique maximum and then strictly decreases. The problem of determining the smallest possible interval containing the maximum of a unimodal function, by probing only...
详细信息
A function is unimodal if it strictly increases to a unique maximum and then strictly decreases. The problem of determining the smallest possible interval containing the maximum of a unimodal function, by probing only at integer values is studied. In the finite case, the search takes place over the range 0 to N, while in the infinite case the search takes place over the nonnegative integers. The analyses are based on an unusual Fibonacci version of Kraft's inequality.
A graph G is P4-sparse if no set of five vertices in G induces more than one chordless path of length three. P4-sparse graphs generalize both the class of cographs and the class of P4-reducible graphs. One remarkable ...
详细信息
A graph G is P4-sparse if no set of five vertices in G induces more than one chordless path of length three. P4-sparse graphs generalize both the class of cographs and the class of P4-reducible graphs. One remarkable feature of P4-sparse graphs is that they admit a tree representation unique up to isomorphism. It has been shown that this tree representation can be obtained in polynomial time. This paper gives a linear time algorithm to recognize P4-sparse graphs and shows how the data structures returned by the recognition algorithm can be used to construct the corresponding tree representation in linear time.
Recent years has seen much progress in the theory and application of iterative learning control schemes for both linear and (classes of) nonlinear dynamics. In the case of the former, many algorithms based on minimizi...
详细信息
Recent years has seen much progress in the theory and application of iterative learning control schemes for both linear and (classes of) nonlinear dynamics. In the case of the former, many algorithms based on minimizing a suitable cost function have been reported. Here the interest is in the so-called norm optimal approach where the basic philosophy is to compute the control input on the current trial such that the tracking error is reduced in an optimal way without too much deviation from the control input used on the previous trial. This paper compares the performance of a range of controllers arising from use of the norm optimal approach - both stand alone and against alternatives.
Computation problems involving planar polygons have been the subject of a significant amount of research. A major focus of this research has been the minimum vertex distance problem, i.e., the problem of finding the ...
详细信息
Computation problems involving planar polygons have been the subject of a significant amount of research. A major focus of this research has been the minimum vertex distance problem, i.e., the problem of finding the shortest distance and the closest vertices between 2 sets of vertices. In the present study, the minimum vertex distance problem is examined for separable convex polygons. A linear algorithm is presented for finding the minimum vertex distances between 2 separable convex polygons; the solution is approachable in O(n) time and is asymptotically optimal.
The channel-assignment problem is central to the integrated circuit fabrication process. Given a two-sided printed circuit board, the problem is to make n pairs of components electrically equivalent. The connections a...
详细信息
The channel-assignment problem is central to the integrated circuit fabrication process. Given a two-sided printed circuit board, the problem is to make n pairs of components electrically equivalent. The connections are made using two vertical runs along with a horizontal one. Each horizontal run lies in a channel. The problem is to minimize the total number of channels used. Our main contribution is to propose a time- and cost-optimal parallel algorithm to solve this problem. Specifically, with an instance of size n of the channel assignment problem as input, our algorithm runs in O(log n)time and uses O(n) processors in the EREW-PRAM model of computation.
Given two sorted arrays A = (a1, a2,....., a(n1)) and B = (b1, b2,....,b(n2)) where their elements are drawn from a linear range in n and n = Max(n (1), n (2)). The merging of two sorted arrays is one of the fundament...
详细信息
Given two sorted arrays A = (a1, a2,....., a(n1)) and B = (b1, b2,....,b(n2)) where their elements are drawn from a linear range in n and n = Max(n (1), n (2)). The merging of two sorted arrays is one of the fundamental problems in computer science. The main contribution of this work is to give a new merging algorithm on a EREW PRAM. The algorithm is cost optimal, deterministic and simple. The algorithm uses n/logn processors and O(n) storage. We also give the conditions that make the algorithm run in a constant time on a EREW PRAM.
A technique to accelerate convergence of stochastic approximation algorithms is studied. It is based on Kesten's idea of equalization of the gain coefficient for the Robbins-Monro algorithm. Convergence with proba...
详细信息
A technique to accelerate convergence of stochastic approximation algorithms is studied. It is based on Kesten's idea of equalization of the gain coefficient for the Robbins-Monro algorithm. Convergence with probability is proved for the multidimensional analog of the Kesten accelerated stochastic approximation algorithm. Asymptotic normality of the delivered estimates is also shown. Results of numerical simulations are presented that demonstrate the efficiency of the acceleration procedure.
This paper considers an optimal control problem for switched nonlinear systems. The objective is to minimize an associated cost functional, by finding an appropriate continuous control input and location switching str...
详细信息
This paper considers an optimal control problem for switched nonlinear systems. The objective is to minimize an associated cost functional, by finding an appropriate continuous control input and location switching strategy. We propose an extension of an algorithm based on strong variations to handle constraints on both locations and switching instants. Numerical experiments testify the viability and the tractability of such a scheme.
作者：
Du, LinYan, YuqingLi, TianLiu, HuawangLi, NanWang, XinNankai Univ
Coll Environm Sci & Engn Tianjin Key Lab Environm Remediat & Pollut Contro MOE Key Lab Pollut Proc & Environm Criteria Tianjin 300350 Peoples R China Nankai Univ
Coll Artificial Intelligence Tianjin Key Lab Intelligent Robot Inst Robot & Automat Informat Syst Tianjin 300350 Peoples R China Tianjin Univ
Sch Environm Sci & Engn Tianjin 300072 Peoples R China
Microbial electrochemical sensors have been used to monitor water quality, with electroactive biofilms (EABs) serving as a core sensing element. However, since the bioelectric signals are incapable of recognizing diff...
详细信息
Microbial electrochemical sensors have been used to monitor water quality, with electroactive biofilms (EABs) serving as a core sensing element. However, since the bioelectric signals are incapable of recognizing different toxicants, the application of biosensors in complicated contamination is limited. With machine learning (ML) as a novel method to analyze bioelectric signals, we first quantified multiple toxicants with microbial electrochemical sensors. In this study, a batch of biosensors were shocked by mixed toxicants (MnCl2, NaNO2, and tetracycline hydrochloride (TCH)) at random concentrations. Regression ML models using different algorithms and datasets were developed and evaluated for prediction accuracy. The most accurate models for MnCl2, NaNO2, and TCH were trained with the algorithms of support vector machine, neural networks, and a generalized linear model. And the training set consisting of drop ratios at all time points showed the best accuracy for MnCl2 and NaNO2, while the most accurate model for TCH was trained with the drop ratio at 6 h. Here, we demonstrated that by integrating machine learning, a microbial electrochemical sensor is able to quantify multiple toxicants simultaneously, providing a fundamental of multiple-parameter biotoxicity detection for environmental monitoring.
暂无评论