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

On-Line Scheduling for Jobs with Arbitrary Release Times on Parallel Related Uniform Machines

Intelligent Information Management 2016年第4期8卷 98-102页

作者： Xiayan Cheng Rongheng Li Yunxia Zhou Department of Mathematics Hunan First Normal University Changsha China Department of Mathematics Key Laboratory of High Performance Computing and Stochastic Information Processing Hunan Normal University Changsha China Department of Computer Hunan Normal University Changsha China

A parallel related uniform machine system consists of m machines with different processing speeds. The speed of any machine is independent on jobs. In this paper, we consider online scheduling for jobs with arbitrary release times on the parallel uniform machine system. The jobs appear over list in terms of order. An order includes the processing size and releasing time of a job. For this model, an algorithm with competitive ratio of 12 is addressed in this paper.

关键词： Online Scheduling Uniform Machine Competitive Ratio approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Explaining a Weighted DAG with Few Paths for Solving Genome-Guided Multi-Assembly

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2015年第6期12卷 1345-1354页

作者： Tomescu, Alexandru I. Gagie, Travis Popa, Alexandru Rizzi, Romeo Kuosmanen, Anna Makinen, Veli Univ Helsinki Helsinki Inst Informat Technol Dept Comp Sci FIN-00014 Helsinki Finland Nazarbayev Univ Sch Sci & Technol Astana Kazakhstan Univ Verona Dept Comp Sci I-37100 Verona Italy

RNA-Seq technology offers new high-throughput ways for transcript identification and quantification based on short reads, and has recently attracted great interest. This is achieved by constructing a weighted DAG whose vertices stand for exons, and whose arcs stand for split alignments of the RNA-Seq reads to the exons. The task consists of finding a number of paths, together with their expression levels, which optimally explain the weights of the graph under various fitting functions, such as least sum of squared residuals. In (Tomescu et al. BMC Bioinformatics, 2013) we studied this genome-guided multi-assembly problem when the number of allowed solution paths was linear in the number of arcs. In this paper, we further refine this problem by asking for a bounded number k of solution paths, which is the setting of most practical interest. We formulate this problem in very broad terms, and show that for many choices of the fitting function it becomes NP-hard. Nevertheless, we identify a natural graph parameter of a DAG G, which we call arc-width and denote < G >, and give a dynamic programming algorithm running in time O < W-k >< G >(k)<< G > + k > n >, where n is the number of vertices and W is the maximum weight of G. This implies that the problem is fixed-parameter tractable (FPT) in the parameters W, < G >, and k. We also show that the arc-width of DAGs constructed from simulated and real RNA-Seq reads is small in practice. Finally, we study the approximability of this problem, and, in particular, give a fully polynomial-time approximation scheme (FPTAS) for the case when the fitting function penalizes the maximum ratio between the weights of the arcs and their predicted coverage.

关键词： RNA-sequencing transcript prediction splicing graph NP-hardness dynamic programming fixed-parameter tractability digraph-width measure approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A New Upper Bound of Hausdorff Measure of the Product of the Cantor Set with Itself

A New Upper Bound of Hausdorff Measure of the Product of the...

引用

The Eighth International Conference on Information and Management Sciences

作者： Juan Deng Department of Mathematical Sciences,Tsinghua University,Beijing 100084,China

Let E be the product of the Middle Third Cantor set with itself,we prove that the minimal value of the inverse density of a special class of balls can be attained,denoted by h（E）,which gives an upper bound of the Hausdorff measure of E in the nature of *** also introduce an approximation method for calculating the exact value of h（E）.And then we get a new upper bound of the Hausdorff measure of E.

关键词： Hausdorff measure approximation algorithm Inverse density Upper bound

来源：评论

学校读者我要写书评

暂无评论

Covert Networks: How Hard is It to Hide? 19

Covert Networks: How Hard is It to Hide?

引用

Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems

作者： Palash Dey Sourav Medya Indian Institute of Technology Kharagpur Kharagpur India University of California Santa Barbara Santa Barbara CA USA

ISBN: (纸本)9781450363099

Covert networks are social networks that often consist of harmful users. Social Network Analysis (SNA) has played an important role in reducing criminal activities (e.g., counter terrorism) via detecting the influential users in such networks. There are various popular measures to quantify how influential or central any vertex is in a network. As expected, strategic and influential miscreants in covert networks would try to hide herself and her partners (called \em leaders ) from being detected via these measures by introducing new edges. Waniek et al. show that the corresponding computational problem, called Hiding Leader, is NP Complete for the degree and closeness centrality measures. We study the popular core centrality measure and show that the problem is NP Complete even when the core centrality of every leader is only 3. On the contrary, we prove that the problem becomes polynomial time solvable for the degree centrality measure if the degree of every leader is bounded above by any constant. We then focus on the optimization version of the problem and show that the Hiding Leader problem admits a 2 factor approximation algorithm for the degree centrality measure. We complement it by proving that one cannot hope to have any (2-epsilon) factor approximation algorithm for any constant $epsilon>0$ unless there is a epsilon/2 factor polynomial time algorithm for the Densest k-Subgraph problem which would be considered a significant breakthrough. We empirically establish that our 2 factor approximation algorithm frequently finds out a near optimal solution. On the contrary, for the core centrality measure, we show that the Hiding Leader problem does not admit any (1-alpha) ln n factor approximation algorithm for any constant alpha in (0,1) unless P=NP even when the core centrality of every leader is only 3. Hence, our work shows that, although classical complexity theoretic framework fails to shed any light on relative difficulty of Hiding Leader for different centr

关键词： network design centrality hiding in networks algorithms social influence core social network analysis covert network approximation algorithm densest subgraph

来源：评论

学校读者我要写书评

暂无评论

Towards Scheduling to Maximize Weighted Delivered Data in Maritime CPSs

Towards Scheduling to Maximize Weighted Delivered Data in Ma...

引用

第28届中国控制与决策会议

作者： Tingting Yang Hailong Feng Chengming Yang Zhonghua Sun Ruilong Deng Navigation College Dalian Maritime University School of Naval Architecture Ocean & Civil EngineeringShanghai Jiao Tong University Department of Electrical and Computer Engineering University of Alberta

ISBN: (纸本)9781467397155

This paper develops offline schedule and online schedule algorithms for maritime Cyber Physical Systems(CPSs),to address the issue of delivered surveillance videos that vessels generate from the origin port to destination *** the sailing,the surveillance videos could be uploaded by the infostations *** videos are splited into packets,which could be delivered successfully before their *** act the issue into a mathematic job-machine *** each job is revealed at a release time,a deadline,a processing time,and a *** maximize the weight of jobs,we propose three algorithms,an offline algorithm,an online ADMISSION algorithm with no bounded processing times,as well as Exponential-Capacity algorithm with bounded processing *** approximation ratio and competitive ratios of them are inducted *** results verified the performance of them.

关键词： Maritime wideband communication time-capacity mapping job-machine scheduling approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Bin-packing Model Based on File Preservation Problem

A Bin-packing Model Based on File Preservation Problem

引用

2010 International Conference of Informationa Science and Management Engineering(2010年信息科学与管理工程国际学术会议 ISME 2010)

作者： Qingshan ZHANG Jida HUANG Huazhen CHANG Shaobo LI School of Mines China University of Mining & Technology Xuzhou China

This paper established a bin-packing model according to file preservation problems, which is a NP hard problem, the paper use FF and FFD algorithm to obtain the corresponding results, by comparing the results, with the bound theory of the optimal solution to prove the obtained solution from FFD algorithm shall be the optimal solution. This paper further analysis of a large-scale one-dimensional packing problem solving method, in order to overcome the disadvantage of classical algorithm in space and time, and for searching a good convergence, with strong local search and to avoid falling into local optimal solution algorithm, this paper give the processes of simulated annealing algorithm.

关键词： bin-packing model NP Hard File Preservation approximation algorithm SA

来源：评论

学校读者我要写书评

暂无评论

Context-aware Crowd-sensing in Opportunistic Mobile Social Networks

Context-aware Crowd-sensing in Opportunistic Mobile Social N...

引用

IEEE International Conference on Mobile Ad Hoc and Sensor Systems

作者： Phuong Nguyen Klara Nahrstedt Department of Computer Science University of Illinois at Urbana-Champaign

ISBN: (纸本)9781467391023

In this paper, we study the physical crowd-sensing problem and draw the connection to the vertex cover problem in graph theory. Since finding the optimal solution for minimum vertex cover problem is NP-complete and the well-known approximation algorithms do not perform well with under crowd-sensing scenario, we propose the notions of node observability and coverage utility score and design a new context-aware approximation algorithm to find vertex cover that is tailored for crowd-sensing task. In addition, we design human-centric bootstrapping strategies to make initial assignment of sensing devices in the physical crowd based on social information about the users (e.g., interests, friendship). Our experiments on real-world data traces show that the proposed approach significantly outperforms the baseline approximation algorithms in terms of sensing coverage.

关键词： Crowd-sensing Opportunistic mobile ad hoc net- work approximation algorithm approximation algorithms Context awareness Device Sensor corners vertex head Nondeterministic polynomial-time hard Graph theory information user optimal solution Social Capital Social Networks

来源：评论

学校读者我要写书评

暂无评论

The Single-machine Parallel-batching Scheduling Problem with Family Jobs to Minimize Makespan

The Single-machine Parallel-batching Scheduling Problem with...

引用

2010 Second International Conference on Communication Systems, Networks and Applications (ICCSNA 2010)

作者： Meng Jintao,Lu Xiaoxu Zhengzhou Institute of Aeronautical Industry Management Zhengzhou 450015,China

In this paper we consider the single-machine parallel-batching scheduling problem with family jobs under on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job until its *** objective is to minimize the maximum completion time of the jobs（makespan）.We deal with the special variant of the problem:the unbounded model in which the machine can handle infinite number of jobs simultaneously,the jobs only have two distinct arrival times and come from m *** provide an on-line algorithm with a worst case ratio of 2-α/2,where α = 5-1]/2.

关键词： single machine scheduling worst-case analysis approximation algorithm on-line Parallelbatching Scheduling

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithm for scheduling parallel applications on hybrid multicore machines with communications delays and energy constraint

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2020年第15期32卷 e5573-e5573页

作者： Ait Aba, Massinissa Zaourar, Lilia Munier, Alix CEA LIST Comp & Design Environm Lab F-91191 Gif Sur Yvette France UPMC LIP6 Paris France Paris Saclay Campus NanoINNOV Bat 862 PC172 F-91191 Gif Sur Yvette France

This paper presents an efficient algorithm with performance guarantee to solve task scheduling problem on hybrid platforms with energy constraint and communication delays. The underlying platform architecture in this work is composed of two types of resources, CPU and GPU, often called hybrid parallel multicore platforms. We focus on finding a generic approach to schedule applications presented by Directed Acyclic Graph (DAG), which minimizes the makespan by considering communication delays and respecting an energy constraint. A two-phase algorithm is proposed with a performance guarantee of 6 compared with the optimal solution;the first phase consists in solving the assignment problem to find the type of processor assigned to execute the tasks (CPU or GPU) using a linear program. In the second phase, we calculate the start execution time of each task to generate a feasible schedule. Finally, we test our algorithm on a large number of instances. These tests demonstrate that the proposed algorithm achieves a close-to-optimal performance.

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

来源：评论

学校读者我要写书评

暂无评论

Determining Storage Locations and Capacities for Emergency Response

Determining Storage Locations and Capacities for Emergency R...

引用

第九届运筹学及其应用国际研讨会

作者： Jianming Zhu Degang Liu Jun Huang Jiye Han College of Engineering Graduate University of Chinese Academy of Sciences Institute of Applied Mathematics Academy of Mathematics and Systems Science CAS

In this paper, we consider the problem of emergency response resource storage locations and capacities. Resources are important for disaster relief operations in coping with natural and manmade emergencies. In order to enhance the ability of response to disasters, different levels of reserve system need to be set up for holding relief resources. These emergency storages may have different capacities and construction costs. In this paper, we formulate a model to determine the storage locations and their capacities at minimum total construction cost. Then, an approximation algorithm is presented by introducing LP-rounding technique. Finally, the proofs of correctness and approximation ratio are shown.

关键词： Location Resource Reserve System LP-rounding approximation algorithm Emergency Response

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：