检索结果-内蒙古大学图书馆

approximation algorithm FOR AN INFINITE-DIMENSIONAL OPERATOR EQUATION XL-BX=C

MATHEMATICS OF CONTROL SIGNALS AND SYSTEMS 1994年第1期7卷 76-93页

作者： NAMBU, T 1. Department of Applied Mathematics Faculty of Engineering Kobe University Nada 657 Kobe Japan

We study an infinite-dimensional operator equation XL - BX = C in a separable Hilbert space. The equation arises in the stabilization study of general linear parabolic systems, where the operators L, B, and C are coefficient operators describing a Feedback control system. The solution to the stabilization naturally leads to an approximation problem of the operator equation. In this paper we propose a concrete algorithm for the approximation with the prescribed convergence rate when the closed operator L is self-adjoint or more generally a spectral operator with compact resolvent.

关键词： INFINITE-DIMENSIONAL SYLVESTER EQUATION INVERSE PROBLEM approximation algorithm PARABOLIC FEEDBACK SYSTEMS

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for minimizing relay node placement in wireless sensor networks

引用

Science China(Information Sciences) 2010年第11期53卷 2332-2342页

作者： LU KeZhong1,2, CHEN GuoLiang1,2, FENG YuHong1,2, LIU Gang1,2 & MAO Rui1,2 1College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518060, China 2National High Performance Computing Center at Shenzhen, Shenzhen 518060, China 1. College of Computer Science and Software Engineering Shenzhen University Shenzhen 518060 China2. National High Performance Computing Center at Shenzhen Shenzhen 518060 China

To eliminate the routing load unbalance among sensor nodes, one approach is to deploy a small number of powerful relay nodes acting as routing nodes in wireless sensor networks, the major optimization objective of which is to minimize the number of relay nodes required. In this paper, we prove that the relay node placement problem in a bounded plane is a P problem, but its computational complexity in general case is quite great. From the geometric cover feature of the relay node placement problem, an O(n2 log n) time greedy approximation algorithm is proposed, where n is the number of sensor nodes. Particularly, at each stage of this algorithm's iterative process, we first select a critical node from uncovered sensor nodes, and then determine the location of relay node based on the principle of preferring to cover the sensor node closer to the critical node, so as to prevent the emergence of isolated node. Experiment results indicate that our proposed algorithm can generate a near optimum feasible relay node deployment in a very short time, and it outperforms existing algorithms in terms of both the size of relay node deployment and the execution time.

关键词： wireless sensor network relay node placement geometrical cover approximation algorithm greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm using: neighbors, history and errors (NHE)

Approximation Algorithm using: neighbors, history and errors...

引用

3rd International Conference on Digital Information Management

作者： Safar, Maytham Al-Masri, Nisreen Kuwait Univ Dept Comp Engn Safat 13060 Kuwait

ISBN: (纸本)9781424429165

In this work we design an approximation algorithm using neighbors, history and errors (NHE algorithm) to analyze and approximate the behavior of sensors readings after it fails. NHE algorithm computes and associates a specific equation to each sensor that has factors computed using neighbors, history data and the approximation error as a feedback factor. In some cases, it is difficult to reach each sensor to read its value either due to a connection problem or the sensor itself is down and not reachable. In those cases, NHE algorithm uses the evaluated equations to approximate this down sensor reading. The results of the experiments using this algorithm prove that it is powerful but with specific constraints.

关键词： Sensors grid sensors estimator algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for Min-Max Correlation Clustering Problem with Outliers 15th

Approximation Algorithm for Min-Max Correlation Clustering P...

引用

15th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Ji, Sai Li, Min Liang, Mei Zhang, Zhenning Chinese Acad Sci Acad Math & Syst Sci Beijing 100190 Peoples R China Shandong Normal Univ Sch Math & Stat Jinan 250358 Peoples R China Beijing Univ Technol Coll Stat & Data Sci Beijing 100124 Peoples R China Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China

ISBN: (纸本)9783030926816;9783030926809

In this paper, we investigate the min-max correlation clustering problem with outliers, which is a combination of the min-max correlation clustering problem with the robust clustering. We first prove that the problem is NP-hard to obtain any finite approximation algorithm. Then we design an approximation algorithm based on LP-rounding technique and receive a bi-criteria guarantee.

关键词： Min-max clustering Correlation clustering Outliers approximation algorithm LP-rounding

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for base station placement in wireless sensor networks

Approximation algorithm for base station placement in wirele...

引用

4th Annual IEEE-Communications-Society Conference on Sensor, Mesh and AD HOC Communications and Networks

作者： Shi, Yi Hou, Y. Thomas Virginia Tech Bradley Dept Elect & Comp Engn Blacksburg VA 24061 USA

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.

关键词： theory approximation algorithm base station placement network lifetime sensor network

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for scheduling applications on hybrid multi-core machines with communications delays 32

Approximation algorithm for scheduling applications on hybri...

引用

32nd IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Aba, Massinissa Ait Zaourar, Lilia Munier-Kordon, Alix CEA LIST Comp & Design Environm Lab F-91191 Gif Sur Yvette France LIP6 UPMC 4 Pl Jussieu F-75005 Paris France

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.

关键词： DAG applications makespan hybrid CPU GPU approximation algorithm scheduling

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for Scheduling a Chain of Tasks on Heterogeneous Systems 1

引用

23rd International Conference on Parallel and Distributed Computing (Euro-Par)

作者： Aba, Massinissa Ait Zaourar, Lilia Munier, Alix CEA LIST Comp & Design Environm Lab F-91191 Gif Sur Yvette France UPMC LIP6 4 Pl Jussieu F-75005 Paris France

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.

关键词： Linear chain of tasks Makespan Energy approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for the Offloading Problem in Edge Computing 15th

Approximation Algorithm for the Offloading Problem in Edge C...

引用

15th International Conference on Wireless algorithms, Systems, and Applications (WASA)

作者： Han, Xinxin Gao, Guichen Ning, Li Wang, Yang Zhang, Yong Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen Peoples R China Univ Chinese Acad Sci Beijing Peoples R China

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.

关键词： Offloading Edge computing approximation algorithm Semidefinite program

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for the Correlation Clustering Problem with Non-uniform Hard Constrained Cluster Sizes 1

引用

13th International Conference on algorithmic Aspects in Information and Management (AAIM)

作者： Ji, Sai Xu, Dachuan Li, Min Wang, Yishui Beijing Univ Technol Dept Operat Res & Sci Comp Beijing 100124 Peoples R China Shandong Normal Univ Sch Math & Stat Jinan Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China

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.

关键词： Correlation clustering Non-uniform hard constrained cluster sizes approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm of the RNA Pseudoknotted Structure Prediction Baesed on MFE

Approximation Algorithm of the RNA Pseudoknotted Structure P...

引用

IEEE International Conference on Information and Automation (ICIA)

作者： Liu, Zhendong Li, Yuejun Zhang, Peng Yang, Zhaohui Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China Shandong Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China

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.

关键词： RNA Pseudoknotted structure Minimum free energy Stacking pairs approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：