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

IEEE Global Communications Conference

作者： Tianyi Chen Hangguan Shan Xin Wang Department of Communication Science and Engineering Fudan University Department of Information Science and Electronic Engineering Zhejiang University

ISBN: (纸本)9781479913510

In this paper, we consider a cellular/infostation integrated network which supports on-demand data service delivery over a wireless link to users in a high-speed train. For the requests with different lifetimes and prices that they are willing to pay, we develop the optimal packet schedule that aims at earning the maximum revenue. To this end, we formulate the problem as an integer linear program (ILP) which is in general NP-hard. However, by exploring the special structure of the formulated ILP, we show that this problem can be turned into a P problem that admits efficient solvers. Specifically, we propose a novel Checker algorithm and prove that this algorithm is guaranteed to find the offline optimal schedule for the intended problem in polynomial time, when the number of total requests is proportional to the length of the total transmission time span. Based on the relevant insights, a class of efficient online Checker algorithms are then developed to approach the optimal schedule when a-priori knowledge of service demands and/or wireless channel capacities is not available in practical systems. It is shown that these online algorithms have a competitive ratio of 1/2, i.e., total revenue earned by them is at least half as much as the revenue earned by offline optimal schedule. Simulation results are provided to demonstrate the merit of the proposed algorithms.

关键词： On-demand services Packet schedule Wireless link Integer linear program algorithm analysis analysis of algorithm wireless high-speed train Integer linear programming Radio links data services packet schedule REVENUE algorithms checker

来源：评论

学校读者我要写书评

暂无评论

Mind the gap: A study of Tube tour

引用

COMPUTERS & OPERATIONS RESEARCH 2012年第11期39卷 2705-2714页

作者： Drozdowski, M. Kowalski, D. Mizgajski, J. Mokwa, D. Pawlak, G. Poznan Univ Tech Inst Comp Sci PL-60965 Poznan Poland

The problem considered in this paper can be expressed as a question: Is it possible to visit all Tube lines in a day? This is a new type of combinatorial optimization problem which generalizes classic problems like TSP, set cover. It has similarities with classic combinatorial optimization problems and ties with operations research applications. We call the graphs corresponding to the city railway systems subway graphs. Examples and properties of such graphs are described in the paper. We show that our problem is NP-hard. algorithms solving the problem are proposed and their performance is studied both analytically and experimentally on transportation networks of several big cities of the world. (C) 2012 Elsevier Ltd. All rights reserved.

关键词： Graph cycles Urban railway algorithm analysis Heuristics

来源：评论

学校读者我要写书评

暂无评论

A note on asynchronous multi-exponentiation algorithm using binary representation

引用

INFORMATION PROCESSING LETTERS 2012年第22期112卷 876-879页

作者： Sun, Da-Zhi Huai, Jin-Peng Li, Jian-Xin Tianjin Univ Sch Comp Sci & Technol Tianjin 300072 Peoples R China Beihang Univ Sch Comp Sci Beijing 100083 Peoples R China

A basic but expensive operation in implementations of several famous public-key crypto-systems is the computation of the multi-exponentiation in a certain finite multiplication group. In 2007, Yang et al. presented an interesting asynchronous multi-exponentiation algorithm called the SUt method, which uses the binary representations for the exponents. In this note, we analyze the computational efficiency of the SUt method by modeling the scanning process as a Markov chain. It shows that their computational efficiency result is incorrect. Moreover, we make a performance comparison among the published techniques and show that the performance of a modified sliding window method is better than that of the SUt method, when there are 4 or more additional registers. We hope that our research will be convenient to the development of the cryptographic devices. (C) 2012 Elsevier By. All rights reserved.

关键词： Cryptography Multi-exponentiation algorithm analysis Markov chain

来源：评论

学校读者我要写书评

暂无评论

Redesigning Viral Genomes

引用

COMPUTER 2012年第3期45卷 47-53页

作者： Skiena, Steven SUNY Stony Brook Stony Brook NY 11794 USA

The advent of low-cost, large-scale DNA synthesis, coupled with advanced algorithmic tools, opens the door to a host of exciting new biotechnology applications, including vaccines.

关键词： Vaccines DNA Genomics Encoding Biological information theory algorithm design and analysis Proteins Computational biology Biological processes algorithm analysis computational biology biology and genetics

来源：评论

学校读者我要写书评

暂无评论

An Improved Complex Network Community Detection algorithm Based on K-Means

An Improved Complex Network Community Detection Algorithm Ba...

引用

Conference on the Future Computer and Control Systems

作者： Wang, Yuqin Jilin Business & Technol Coll Dept Informat Engn Changchun 130062 Peoples R China

ISBN: (纸本)9783642293894

In order to find community structure that exists in complex network structure, this paper introduced K-means approach to the complex network community structure of the research. This paper studies the complex network of community structure detection algorithm, through the existing algorithm learn and study, proposed an improved algorithm based on K-means. Not know the premise of community structure for the complex networks division, the algorithm is simple and easy to understand, and the algorithm was used in karate network, through experimental verification, experimental results show that the algorithm is effective.

关键词： complex networks community structure k-means detection algorithm algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

AVERAGE-CASE analysis OF PERFECT SORTING BY REVERSALS

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2011年第3期3卷 369-392页

作者： Bouvel, Mathilde Chauve, Cedric Mishna, Marni Rossin, Dominique Univ Bordeaux 1 CNRS LaBRI Bordeaux France Simon Fraser Univ Dept Math Burnaby BC V5A 1S6 Canada Ecole Polytech CNRS LIX Palaiseau France

Perfect sorting by reversals, a problem originating in computational genomics, is the process of sorting a signed permutation to either the identity or to the reversed identity permutation, by a sequence of reversals that do not break any common interval. Berard et al. (2007) make use of strong interval trees to describe an algorithm for sorting signed permutations by reversals. Combinatorial properties of this family of trees are essential to the algorithm analysis. Here, we use the expected value of certain tree parameters to prove that the average run-time of the algorithm is at worst, polynomial, and additionally, for sufficiently long permutations, the sorting algorithm runs in polynomial time with probability one. Furthermore, our analysis of the subclass of commuting scenarios yields precise results on the average length of a reversal, and the average number of reversals.

关键词： algorithm analysis genome rearrangements tree parameters simple permutations

来源：评论

学校读者我要写书评

暂无评论

On Adaptive Random Testing Through Iterative Partitioning

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2011年第4期27卷 1449-1472页

作者： Chen, Tsong Yueh Huang, De Hao Zhou, Zhi Quan Univ Wollongong Sch Comp Sci & Software Engn Wollongong NSW 2522 Australia Swinburne Univ Technol Fac Informat & Commun Technol Hawthorn Vic 3122 Australia Swinburne Univ Technol Informat Technol Serv Hawthorn Vic 3122 Australia

Random Testing (RT) is an important and fundamental approach to testing computer software. Adaptive Random Testing (ART) has been proposed to improve the fault-detection capability of RT. ART employs the location information of successful test cases (those that have been executed but not revealed a failure) to enforce an even spread of random test cases across the input domain. Distance-based ART (D-ART) and Restriction-based ART (R-ART) are the first two ART methods, which have considerably improved the fault-detection capability of RT. Both these methods, however, require additional computation to ensure the generation of evenly spread test cases. To reduce the overhead in test case generation, we present in this paper a new ART method using the notion of iterative partitioning. The input domain is divided into equally sized cells by a grid. The grid cells are categorized into three different groups according to their relative locations to successful test cases. In this way, our method can easily identify those grid cells that are far apart from all successful test cases for test case generation. Our method significantly reduces the time complexity, while keeping the high fault-detection capability.

关键词： software testing random testing adaptive random testing simulation algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

On Scheduling in Map-Reduce and Flow-Shops 11

On Scheduling in Map-Reduce and Flow-Shops

引用

23rd Annual Symposium on Parallelism in algorithms and Architectures

作者： Moseley, Benjamin Dasgupta, Anirban Kumar, Ravi Sarlos, Tamas Univ Illinois Urbana IL 61801 USA

ISBN: (纸本)9781450307437

The map-reduce paradigm is now standard in industry and academia for processing large-scale data. In this work, we formalize job scheduling in map-reduce as a novel generalization of the two-stage classical flexible flow shop (FFS) problem: instead of a single task at each stage, a job now consists of a set of tasks per stage. For this generalization, we consider the problem of minimizing the total flowtime and give an efficient 12-approximation in the offline setting and an online (1 + epsilon)-speed O(1/epsilon(2))-competitive algorithm. Motivated by map-reduce, we revisit the two-stage flow shop problem, where we give a dynamic program for minimizing the total flowtime when all jobs arrive at the same time. If there are fixed number of job-types the dynamic program yields a PTAS;it is also a QPTAS when the processing times of jobs are polynomially bounded. This gives the first improvement in approximation of flowtime for the two-stage flow shop problem since the trivial 2-approximation algorithm of Gonzalez and Sahni [29] in 1978, and the first known approximation for the FFS problem. We then consider the generalization of the two-stage FFS problem to the unrelated machines case, where we give an offline 6-approximation and an online (1 + epsilon)-speed O(1/epsilon(4))-competitive algorithm.

关键词： Scheduling and resource allocation algorithm analysis Approximation algorithms On-line problems Map-reduce Flow-shops

来源：评论

学校读者我要写书评

暂无评论

Formal methods of algorithm analysis for decreasing RTL-verification complexity

Formal methods of algorithm analysis for decreasing RTL-veri...

引用

9th International Conference on the Experience of Designing and Application of CAD Systems in Microelectronics

作者： Lyalin, Alexander Moscow Inst Phis & Technol Dept Comp Sci Dolgoprudnyi 141700 Russia

ISBN: (纸本)9789665335870

The basis for RTL-development and verification system is functional device specification. More often bugs are "produced" when informal transitions from this specification to RTL and "verification environment"- code are taken by design and validation engineers. In contrast to this traditional approach the formal transition method to RTL-code and verification environment development is introduced, based on device C-model Control-DataFlow Graph (CDFG) analysis. As an example, in this article the introduced formal approach is applied for JPEG2000 model for getting RTL SystemC-code.

关键词： SPARK SystemC algorithm analysis CDFG functional verification formal transition JPEG2000

来源：评论

学校读者我要写书评

暂无评论

A model to simplify 2D triangle meshes with irregular shapes

引用

APPLIED MATHEMATICS AND COMPUTATION 2010年第10期216卷 2937-2946页

作者： Tortosa, L. Vicent, J. F. Zamora, A. Univ Alicante Dept Ciencia Computac & Inteligencia Artificial E-03080 Alicante Spain

We present a 2D triangle mesh simplification model which is able to produce high quality approximations of any original planar mesh, regardless of the shape of the original mesh. This method consists of two phases: a self-organizing algorithm and a triangulation algorithm. The self-organizing algorithm is an unsupervised incremental clustering algorithm which provides us a set of nodes representing the best approximation of the original mesh. The triangulation algorithm reconstructs the simplified mesh from the planar points obtained by the self-organizing training process. Some examples are detailed with the purpose of demonstrating the ability of the model to perform the task of simplifying an original mesh with irregular shape. (C) 2010 Elsevier Inc. All rights reserved.

关键词： algorithm analysis Mesh simplifications Artificial neural networks Triangulation GNG3D model Self-organizing systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：