Determination of Ribonucleic Acid structure is challenging, in order to optimize the RNA pseudoknotted structure, the paper investigates the computational problem and complexity of predicting RNA structure. A new comp...
详细信息
ISBN:
(纸本)9781479913343
Determination of Ribonucleic Acid structure is challenging, in order to optimize the RNA pseudoknotted structure, the paper investigates the computational problem and complexity of predicting RNA structure. A new computational method and model with minimum free energy are adopted to predict RNA structure. The main contribution of the paper is to achieves an efficient approximation algorithm for finding RNA pseudoknotted structure and nested structures. We have compared with other algorithms in time complexity and space complexity, the approximation algorithm takes O(n(3)) time and O(n(2)) space, where n is the length of the RNA sequences. The experimental tests for a large database of RNA show that the algorithm is more exact and effective than the algorithms, the algorithm can predict arbitrary pseudoknots, and improve the a predicting accuracy.
We consider the squared metric soft capacitated facility location problem (SMSCFLP), which includes both the squared metric facility location problem (SMFLP) and the soft capacitated facility location problem (SCFLP) ...
详细信息
ISBN:
(纸本)9783030349806;9783030349790
We consider the squared metric soft capacitated facility location problem (SMSCFLP), which includes both the squared metric facility location problem (SMFLP) and the soft capacitated facility location problem (SCFLP) as special cases. As our main contribution, we propose a primal-dual based 10-approximation algorithm for the SMSCFLP. Our work also extends the applicability of the primal-dual technique.
In a sweep-coverage problem, each point of interest should be visited at least once by some mobile sensor every required time interval. Because of energy constraint, each mobile sensor has to visit a base station for ...
详细信息
In a sweep-coverage problem, each point of interest should be visited at least once by some mobile sensor every required time interval. Because of energy constraint, each mobile sensor has to visit a base station for replenishment before running out of its power. We model the problem as a distance constraint sweep-coverage problem the goal of which is to minimize the sum of the number of mobile sensors and the number of base stations used to meet the requirements. This paper presents an approximation algorithm with a guaranteed approximation ratio 7.
Simulating noisy quantum circuits is vital in designing and verifying quantum algorithms in the current NISQ (Noisy Intermediate-Scale Quantum) era, where quantum noise is unavoidable. However, it is much more ineffic...
详细信息
ISBN:
(纸本)9798350348606;9783981926385
Simulating noisy quantum circuits is vital in designing and verifying quantum algorithms in the current NISQ (Noisy Intermediate-Scale Quantum) era, where quantum noise is unavoidable. However, it is much more inefficient than the classical counterpart because of the quantum state explosion problem (the dimension of state space is exponential in the number of qubits) and the complex (non-unitary) representation of noises. Consequently, only noisy circuits with up to about 50 qubits can be simulated approximately well. To improve the scalability of the circuits that can be simulated, this paper introduces a novel approximation algorithm for simulating noisy quantum circuits when the noisy effectiveness is insignificant. The algorithm is based on a new tensor network diagram for the noisy simulation and uses the singular value decomposition to approximate the tensors of quantum noises in the diagram. The contraction of the tensor network diagram is implemented on Google's TensorNetwork. The effectiveness and utility of the algorithm are demonstrated by experimenting on a series of practical quantum circuits with realistic superconducting noise models. As a result, our algorithm can approximately simulate quantum circuits with up to 225 qubits and 20 noises (within about 1.8 hours). In particular, our method offers a speedup over the commonly-used approximation (sampling) algorithm - quantum trajectories method [1]. Furthermore, our approach can significantly reduce the number of samples in the quantum trajectories method when the noise rate is small enough.
At a container port, container vessels are served by quay cranes for loading and unloading containers. Each vessel is typically split into bays from head to tail where containers are stored. Parallel quay cranes can p...
详细信息
At a container port, container vessels are served by quay cranes for loading and unloading containers. Each vessel is typically split into bays from head to tail where containers are stored. Parallel quay cranes can process different bays simultaneously, and their processing efficiency significantly affects the turn-around time of a container vessel. Sharing a single traveling rail, the quay cranes cannot crossover each other, and this phenomenon is referred as the non-crossing constraint. In addition, the quay cranes may have different processing speeds due to gradual equipment updates. Inspired by updating activities of cranes in modern container terminals, this paper studies a scheduling problem with two uniform quay cranes, aiming at minimizing the turn-around time of a vessel, i.e., the makespan. We mainly develop an integrated approximation algorithm which is min{(s + 1)/s, (s + 1)(2)/(s + 2)}-approximation, where the two quay cranes are of processing speeds 1 and s(>= 1), respectively.
The multi allocation p -hub median problem (MApHM), the multi allocation uncapacitated hub location problem (MAuHLP) and the multi allocation p -hub location problem (MApHLP) are common hub location problems with seve...
详细信息
The multi allocation p -hub median problem (MApHM), the multi allocation uncapacitated hub location problem (MAuHLP) and the multi allocation p -hub location problem (MApHLP) are common hub location problems with several practical applications. HLPs combine the task of constructing a network and solving a routing on that network. Specifically, a set of hubs must be chosen and each routing must be performed using one or two hubs as stopovers. The costs between two hubs are discounted by a parameter α . The objective is to minimize the total transportation cost in the MApHM and additionally to minimize the set-up costs for the hubs in the MAuHLP and MApHLP. In this paper, an approximation algorithm to solve these problems is developed, which improves the approximation bound for MAuHLP to 2.408. The proposed algorithm reduces the HLPs to Facility Location Problems (FLPs), incorporating the idea of preferring hubs in the direction of the destination. Depending on the HLP, different FLP approximation algorithms with approximation bound γ are used. In cases where the discount factor satisfies 0 < α < 1 γ or α ≥ 0 . 619 , the resulting approximation bound still improves upon the current state of the art. The proposed algorithm is capable of solving much bigger instances than any exact algorithm in the literature. New benchmark instances have been created and published, such that HLP algorithms can be tested and compared on standardized huge instances. There, the proposed algorithm outperformed the previous best approximation algorithm in nearly all test instances.
In this paper,we consider the-prize-collecting minimum vertex cover problem with submodular penalties,which generalizes the well-known minimum vertex cover problem,minimum partial vertex cover problem and minimum vert...
详细信息
In this paper,we consider the-prize-collecting minimum vertex cover problem with submodular penalties,which generalizes the well-known minimum vertex cover problem,minimum partial vertex cover problem and minimum vertex cover problem with submodular *** are given a cost graph and an *** problem determines a vertex set such that covers at least *** objective is to minimize the total cost of the vertices in plus the penalty of the uncovered edge set,where the penalty is determined by a submodular *** design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the *** the submodular penalty cost function is normalized and nondecreasing,the proposed algorithm has an approximation factor *** the submodular penalty cost function is linear,the approximation factor of the proposed algorithm is reduced to,which is the best factor if the unique game conjecture holds.
Emphasis on effective demand management is becoming increasingly recognized as an important factor in operations performance as well as the supply management. One of the known leverages to demand management is pricing...
详细信息
Emphasis on effective demand management is becoming increasingly recognized as an important factor in operations performance as well as the supply management. One of the known leverages to demand management is pricing. In joint pricing and production planning problem, manufacturer or supplier faces a price-sensitive demand and it should maximize its profit by making decision on the production policy among the finite time horizon while predicting the demand via determination of the prices of the products it sells. In this paper, a single-item joint pricing and production planning with concave revenue function has been discussed. By a piecewise linear approximation and reduction of the resulting problem to a bilinear one, an effective heuristic procedure has been proposed to solve it optimally. The efficiency of the procedure has been shown by numerical experiments.
Sequence comparison leads to a combinatorial optimization problem of sorting permutations by reversals and transpositions. Namely, given any two permutations, find the shortest distance between them. This problem is r...
详细信息
Sequence comparison leads to a combinatorial optimization problem of sorting permutations by reversals and transpositions. Namely, given any two permutations, find the shortest distance between them. This problem is related with genome rearrangement. The sorting of signed permutations is studied. Because in genome rearrangement, genes are oriented in DNA sequences. The transpositions which have been studied in the literature can be viewed as operations working on two consecutive segments of the genome. In this paper, a new kind of transposition which can work on two arbitrary segments of the genome is proposed, and the sorting of signed permutations by reversals and this new kind of transpositions are studied. After establishing a lower bound on the number of operations needed, a 2-approximation algorithm is presented for this problem and an example is given to show that the performance ratio of the algorithm cannot be improved.
In this paper,the authors study the multi-vehicle capacitated vehicle routing problem on a line-shaped network with unsplittable *** objective is to find a transportation scheme to minimize the longest distance travel...
详细信息
In this paper,the authors study the multi-vehicle capacitated vehicle routing problem on a line-shaped network with unsplittable *** objective is to find a transportation scheme to minimize the longest distance traveled by a single vehicle such that all the customers are served without violating the capacity *** authors show that this problem has no polynomialtime algorithm with performance ratio less than 2 on condition that P≠NP,and then provide a 2-approximation algorithm.
暂无评论