A coloring concept is presented which shows the voltage level and the status of the power system element and allows the identification of the existing connectivity units. Connectivity units may be nodes, network group...
详细信息
A coloring concept is presented which shows the voltage level and the status of the power system element and allows the identification of the existing connectivity units. Connectivity units may be nodes, network groups (network islands), network districts (sets of interconnected nodes on the same level), and power source groups (elements fed by a common source point). The task of connectivity unit coloring is converted to the task of coloring a graph. This enables graph theory to be applied. An update algorithm is provided to update graph colors after vertex-edge changes caused by switch indication changes. Issues in implementing such a power system coloring function within a full graphic based energy management system are discussed. A typical example is the trade-off between software effort, computational complexity (performance), and the number of colors required.< >
In this paper, we study the feasibility problem of scheduling a set of start time dependent tasks on a single machine with deadlines, processing rates and identical initial processing times. First, we show that the ca...
详细信息
In this paper, we study the feasibility problem of scheduling a set of start time dependent tasks on a single machine with deadlines, processing rates and identical initial processing times. First, we show that the cases with arbitrary deadlines are strongly NP-complete. Second, we show that the cases with two distinct deadlines are NP-complete in the ordinary sense. Finally, we give an optimal polynomial algorithm for the makespan problem with two distinct processing rates. We solve a series of open problems in the literature and give a sharp boundary delineating the complexity of the problems.
Automated karyotyping for chromosome classification is an essential task in cytogenetics for diagnosis of genetic disorders and has therefore been an important pattern recognition problem. The existing learning approa...
详细信息
Automated karyotyping for chromosome classification is an essential task in cytogenetics for diagnosis of genetic disorders and has therefore been an important pattern recognition problem. The existing learning approaches generally discard the previously acquired knowledge and often require retraining, leading to space and time complexities. Incremental learning methods have gained popularity in the current learning scenarios to deal with these issues. This study proposes a novel approach of incremental learning for chromosomes classification for automated karyotyping of metaphase chromosomes. It addresses the issue of catastrophic forgetting with the generation of new class and performs knowledge amassing to classify the chromosomes in Denver groups (A-G). The adaptive nature of the proposed method contributes to its sustained accuracy even for dynamically changing data. An average classification accuracy of 97% is achieved with experimentation on 1800 chromosomes from a publicly available database.
Approximate computing exploits the fact that many applications do not require the results to be exact but not to exceed a threshold in a given error metric. Algorithms in approximate computing require to compute the e...
详细信息
Approximate computing exploits the fact that many applications do not require the results to be exact but not to exceed a threshold in a given error metric. Algorithms in approximate computing require to compute the error of the approximation in order to measure its quality. In this paper, the computational complexity of several of such error metrics commonly used in approximate computing is investigated. We show that these metrics lie within the complexity classes FPNP and #P and, therefore, are hard to compute. We further classify the error metrics into two classes. The framework used in this generalization is then used to exemplary develop specialized error metrics. (C) 2018 Elsevier B.V. All rights reserved.
This study presents a distributed gradient-based approach to solve system optimal dynamic traffic assignment (SODTA) formulated based on the cell transmission model. The algorithm distributes SODTA into local sub-prob...
详细信息
This study presents a distributed gradient-based approach to solve system optimal dynamic traffic assignment (SODTA) formulated based on the cell transmission model. The algorithm distributes SODTA into local sub-problems, who find optimal values for their decision variables within an intersection. Each sub-problem communicates with its immediate neighbors to reach a consensus on the values of common decision variables. A sub-problem receives proposed values for common decision variables from all adjacent sub-problems and incorporates them into its own offered values by weighted averaging and enforcing a gradient step to minimize its objective function. Then, the updated values are projected onto the feasible region of the sub-problems. The algorithm finds high quality solutions in all tested scenarios with a finite number of iterations. The algorithm is tested on a case study network under different demand levels and finds solutions with at most a 5% optimality gap.
This study proposes a video retargeting method using deep neural network-based object detection. First, the meaningful regions of the input video denoted by bounding boxes of the object detection are extracted. In thi...
详细信息
This study proposes a video retargeting method using deep neural network-based object detection. First, the meaningful regions of the input video denoted by bounding boxes of the object detection are extracted. In this case, the area is defined considering the size and number of bounding boxes for objects detected. The bounding boxes of each frame image are considered as regions of interest (RoIs). Second, the Siamese object tracking network is used to address high computational complexity of the object detection network. By dividing the video into scenes, object detection is performed for the first frame image of each scene to obtain the first bounding box. Object tracking is performed for the next sequential frame image until a scene change is detected. Third, the image is resized in the horizontal direction to alter the aspect ratio of the image and obtain the 1D RoIs of the image by projecting bounding boxes in the vertical direction. Then, the proposed method computes the grid map from the 1D RoIs to calculate new coordinates of each column data of the image. Finally, the retargeted video is obtained by rearranging all retargeted frame images. Comparative experiments conducted with various benchmark methods show an average bidirectional similarity score of 1.92, which is higher than other conventional methods. The proposed method was stable and satisfied viewers without causing cognitive discomfort as conventional methods.
作者：
Yong XIAKey Laboratory of Mathematics
Informatics andBehavioral Semantics of the Ministry of Education of China Beihang University Beijing100083 China
The Gilmore-Lawler bound (GLB) is one of the well-known lower bound of quadratic assignment problem (QAP). Checking whether GLB is tight is an NP-complete problem. In this article, based on Xia and Yuan linearization ...
详细信息
The Gilmore-Lawler bound (GLB) is one of the well-known lower bound of quadratic assignment problem (QAP). Checking whether GLB is tight is an NP-complete problem. In this article, based on Xia and Yuan linearization technique, we provide an upper bound of the complexity of this problem, which makes it pseudo-polynomial solvable. We also pseudo-polynomially solve a class of QAP whose GLB is equal to the optimal objec-tive function value, which was shown to remain NP-hard.
In doing the statistical analysis of a bubble-sort program [1], where all computing operations were of the same type, we observed that the statistical results tallied fairly well with the mathematical claim about the ...
详细信息
In doing the statistical analysis of a bubble-sort program [1], where all computing operations were of the same type, we observed that the statistical results tallied fairly well with the mathematical claim about the algorithm's computational complexity. In our next algorithm, the computing operations are not of the same type. We test and observe that the statistical measure of the algorithm's complexity, arguably more 'realistic,' does not tally with its mathematical counterpart. (C) 1999 Elsevier Science Ltd. All rights reserved.
A polynomial-time algorithm based on a revised method of iterative central difference limit is presented for computing the numerical value of the derivative of a given analytic function. Through numerical experiments,...
详细信息
A polynomial-time algorithm based on a revised method of iterative central difference limit is presented for computing the numerical value of the derivative of a given analytic function. Through numerical experiments, we establish that this algorithm is a best one. This can be used to obtain the derivative to a desired accuracy subject to the precision of the computer for violently fluctuating or rapidly oscillatory functions. The concerned time/computational complexity is so small in practice that in the non-main-frame supercomputing era when over estimated 95% of computing resources is unutilized and hence a waste, the complexity here is not an issue. We have, for the purpose of a comparison, also included Matlab symbolic-cum-numerical computation to obtain the derivative of the foregoing functions numerically. Matlab programs in both Matlab standard precision as well as Matlab variable precision are also included for the central difference limit along with the symbolic-cum-numerical computation. The reader concerned with computing the derivative of an ill-conditioned function - large or small - can use these programs by copying, pasting, and executing and can readily check the quality of the derivative. (C) 2010 Elsevier Inc. All rights reserved.
This research addresses the challenges of high Peak-to-Average Power Ratio (PAPR), sideband leakage, and spectrum efficiency in 5G wireless networks. We compare Universal Filtered Multi-Carrier (UFMC), Scrambled UFMC ...
详细信息
This research addresses the challenges of high Peak-to-Average Power Ratio (PAPR), sideband leakage, and spectrum efficiency in 5G wireless networks. We compare Universal Filtered Multi-Carrier (UFMC), Scrambled UFMC (S-UFMC), and Orthogonal Frequency Division Multiplexing (OFDM) techniques using Amplitude Phase Shift Keying (APSK) modulation. Our findings show that APSK modulation significantly reduces PAPR compared to traditional methods. Integrating Particle Swarm Optimization (PSO) with Partial Transmit Sequences (PTS)-OFDM and S-UFMC minimizes PAPR and computational complexity. Results demonstrate that S-UFMC with PSO optimization achieves superior performance, offering lower PAPR, reduced complexity, and enhanced spectral efficiency, positioning it as a promising 5G waveform. This research highlights the potential of advanced waveform designs to improve 5G communication systems. UFMC demonstrated improved spectral efficiency with sidelobe levels reaching as low as 0.2, indicating efficient spectrum utilization. The research achieved a PAPR of 7.393 dB for 16-APSK with 512 subcarriers and 7.414 dB for 1024 subcarriers after optimization. The PSO algorithm significantly reduced PAPR values, with the Scrambled UFMC system outperforming PTS-OFDM and standard UFMC in terms of PAPR.
暂无评论