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

EFFICIENT CSL MODEL CHECKING USING STRATIFICATION

LOGICAL METHODS IN COMPUTER SCIENCE 2012年第2期8卷

作者： Zhang, Lijun Jansen, David N. Nielson, Flemming Hermanns, Holger Tech Univ Denmark DTU Informat Lyngby Denmark Radboud Univ Nijmegen NL-6525 ED Nijmegen Netherlands Univ Saarland D-6600 Saarbrucken Germany

For continuous-time Markov chains, the model-checking problem with respect to continuous-time stochastic logic (CSL) has been introduced and shown to be decidable by Aziz, Sanwal, Singhal and Brayton in 1996 [ 1, 2]. Their proof can be turned into an approximation algorithm with worse than exponential complexity. In 2000, Baier, Haverkort, Hermanns and Katoen [ 4, 5] presented an efficient polynomial-time approximation algorithm for the sublogic in which only binary until is allowed. In this paper, we propose such an efficient polynomial-time approximation algorithm for full CSL. The key to our method is the notion of stratified CTMCs with respect to the CSL property to be checked. On a stratified CTMC, the probability to satisfy a CSL path formula can be approximated by a transient analysis in polynomial time (using uniformization). We present a measure-preserving, linear-time and - space transformation of any CTMC into an equivalent, stratified one. This makes the present work the centerpiece of a broadly applicable full CSL model checker. Recently, the decision algorithm by Aziz et al. was shown to work only for stratified CTMCs. As an additional contribution, our measure-preserving transformation can be used to ensure the decidability for general CTMCs.

关键词： continuous-time Markov chains continuous stochastic logic model checking approximation algorithm stratification

来源：评论

学校读者我要写书评

暂无评论

Minimizing total job completion time in MapReduce scheduling

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2021年 158卷 107387-107387页

作者： Dong, Jianming Goebel, Randy Hu, Jueliang Lin, Guohui Su, Bing Zhejiang Sci Tech Univ Dept Math Hangzhou Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Xian Technol Univ Sch Econ & Management Xian Peoples R China

We follow up an earlier studied multiple-task parallel-machine scheduling model that captures the core challenges in MapReduce scheduling, with the optimization goal to minimize the total job completion time. The problem is a novel generalization of the classic two-stage flow-shop scheduling, in which we are given a set of jobs each is associated with multiple map tasks and multiple reduce tasks. All these tasks are non-preemptive to be processed on multiple parallel identical map machines and multiple parallel identical reduce machines, respectively, under the strict precedence constraints that, for each job, any reduce task cannot start before all its map tasks have been finished. We prove a new lower bound on the total job completion time, and based on which we present an O(nlogn + N + m(1) + m(2))-time (9-3/m(1))-approximation algorithm, where n and N are the number of jobs and the total number of tasks, respectively, m(1) and m(2) are the numbers of map and reduce machines, respectively, and they can even be part of the input. Our algorithm improves the previous best 12-approximation, and it reduces to the best approximation algorithms for several interesting or well studied special cases. We confirm through numerical experiments on 828, 100 instances that both our lower bound and our algorithm significantly outperform: the empirical mean improvement ratio of the new lower bound is as high as 37.75%, and the empirical mean approximation ratio of our algorithm is only 1.7582.

关键词： MapReduce scheduling Two-stage flow-shop Parallel identical machines Shortest processing time approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximizing spatial-temporal coverage in mobile crowd-sensing based on public transports with predictable trajectory

引用

INTERNATIONAL JOURNAL OF DISTRIBUTED SENSOR NETWORKS 2018年第8期14卷

作者： Wang, Chaowei Li, Chensheng Qin, Cai Wang, Weidong Li, Xiuhua Beijing Univ Posts & Telecommun Sch Elect Engn Beijing 100876 Peoples R China

Mobile crowd-sensing is a prospective paradigm especially for intelligent mobile terminals, which collects ubiquitous data efficiently in metropolis. The existing crowd-sensing schemes based on intelligent terminals mainly consider the current trajectory of the participants, and the quality highly depends on the spatial-temporal coverage which is easily weakened by the mobility of participants. Nowadays, public transports are widely used and affordable in many cities around the globe. Public transports embedded with substantial sensors act as participants in crowd-sensing, but different from the intelligent terminals, the trajectory of public transports is schedulable and predictable, which sheds an opportunity to achieve high-quality crowd-sensing. Therefore, based on the predictable trajectory of public transports, we design a novel system model and formulate the selection of public transports as an optimization problem to maximize the spatial-temporal coverage. After proving the public transport selection is non-deterministic polynomial-time hardness, an approximation algorithm is proposed and the coverage is close to 1. We evaluate the proposed algorithm with samples of real T-Drive trajectory data set. The results show that our algorithm achieves a near optimal coverage and outperforms existing algorithms.

关键词： Mobile crowd-sensing schedulable trajectory spatial-temporal coverage approximation algorithm performance guarantee

来源：评论

学校读者我要写书评

暂无评论

Extracting typical classes and a database schema from semistructured data

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2001年第1期E84D卷 100-112页

作者： Suzuki, N Sato, Y Hayase, M Okayama Prefectural Univ Fac Comp Sci & Syst Engn Soja 7191197 Japan

Semistructured data has no a-priori schema information, formation which causes some problems such as inefficient storage and query execution. To cope with such problems, extracting schema information from semistructured data has been all important issue. However, in most cases optimal schema information cannot be extracted efficiently, and few efficient approximation algorithms have been proposed. In this paper, we consider an approximation algorithm fur extracting "typical" classes from semistructured data. Intuitively, a class C is said to be typical if the structure of C is "similar" to those of "many" objects. We present the following results. First, we prove that the problem of deciding if a typical class can be extracted from given semistructured data is NP-complete. Second, we present an approximation algorithm for extracting typical classes from given semistructured data, and show a sufficient condition for the approximation algorithm tu run in polynomial time. Finally, by using extracted classes obtained by the approximation algorithm, we propose a polynomial-time algorithm for constructing a set R of classes such that R covers all the objects to form a database schema.

关键词： semistructured data class extraction approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Two competitive agents to minimize the weighted total late work and the total completion time

引用

APPLIED MATHEMATICS AND COMPUTATION 2021年 406卷 126286-126286页

作者： Zhang, Xingong Chongqing Normal Univ Coll Math Sci Chongqing 401331 Peoples R China

This paper studies deterministic constraint optimization problem with two competitive agents in which the following objective functions on a single machine: the total weighted late work and the total completion time. We show that the constraint optimization problem is the binary NP-hard by Knapsack problem reduction. Furthermore, we present a pseudo-polynomial time algorithm by early due date maximum not-late sequence, and an approximation Pareto curve by dynamic programming algorithm and two eliminated states, which time complexity of the two approximation algorithms are O(n(A)(2)n(B)Q Sigma (p(j)(A) + p(j)(B))) and O(n(4)/theta(2) log UBA log UBB), where p(j), theta are processing time of job J(j), a given positive constant, and UBx an upper bound of the objective function of agent x, x subset of {A, B}. Finally, we present a simple approximation algorithm by the earliest due date (EDD) rule, which jobs of agent B are assigned an dummy due date. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Two competitive agent Single-machine scheduling Total late work approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On Realistic Target Coverage by Autonomous Drones

引用

ACM TRANSACTIONS ON SENSOR NETWORKS 2019年第3期15卷 32-32页

作者： Saeed, Ahmed Abdelkader, Ahmed Khan, Mouhyemen Neishaboori, Azin Harras, Khaled A. Mohamed, Amr Georgia Inst Technol Atlanta GA 30332 USA Univ Maryland Dept Comp Sci College Pk MD 20742 USA Carnegie Mellon Univ Sch Comp Sci Pittsburgh PA 15213 USA Qatar Univ Dept Comp Sci & Engn Doha Qatar Inst Technol Sch Comp Sci Atlanta GA USA

Low-cost mini-drones with advanced sensing and maneuverability enable a new class of intelligent sensing systems. To achieve the full potential of such drones, it is necessary to develop new enhanced formulations of both common and emerging sensing scenarios. Namely, several fundamental challenges in visual sensing are yet to be solved including (1) fitting sizable targets in camera frames;(2) positioning cameras at effective viewpoints matching target poses;and (3) accounting for occlusion by elements in the environment, including other targets. In this article, we introduce Argus, an autonomous system that utilizes drones to collect target information incrementally through a two-tier architecture. To tackle the stated challenges, Argus employs a novel geometric model that captures both target shapes and coverage constraints. Recognizing drones as the scarcest resource, Argus aims to minimize the number of drones required to cover a set of targets. We prove this problem is NP-hard, and even hard to approximate, before deriving a best-possible approximation algorithm along with a competitive sampling heuristic which runs up to 100x faster according to large-scale simulations. To test Argus in action, we demonstrate and analyze its performance on a prototype implementation. Finally, we present a number of extensions to accommodate more application requirements and highlight some open problems.

关键词： Target coverage full-view coverage drone-based surveillance art gallery problems visibility approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Augmenting graphs to minimize the radius

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2023年 113卷

作者： Gudmundsson, Joachim Sha, Yuan Univ Sydney Sch Comp Sci Sydney NSW Australia

We study the problem of augmenting a metric graph by adding k edges while minimizing the radius of the augmented graph. We give a simple 3-approximation algorithm and show that there is no polynomial-time (5/3 - e)-approximation algorithm, for any e > 0, unless P =N *** also give two exact algorithms for the special case when the input graph is a tree, one of which is generalized to handle metric graphs with bounded treewidth.

关键词： Graph augmentation Radius approximation algorithm Bounded treewidth

来源：评论

学校读者我要写书评

暂无评论

Multicommodity Demand Flow in a Tree and Packing Integer Programs

引用

ACM TRANSACTIONS ON algorithmS 2007年第3期3卷 27–es页

作者： Chekuri, Chandra Mydlarz, Marcelo Shepherd, F. Bruce Univ Illinois Dept Comp Sci 201 N Goodwin Ave Urbana IL 61801 USA Yahoo Res Santiago Chile McGill Univ Dept Math & Stat Montreal PQ H3A 2K6 Canada

We consider requests for capacity in a given tree network T = (V, E) where each edge e of the tree has some integer capacity u(e). Each request f is a node pair with an integer demand d(f) and a profit w(f) which is obtained if the request is satisfied. The objective is to find a set of demands that can be feasibly routed in the tree and which provides a maximum profit. This generalizes well-known problems, including the knapsack and b-matching problems. When all demands are 1, we have the integer multicommodity flow problem. Garg et al. [1997] had shown that this problem is NP-hard and gave a 2-approximation algorithm for the cardinality case (all profits are 1) via a primal-dual algorithm. Our main result establishes that the integrality gap of the natural linear programming relaxation is at most 4 for the case of arbitrary profits. Our proof is based on coloring paths on trees and this has other applications for wavelength assignment in optical network routing. We then consider the problem with arbitrary demands. When the maximum demand d(max) is at most the minimum edge capacity u(min), we show that the integrality gap of the LP is at most 48. This result is obtained by showing that the integrality gap for the demand version of such a problem is at most 11.542 times that for the unit-demand case. We use techniques of Kolliopoulos and Stein [2004, 2001] to obtain this. We also obtain, via this method, improved algorithms for line and ring networks. Applications and connections to other combinatorial problems are discussed.

关键词： Integer multicommodity flow tree integrality gap packing integer program approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Parallel Machine Scheduling Problem Maximizing Total Weighted Early Work

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2021年第6期38卷 2150007-2150007页

作者： Choi, Byung-Cheon Park, Myoung-Ju Kim, Kyung Min Min, Yunhong Chungnam Natl Univ Sch Business 99 Daehak Ro Daejeon 34134 South Korea Kyung Hee Univ Dept Ind & Management Syst Engn 1732 Deogyeong Daero Yongin 17104 Kyunggi Do South Korea Myongji Univ Dept Ind Management & Engn 116 Myongji Ro Yongin 17058 Gyeonggi Do South Korea Incheon Natl Univ Grad Sch Logist 119 Acad Ro Incheon 22012 Gyeonggi Do South Korea

We consider the total weighted early work maximization problem on identical machines in parallel such that the weights are identical, or the due date is the same. First, we present an approach to solve the case with a fixed number of machines in pseudo-polynomial time. Then, we develop approximation algorithms for the two cases with identical weights and with a common due date. For the case with identical weights, furthermore, we show that the parallel-machine and a single-machine cases are strongly NP-hard and weakly NP-hard, respectively, even if the due date of each job is equal to the processing time multiplied by a constant.

关键词： Scheduling early work computational complexity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A novel health prognosis method for system based on improved degenerated Hidden Markov model

引用

ROBOTICS AND COMPUTER-INTEGRATED MANUFACTURING 2022年第0期78卷

作者： Liu, Qinming Chen, Xiang Dong, Ming Chen, Frank Univ Shanghai Sci & Technol Business Sch Dept Ind Engn 516 Jungong Rd Shanghai 200093 Peoples R China Shanghai Jiao Tong Univ Antai Coll Econ & Management Dept Operat Management 1954 Huashan Rd Shanghai 200030 Peoples R China Univ Texas San Antonio Dept Mech Engn San Antonio TX 78249 USA

Health prognosis for power system is considered as a crucial process of condition-based maintenance. In order to solve the problem of large deviation between Hidden Markov Model and actual system health diagnosis, this paper developed an improved Degenerated Hidden Markov Model (DGHMM) with a core of the quasi power relation. First, the model adopts the degradation factors described the process of recession for equipment continuous decreasing in performance. Compared with the conventional exponential accelerated degradation, the quasi power relation accelerated degradation can better describe the process that the performance of the system decreases gradually with the increase of service age. Then, the improved genetic algorithm can replace the conventional EM algorithm for parameters estimation, which overcomes the limitation that the EM algorithm is easy to fall into local optimization. At the same time, in terms of the limitation of life prognosis problem as a result of the Hidden Markov Model must obey exponential distribution, an algorithm named greed approximation based on approximation algorithm and Viterbi algorithm can be proposed to seek maximum probability remaining observation for the purpose of seeking maximum probability dynamically surplus state path to predict the residual life of system. Finally, the proposed method is validated and evaluated with the data set of caterpillar hydraulic pumps. The results show that the method of system health diagnosis and life prognosis based on the improved degraded hidden Markov model is more effective in describing system degeneration and the accuracy of equipment state diagnosis, and is also feasible in the prediction of residual life.

关键词： Hidden Markov model Degradation health diagnostics Residual useful lifetime Genetic algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：