Base station location has significant impact on network lifetime performance for a sensor network. For a multi-hop sensor network, this problem is particular challenging as we need to jointly consider base station pla...
详细信息
ISBN:
(纸本)9781424412679
Base station location has significant impact on network lifetime performance for a sensor network. For a multi-hop sensor network, this problem is particular challenging as we need to jointly consider base station placement and data routing strategy to maximize network lifetime performance. This paper presents an approximation algorithm that can guarantee (1 - epsilon) optimal network lifetime performance for base station placement problem with any desired error bound epsilon > 0. The proposed (1 - epsilon) optimal approximation algorithm is based on several novel techniques that enable to reduce an infinite search space to a finite-element search space for base station location. The first technique used in this reduction is to discretize cost parameters (with performance guarantee) associated with energy consumption. Subsequently, the continuous search space can be broken up into a finite number of subareas. The second technique is to exploit the cost property of each subarea and represent it by a novel notion called "fictitious cost point," each with guaranteed cost bounds. This approximation algorithm offers a simpler and in most cases practically faster algorithm than a state-of-the-art algorithm and represents the best known result to this important problem.
This paper presents an efficient approximation algorithm to solve the task scheduling problem on heterogeneous platform for the particular case of the linear chain of tasks. The objective is to minimize both the total...
详细信息
ISBN:
(数字)9783319751788
ISBN:
(纸本)9783319751788;9783319751771
This paper presents an efficient approximation algorithm to solve the task scheduling problem on heterogeneous platform for the particular case of the linear chain of tasks. The objective is to minimize both the total execution time (makespan) and the total energy consumed by the system. For this purpose, we introduce a constraint on the energy consumption during execution. Our goal is to provides an algorithm with a performance guarantee. Two algorithms have been proposed;the first provides an optimal solution for preemptive scheduling. This solution is then used in the second algorithm to provide an approximate solution for non-preemptive scheduling. Numerical evaluations demonstrate that the proposed algorithm achieves a close-to-optimal performance compared to exact solution obtained by CPLEX for small instances. For large instances, CPLEX is struggling to provide a feasible solution, whereas our approach takes less than a second to produce a solution for an instance of 10000 tasks.
This paper presents an efficient algorithm with performance guarantee (approximation algorithm) to solve task scheduling problem on hybrid platform. The underlying platform architecture in this work is composed by two...
详细信息
ISBN:
(纸本)9781538655559
This paper presents an efficient algorithm with performance guarantee (approximation algorithm) to solve task scheduling problem on hybrid platform. The underlying platform architecture in this work is composed by two types of resources CPU and GPU, often called hybrid parallel multi-core platforms. We consider here for each type of resource identical nodes with communications delays. We focus in finding a generic approach to schedule applications presented by DAG (Directed Acyclic Graph) that minimizes makespan by considering communication delay between processors and tasks. A 6-approximation scheduling algorithm is proposed and evaluated in comparison to exact solutions and to another method. We demonstrate that the proposed algorithm achieves a close-to-optimal performance. Finally, our algorithm has been experimented on a large number of instances. These tests assess the good practical behavior of the algorithms with respect to the state-of-the-art solutions whenever these exist.
In the edge-cloud environment, offloading technique decides the task to be executed either at the cloud or at the edge. Offloading can improve the quality of service and the efficiency of the system. In most previous ...
详细信息
ISBN:
(纸本)9783030590161;9783030590154
In the edge-cloud environment, offloading technique decides the task to be executed either at the cloud or at the edge. Offloading can improve the quality of service and the efficiency of the system. In most previous works on the offloading problem, the communication costs between tasks on both cloud side or the edge side are often ignored. We consider a general offloading model where the communication costs between any two tasks is non-zero and asymmetric. Moreover, due to the resource limitation on the edge side, we assume that the number of tasks executed on the edge side is bounded by a fixed constant k. This generalized offloading problem is NP-hard in minimizing the total cost with cardinality constraint. Based on semidefinite program, we give an approximation algorithm with the performance guarantee of 2/pi.
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.
This paper considers the correlation clustering problem with non-uniform hard constrained cluster sizes, which is a generalization of correlation clustering problem. In this problem, we are given a positive integer U-...
详细信息
ISBN:
(数字)9783030271954
ISBN:
(纸本)9783030271954;9783030271947
This paper considers the correlation clustering problem with non-uniform hard constrained cluster sizes, which is a generalization of correlation clustering problem. In this problem, we are given a positive integer U-upsilon for each vertex upsilon, and require vertical bar C vertical bar = min(upsilon is an element of C) U-upsilon for any cluster C. We provide a (2, 4)-bicriteria approximation algorithm for this problem. Namely, the solution returned by the algorithm has the cost that is at most 4 times the optimum, and for each cluster C in the solution, we have vertical bar C vertical bar <= 2min(upsilon is an element of C) U-upsilon.
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.
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.
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.
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.
暂无评论