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

The second International Conference of Electrical and Electronics Engineering(ICEEE 2011)

作者： Shi Lei-yu Peng Jing Wang Yong School of Electronic Science and Engineering National University of Defense Technology

A new mathematical problem, namely searching a connected dominating set(CDS) with the minimum total edge weight in an edge-weighted graph which can provide a better mathematical model for wireless networks, has been brought forward from the design of wireless networksTo solve this problem, an approximation algorithm with polynomial-time complexity is proposed in this paperThe simulation results demonstrate the effectiveness of the proposed algorithm, and the results also show that the approximation ratio of the proposed algorithm is up to 0.7.

关键词： connected dominating set edge weighted graphs approximation algorithm wireless networks

来源：评论

学校读者我要写书评

暂无评论

Preemptive scheduling with job-dependent setup times 99

Preemptive scheduling with job-dependent setup times

引用

Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms

作者： Petra Schuurman Gerhard J. Woeginger Department of Mathematics and Computing Science Eindhoven University of Technology P.O. Box 513 5600 MB Eindhoven The Netherlands Institut für Mathematik TU Graz Steyrergwe 30 A-8010 Graz Austria

来源：评论

学校读者我要写书评

暂无评论

Cost Effective Mobile and Static Road Side Unit Deployment for Vehicular Adhoc Networks

Cost Effective Mobile and Static Road Side Unit Deployment f...

引用

International Conference on Computing, Networking and Communications

作者： Donghyun Kim Yesenia Velasco Zishen Yang Wei Wang Rasheed Hussain R. N. Uma Department of Mathematics and Physics North Carolina Central University School of Math. and Statistics Xi'an Jiaotong Univ. Department of Computer Science Innopolis University

ISBN: (纸本)9781467385800

This paper investigates a new strategy to best deploy road side units so that their spatio-temporal coverage is maximized under a limited budget. For the first time in the literature, we consider three different RSU deployment strategies in a single framework, on static locations, public mobile transportation, and fully controllable vehicles. We first introduce a new strategy to abstract a map of city area into a grid graph. Then, we formulate the problem as a new optimization problem and show its NP-hardness. To solve this problem, we transform this problem into another optimization problem and propose a new polynomial running time approximation algorithm and show its performance ratio is at least the half of the best possible ratio.

关键词： Vehicular ad-hoc networks Road side unit deployment approximation algorithm Graph theory Optimization

来源：评论

学校读者我要写书评

暂无评论

Python-based Optimization Model and algorithm for Rescue Routes During Gas Leak Emergencies

Python-based Optimization Model and Algorithm for Rescue Rou...

引用

第三十二届中国控制会议

作者： Wen-mei GAI Yun-feng DENG Jing LI Yan DU School of Civil and Environmental Engineering University of Science and Technology Beijing Chinese Academy of Governance Institute of Public Safety China Academy of science and Technology School of Civil and Environmental Engineering University of Science and Technology Beijing

ISBN: (纸本)9781479900305

Based on the theories and methods of operations research,a mathematical model for the short est rescue route during gas leak emergencies in high-sulfur oil and gas fields is built in this pap er,which contains two weights of rescue rout e optimization,and serves the bi-objective optimization *** approximate search algorithm with two optimization objectives is proposed for the model based on heuristic algorithm,which could find out the shortest escape route from the double-weight escape route network by construct ing anxiliary *** the study case of the gas leak emergency rescue system of the Puguang gas field in Sichnan,the algorithm procedures are introduced,the convergence rate of the algorithm are analyzed,and the time complexity and the strengths of the algorithm are *** this algorithm,decision makers can find out the optimum rescue route on the distribution sketch map of the Puguang gas field,thus realizing the two optimizing targets,and providing strong technical support for gas leak rescue in the gas field.

关键词： Gas leak bi-objective optimization relief route approximation algorithm mathematical model Python major accidents emergency rescue

来源：评论

学校读者我要写书评

暂无评论

A New Bound for the Path Cover Problem

A New Bound for the Path Cover Problem

引用

2014全国理论计算机科学学术年会

作者： Xingfu Li Daming Zhu School of Computer Science and Technology Shandong UniversityJinanShandong 250100China

We consider the path cover problem which is to find a set of vertex-disjoint paths for a simple undirectedgraph with maximum number of edges to cover all vertices of this *** path cover problem isNP-hard because the well known Hamilton path problem is NP complete and the Hamilton path problemis a special case of the path cover *** this paper we present a new upper bound for the size of asolution of the path cover problem We believe that the upper bound is useful for our future *** application,we devise a 7-10approximation algorithm whose time complexity is O(|V‖E|1.5log(|V|))where |V| is the number of vertices and |E| is the number of edges of a *** that the bestapproximation ratio is 6-7 which is achieved by Berman et al[20].However,their algorithm has timecomplexity O(|V|9) which is much slower than ours.

关键词： approximation algorithm upper bound path cover

来源：评论

学校读者我要写书评

暂无评论

HEURISTICS FOR THE TRANSPOSITION DISTANCE PROBLEM

引用

JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY 2013年第5期11卷 1350013-1350013页

作者： Dias, Ulisses Dias, Zanoni Univ Estadual Campinas Inst Comp BR-13083852 Campinas SP Brazil

Transpositions are large-scale mutational events that occur when a block of genes moves from a region of a chromosome to another region within the same chromosome. The transposition distance problem is the minimum number of transpositions required to transform one genome into another. Recently, Bulteau et al. [Bulteau L, Fertin G, Rusu U, Automata, Languages and Programming, Vol. 6755 of Lecture Notes in Computer Science, pp. 654-665, Springer Berlin, Heidelberg, 2011] proved that finding the transposition distance is a NP-Hard problem. Some approximation algorithm for this problem have been presented to date [Bafna V, Pevzner PA, SIAM J Discr Math 11(2): 224-240, 1998;Elias I, Hartman T, IEEE/ACM Trans Comput Biol Bioinform 3(4): 369-379, 2006;Mira CVG, Dias Z, Santos HP, Pinto GA, Walter ME, Proc 3rd Brazilian Symp Bioinformatics (BSB'2008), pp. 115-126, Santo Andre, Brazil, 2008;Walter MEMT, Dias Z, Meidanis J, Proc String Processing and Information Retrieval (SPIRE'2000), pp. 199-208, Coruna, Spain, 2000]. Here we focus on developing heuristics to provide an improved approximated solution. Our approach outperforms other algorithms on small sized permutations. We also show that our algorithm keeps the good performance on longer permutations.

关键词： Genome rearrangement sorting by transposition approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Link Scheduling in Wireless Cooperative Communication Networks

Link Scheduling in Wireless Cooperative Communication Networ...

引用

IEEE International Conference on Mobile Ad Hoc and Sensor Systems

作者： Chenxi Qiu Haiying Shen Department of Electrical and Computer Engineering Clemson University

ISBN: (纸本)9781467391023

In this paper, we study the link scheduling problem in wireless cooperative communication networks, in which receivers are allowed to combine copies of a message from different senders to combat fading. We formulate a problem called cooperative link scheduling problem (CLS), which aims to find a schedule of links that uses the minimum number of time slots to inform all the receivers. As a solution, we propose an algorithm for CLS with g(Κ) approximation ratio, where g(Κ) is so called diversity of key links. Simulation results indicate that our cooperative link scheduling approaches outperform non-cooperative ones.

关键词： Cooperative communication Link scheduling approximation algorithm cooperative communication approximation algorithms networks(communications) Receivers wireless

来源：评论

学校读者我要写书评

暂无评论

Complex-Demand Knapsack Problems and Incentives in AC Power Systems 13

Complex-Demand Knapsack Problems and Incentives in AC Power ...

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Lan Yu Chi-Kin Chau Nanyang Technological University Singapore Singapore Masdar Institute of Science and Technology Abu Dhabi Uae

ISBN: (纸本)9781450319935

We consider AC electrical systems where each electrical device has a power demand expressed as a complex number, and there is a limit on the magnitude of total power supply. Motivated by this scenario, we introduce the complex-demand knapsack problem (C-KP), a new variation of the traditional knapsack problem, where each item is associated with a demand as a complex number, rather than a real number often interpreted as weight or size of the item. While keeping the same goal as to maximize the sum of values of the selected items, we put the capacity limit on the magnitude of the sum of satisfied demands. For C-KP, we prove its inapproximability by FPTAS (unless P = NP), as well as presenting a (1/2 - ε)-approximation algorithm. Furthermore, we investigate the selfish multi-agent setting where each agent is in charge of one item, and an agent may misreport the demand and value of his item for his own interest. We show a simple way to adapt our approximation algorithm to be monotone, which is sufficient for the existence of incentive compatible payments such that no agent has an incentive to misreport. Our results shed insight on the design of multi-agent systems for smart grid.

关键词： Knapsack problem approximation algorithm FPTAS Incentive compatibility Truthfulness AC electrical system Smart grid

来源：评论

学校读者我要写书评

暂无评论

An O(n³) algorithm for sorting signed genomes by reversals, transpositions, transreversals and block-interchanges

引用

JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY 2016年第1期14卷 1640002-1640002页

作者： Yu, Shuzhi Hao, Fanchang Leong, Hon Wai Natl Univ Singapore Dept Comp Sci 13 Comp Dr Singapore 117417 Singapore Shandong Univ Polit Sci & Law Sch Informat Jinan 250014 Shandong Peoples R China Shandong Univ Polit Sci & Law Key Lab Evidence Identifying Univ Shandong Jinan 250014 Shandong Peoples R China

We consider the problem of sorting signed permutations by reversals, transpositions, transreversals, and block-interchanges. The problem arises in the study of species evolution via large-scale genome rearrangement operations. Recently, Hao et al. gave a 2-approximation scheme called genome sorting by bridges (GSB) for solving this problem. Their result extended and unified the results of (i) He and Chen - a 2-approximation algorithm allowing reversals, transpositions, and block-interchanges (by also allowing transversals) and (ii) Hartman and Sharan - a 1.5-approximation algorithm allowing reversals, transpositions, and transversals (by also allowing block-interchanges). The GSB result is based on introduction of three bridge structures in the breakpoint graph, the L-bridge, T-bridge, and X-bridge that models good-reversal, transposition/transreversal, and block-interchange, respectively. However, the paper by Hao et al. focused on proving the 2-approximation GSB scheme and only mention a straightforward O(n(6)) algorithm. In this paper, we give an O(n(3)) algorithm for implementing the GSB scheme. The key idea behind our faster GSB algorithm is to represent cycles in the breakpoint graph by their canonical sequences, which greatly simplifies the search for these bridge structures. We also give some comparison results (running time and computed distances) against the original GSB implementation.

关键词： algorithm genome rearrangement genome sorting approximation algorithm reversal transreversal transposition block-interchange

来源：评论

学校读者我要写书评

暂无评论

Clustering for Metric and Nonmetric Distance Measures

引用

ACM TRANSACTIONS ON algorithmS 2010年第4期6卷 1–26页

作者： Ackermann, Marcel R. Bloemer, Johannes Sohler, Christian Univ Paderborn Dept Comp Sci D-33095 Paderborn Germany Tech Univ Dept Comp Sci D-44221 Dortmund Germany

We study a generalization of the k-median problem with respect to an arbitrary dissimilarity measure D. Given a finite set P of size n, our goal is to find a set C of size k such that the sum of errors D(P, C) = Sigma(p is an element of P) min(c is an element of C) {D(p, c)} is minimized. The main result in this article can be stated as follows: There exists a (1 + epsilon)-approximation algorithm for the k-median problem with respect to D, if the I-median problem can be approximated within a factor of (1 + epsilon) by taking a random sample of constant size and solving the I-median problem on the sample exactly. This algorithm requires time n2(O(mklog(mk/epsilon))), where m is a constant that depends only on epsilon and D. Using this characterization, we obtain the first linear time (1 + epsilon)-approximation algorithms for the k-median problem in an arbitrary metric space with bounded doubling dimension, for the Kullback-Leibler divergence (relative entropy), for the Itakura-Saito divergence, for Mahalanobis distances, and for some special cases of Bregman divergences. Moreover, we obtain previously known results for the Euclidean k-median problem and the Euclidean k-means problem in a simplified manner. Our results are based on a new analysis of an algorithm of Kumar et al. [2004].

关键词： approximation algorithm Bregman divergences Itakura-Saito divergence k-means clustering k-median clustering Kullback-Leibler divergence Mahalanobis distance random sampling

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：