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

Analysis of a time-dependent scheduling problem by signatures of deterioration rate sequences

DISCRETE APPLIED MATHEMATICS 2006年第15期154卷 2150-2166页

作者： Gawiejnowicz, Stanislaw Kurc, Wieslaw Pankowska, Lidia Adam Mickiewicz Univ Fac Math & Comp Sci PL-61614 Poznan Poland

In the paper a single machine time-dependent scheduling problem is considered. The processing time p(j) of each job is described by a function of the starting time t of the job, p(j) = 1 + alpha(j)t, where the job deterioration rate alpha(j) >= 0 for j = 0, 1,..., n and t >= 0. Jobs are nonpreemptable and independent, there are no ready times and no deadlines. The criterion of optimality of a schedule is the total completion time. First, the notion of a signature for a given sequence of job deterioration rates is introduced, two types of the signature are defined and their properties are shown. Next, on the basis of these properties a greedy polynomial-time approximation algorithm for the problem is formulated. This algorithm, starting from an initial sequence, iteratively constructs a new sequence concatenating the previous sequence with new elements, according to the sign of one of the signatures of this sequence. Finally, these results are applied to the problem with job deterioration rates which are consecutive natural numbers, alpha(j) = j for j = 0, 1,..., n. Arguments supporting the conjecture that in this case the greedy algorithm is optimal are presented. (c) 2006 Elsevier B.V. All rights reserved.

关键词： single machine scheduling deteriorating jobs total completion time approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating the projection depth median of dimensions p 3

引用

COMMUNICATIONS IN STATISTICS-SIMULATION AND COMPUTATION 2017年第5期46卷 3756-3768页

作者： Liu, Xiaohui Jiangxi Univ Finance & Econ Sch Stat Nanchang 330013 Jiangxi Peoples R China Jiangxi Univ Finance & Econ Res Ctr Appl Stat Nanchang 330013 Jiangxi Peoples R China

As a multivariate generalization of the univariate median, projection depth median (PM) is unique, and enjoys a very high breakdown point, much higher than its affine equivariant competitors such as halfspace depth median. Nevertheless, its computation is challenging. Until now PM can only be exactly computed efficiently for bivariate data. In this article, we develop an algorithm to approximate PM in higher dimensions. Some data examples indicate that the proposed algorithm performs well in terms of both accuracy and efficiency. As an application, we investigate the finite sample relative efficiency of PM by utilizing the Matlab implementation of this algorithm.

关键词： approximate algorithm Projection depth Projection depth median Relative efficiency 62F10 62F40 62F35

来源：评论

学校读者我要写书评

暂无评论

Finding events in temporal networks: segmentation meets densest subgraph discovery

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2019年第4期62卷 1611-1639页

作者： Rozenshtein, Polina Bonchi, Francesco Gionis, Aristides Sozio, Mauro Tatti, Nikolaj Aalto Univ Dept Comp Sci Data Min Grp Espoo Finland Aalto Univ Dept Comp Sci Espoo Finland ISI Fdn Turin Italy Eurecat Technol Ctr Catalunya Big Data & Data Sci Barcelona Spain Telecom ParisTech Univ Dept Comp Sci Paris France F Secure Corp Helsinki Finland Univ Helsinki Helsinki Finland Nordea Data Sci Lab Helsinki Finland

In this paper, we study the problem of discovering a timeline of events in a temporal network. We model events as dense subgraphs that occur within intervals of network activity. We formulate the event discovery task as an optimization problem, where we search for a partition of the network timeline into k non-overlapping intervals, such that the intervals span subgraphs with maximum total density. The output is a sequence of dense subgraphs along with corresponding time intervals, capturing the most interesting events during the network lifetime. A naive solution to our optimization problem has polynomial but prohibitively high running time. We adapt existing recent work on dynamic densest subgraph discovery and approximate dynamic programming to design a fast approximation algorithm. Next, to ensure richer structure, we adjust the problem formulation to encourage coverage of a larger set of nodes. This problem is NP-hard;however, we show that on static graphs a simple greedy algorithm leads to approximate solution due to submodularity. We extend this greedy approach for temporal networks, but we lose the approximation guarantee in the process. Finally, we demonstrate empirically that our algorithms recover solutions with good quality.

关键词： Densest subgraph Segmentation Dynamic programming approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Bloom filter based processing algorithms for the multi-dimensional event query in wireless sensor networks

引用

JOURNAL OF NETWORK AND COMPUTER APPLICATIONS 2014年第Jan.期37卷 323-333页

作者： Li, Guilin Guo, Longjiang Gao, Xing Liao, Minghong Xiamen Univ Sch Software Xiamen Peoples R China Heilongjiang Univ Sch Comp Sci & Technol Harbin Peoples R China

To solve the multi-dimensional event based query in wireless sensor networks, this paper proposes four bloom filter based query processing algorithms UBP, BBP, SRBP and PBP. The four algorithms proposed can be classified into two classes: two bloom filter based precise algorithms, which are UBP and BBP, and two bloom filter based approximate algorithms, which are SRBP and PBP. By using the bloom filter and introducing the inaccuracy, the communication cost involved by the query processing can be reduced. For the two precise algorithms UBP and BBP, simulation results show that UBP consumes 51% less energy than BBP on average. UBP is better than BBP on energy consumption. For energy consumption comparison between the approximate algorithms and the precise algorithm UBP, simulation results show that SRBP consumes 18% less energy than UBP on average as while as PBP consume approximately the same energy as UBP on average. For query accuracy comparison between the approximate algorithms and the precise algorithm UBP, simulation results show that the average relative error between UBP and PBP is 14% and the average relative error between UBP and SRBP is 2%. SRBP is better than PBP on energy consumption and query accuracy respectively. UBP and SRBP are two preferred bloom filter based query processing algorithms. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Multi-dimensional event query Bloom filter approximate algorithm Wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

SCHEDULING INDEPENDENT TASKS ON UNIFORM PROCESSORS: 收藏
分享
引用; SIAM JOURNAL ON COMPUTING 1984年第4期13卷 705-716页; 作者： DOBSON, G Univ of Rochester Graduate Sch of Management Rochester NY USA Univ of Rochester Graduate Sch of Management Rochester NY USA; A worst-case analysis is given for the LPT (longest processing time) heuristic applied to the problem of scheduling independent tasks on uniform processors. A bound of 1912</span; A worst-case analysis is given for the LPT (longest processing time) heuristic applied to the problem of scheduling independent tasks on uniform processors. A bound of $\frac{19}{12}$; 关键词： scheduling independent tasks uniform processors finish time approximate algorithm; 来源：评论; 学校读者我要写书评

暂无评论

A Novel Routing algorithm with Bernoulli Sampling-based Link Quality Estimation in Wireless Sensor Networks

引用

WIRELESS PERSONAL COMMUNICATIONS 2022年第3期126卷 2753-2779页

作者： Meng, Chao Nanjing Univ Posts & Telecommun Nanjing Sch Modern Posts Nanjing 210003 Jiangsu Peoples R China

Link quality is important and can greatly affect the performance of wireless transmission algorithms and protocols. Currently, researchers have proposed a variety of approaches to implement link quality estimation. However, the estimated result of link quality is not accurate enough and the error is large, so they may lead to the failure of routing algorithm and protocol. In this paper, a novel method is proposed to achieve the more accurate estimation of link quality than before. This method employs Bernoulli sampling-based algorithm to complete the estimation of link quality. The problem is modeled as calculation of estimators based on Bernoulli sampling data. The authors further prove that the calculation results are accurate by probability theory. Furthermore, according to link quality estimation, the authors also provide a centralized routing algorithm and a distributed improvement algorithm in order to switch the data transmission on the better quality link. Finally, the extensive experiment results indicate that the proposed methods obtain high performance in terms of energy consumption and accuracy.

关键词： Wireless sensor networks Bernoulli sampling Link quality approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Mining Probabilistically Frequent Sequential Patterns in Large Uncertain Databases

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2014年第5期26卷 1171-1184页

作者： Zhao, Zhou Yan, Da Ng, Wilfred Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China

Data uncertainty is inherent in many real-world applications such as environmental surveillance and mobile tracking. Mining sequential patterns from inaccurate data, such as those data arising from sensor readings and GPS trajectories, is important for discovering hidden knowledge in such applications. In this paper, we propose to measure pattern frequentness based on the possible world semantics. We establish two uncertain sequence data models abstracted from many real-life applications involving uncertain sequence data, and formulate the problem of mining probabilistically frequent sequential patterns (or p-FSPs) from data that conform to our models. However, the number of possible worlds is extremely large, which makes the mining prohibitively expensive. Inspired by the famous PrefixSpan algorithm, we develop two new algorithms, collectively called U-PrefixSpan, for p-FSP mining. U-PrefixSpan effectively avoids the problem of "possible worlds explosion", and when combined with our four pruning and validating methods, achieves even better performance. We also propose a fast validating method to further speed up our U-PrefixSpan algorithm. The efficiency and effectiveness of U-PrefixSpan are verified through extensive experiments on both real and synthetic datasets.

关键词： Frequent patterns uncertain databases approximate algorithm possible world semantics

来源：评论

学校读者我要写书评

暂无评论

Provably efficient security-aware service function tree composing and embedding in multi-vendor networks

引用

COMPUTER NETWORKS 2024年 254卷

作者： Zheng, Danyang Xing, Huanlai Feng, Li Cao, Xiaojun Southwest Jiaotong Univ Sch Comp & Artificial Intelligence Chengdu Peoples R China Georgia State Univ Dept Comp Sci Atlanta GA USA

Multicast greatly benefits many emerging applications such as federated learning, metaverse, and data warehouse. Recently, due to frequent cyber-attacks, multicast services have tended to request rigorous security agreements, which likely differ among the destinations. To meet such agreements, one can employ security-aware service functions (SFs) to construct the security-aware SF tree (S-SFT) for multicast services. A security-aware SF can be provided by various vendors with diverse configurations and implementation costs. The multi-configured SFs and the various security agreements will add significant complexity to the deployment process of the security-aware multicast request. In this work, for the first time, we study how to effectively compose and embed an S-SFT over the network with multiple vendors. We formulate the problem of security- aware SFT composing and embedding. We develop a new technique called cost-security-centrality (CSC) based on the pigeonhole' s principle and propose a heuristic algorithm called CSC-based S-SFT deployment (CSC-SD). Via thorough mathematical proofs, we show that CSC-SD is logarithm approximate. Extensive simulations show that CSC-SD significantly outperforms the benchmarks and reveal that more function sharing facilitates saving implementation cost, but more routing sharing does not indicate saving routing cost.

关键词： Security-aware service function chain approximate algorithm Service function tree deployment

来源：评论

学校读者我要写书评

暂无评论

An improved algorithm for integrated production and distribution scheduling problem with committed delivery dates

引用

OPTIMIZATION LETTERS 2015年第3期9卷 537-567页

作者： Zhong, Weiya Shanghai Univ Sch Management Dept Business Adm Shanghai Peoples R China

In this paper, we study a machine scheduling problem with job transportation coordination. The orders including different amount of the same product will be delivered to their customers after being completed on a single machine and each order has a delivery due date which is promised by the manufacturer to its customer. A third-party logistics provider picks up the finished orders at the end of each day and charges each order a delivery cost, which is linearly decreasing with the delivery time and linearly increasing with its quantity. The goal is to find a schedule minimizing total delivery cost under the constraint that all the orders are delivered to the customers before the due dates. The problem is strongly NP-hard. We propose an improved approximate algorithm with worst-case ratio of , which improves the existing one with worst-case ratio of .

关键词： Scheduling approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Network Service Chaining and Embedding With Provable Bounds

引用

IEEE INTERNET OF THINGS JOURNAL 2021年第9期8卷 7140-7151页

作者： Zheng, Danyang Gu, Huaxi Wei, Wenting Peng, Chengzong Cao, Xiaojun Georgia State Univ Dept Comp Sci Atlanta GA 30302 USA Xidian Univ State Key Lab Integrated Serv Networks Xian 710071 Peoples R China

Network function virtualization (NFV) is introduced to effectively deliver end-to-end network services for the emerging Internet of Things (IoT), multiaccess edge computing, and 5G communication techniques. In NFV, the network service request can be accommodated in the form of a service function chain (SFC). The SFC will have to reserve abundant resources, such as link bandwidth, service functions, and computation in the physical network to meet the demands of customers. Minimizing the cost from the resource reservation in NFV remains challenging, even though a few works in the literature proposed cost-optimization methodologies with assumptions to guarantee their correctness. In this article, we comprehensively investigate how to minimize the cost when delivering network services as SFCs with provable bounds and fewer assumptions. We formally define the problem of minimum cost service function chaining and embedding (MC-SFCE) and propose an algorithm, namely, cost factor-based SFCE optimization with shortcut (COFO-SC), for MC-SFCE. Novel mathematical analysis is provided to demonstrate the correctness of our approaches and related bounds. Our extensive simulations and analysis also show that the proposed COFO-SC outperforms the schemes directly extended from the existing work.

关键词： Internet of Things Bandwidth Topology Approximation algorithms Optimization Heuristic algorithms Switches approximate algorithm Internet of Things (IoT) network function virtualization (NFV) service function chain (SFC) embedding

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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