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

60th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： van den Brand, Jan Nanongkai, Danupon KTH Royal Inst Technol Stockholm Sweden

ISBN: (纸本)9781728149523

Consider the following distance query for an n-node graph G undergoing edge insertions and deletions: given two sets of nodes I and J, return the distances between every pair of nodes in I x J. This query is rather general and captures several versions of the dynamic shortest paths problem. In this paper, we develop an efficient (1 + epsilon)-approximation algorithm for this query using fast matrix multiplication. Our algorithm leads to answers for some open problems for Single-Source and All-Pairs Shortest Paths (SSSP and APSP), as well as for Diameter, Radius, and Eccentricities. Below are some highlights. Note that all our algorithms guarantee worst-case update time and are randomized (Monte Carlo), but do not need the oblivious adversary assumption. Subquadratic update time for SSSP, Diameter, Centralities, ect.: When we want to maintain distances from a single node explicitly (without queries), a fundamental question is to beat trivially calling Dijkstra's static algorithm after each update, taking Theta(n(2)) update time on dense graphs. A better time complexity was not known even with amortization. It was known to be improbable for exact algorithms and for combinatorial any-approximation algorithms to polynomially beat the Omega(n(2)) bound (under some conjectures) [Roditty, Zwick, ESA'04;Abboud, V. Williams, FOCS'14].(1) Our algorithm with I = {s} and J = V (G) implies a (1 + epsilon)-approximation algorithm for this, guaranteeing O(n(1.823)/epsilon(2)) worst-case update time for directed graphs with positive real weights in [1, W](2) With ideas from [Roditty, V. Williams, STOC'13], we also obtain the first subquadratic worst-case update time for (5/3 + epsilon)-approximating the eccentricities and (1.5 + epsilon)-approximating the diameter and radius for unweighted graphs (with small additive errors). We also obtain the first subquadratic worst-case update time for (1 + epsilon)-approximating the closeness centralities for undirected unweighted graphs. Wors

关键词： data-structures dynamic algorithms diameter radius eccentricities single-source distances all-pairs distances approximate

来源：评论

学校读者我要写书评

暂无评论

Rounding dynamic Matchings against an Adaptive Adversary 2020

Rounding Dynamic Matchings against an Adaptive Adversary

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Wajc, David Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781450369794

We present a new dynamic matching sparsification scheme. From this scheme we derive a framework for dynamically rounding fractional matchings against adaptive adversaries. Plugging in known dynamic fractional matching algorithms into our framework, we obtain numerous randomized dynamic matching algorithms which work against adaptive adversaries. In contrast, all previous randomized algorithms for this problem assumed a weaker, oblivious, adversary. Our dynamic algorithms against adaptive adversaries include, for any constant epsilon > 0, a (2 + epsilon)-approximate algorithm with constant update time or polylog worst-case update time, as well as (2 - delta)-approximate algorithms in bipartite graphs with arbitrarily-small polynomial update time. All these results achieve polynomially better update time to approximation trade-offs than previously known to be achievable against adaptive adversaries.

关键词： dynamic algorithms dynamic Matching Matching Sparsifier Adaptive Adversary

来源：评论

学校读者我要写书评

暂无评论

dynamic Boolean Matrix Factorizations

Dynamic Boolean Matrix Factorizations

引用

12th IEEE International Conference on Data Mining (ICDM)

作者： Miettinen, Pauli Max Planck Inst Informat D-66123 Saarbrucken Germany

ISBN: (纸本)9781467346498;9780769549057

Boolean matrix factorization is a method to decompose a binary matrix into two binary factor matrices. Akin to other matrix factorizations, the factor matrices can be used for various data analysis tasks. Many (if not most) real-world data sets are dynamic, though, meaning that new information is recorded over time. Incorporating this new information into the factorization can require a re-computation of the factorization - something we cannot do if we want to keep our factorization up-to-date after each update. This paper proposes a method to dynamically update the Boolean matrix factorization when new data is added to the data base. This method is extended with a mechanism to improve the factorization with a trade-off in speed of computation. The method is tested with a number of real-world and synthetic data sets including studying its efficiency against off-line methods. The results show that with good initialization the proposed online and dynamic methods can beat the state-of-the-art offline Boolean matrix factorization algorithms.

关键词： Boolean matrix factorization On-line algorithms dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic Power Control for Packets with Deadlines

Dynamic Power Control for Packets with Deadlines

引用

IEEE Global Conference on Communications (GLOBECOM) / Workshop on Wireless Networking and Control for UAV

作者： Fountoulakis, Emmanouil Pappas, Nikolaos Liao, Qi Ephremides, Anthony Angelakis, Vangelis Linkoping Univ Dept Sci & Technol Linkoping Sweden Nokia Bell Labs Stuttgart Germany Univ Maryland Elect & Comp Engn Dept College Pk MD 20742 USA

ISBN: (纸本)9781538647271

Wireless devices need to adapt their transmission power according to the fluctuating wireless channel in order to meet constraints of delay sensitive applications. In this paper, we consider delay sensitivity in the form of strict packet deadlines arriving in a transmission queue. Packets missing the deadline while in the queue are dropped from the system. We aim at minimizing the packet drop rate under average power constraints. We utilize tools from Lyapunov optimization to find an approximate solution by selecting power allocation. We evaluate the performance of the proposed algorithm and show that it achieves the same performance in terms of packet drop rate with that of the Earliest Deadline First (EDF) when the available power is sufficient. However, our algorithm outperforms EDF regarding the trade-off between packet drop rate and average power consumption.

关键词： Deadline-constrained traffic power efficient algorithms Lyapunov optimization centralized scheduler dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

On-line and dynamic Estimation of Rician Fading Channels in GSM-R Networks

On-line and Dynamic Estimation of Rician Fading Channels in ...

引用

4th International Conference on Wireless Communications and Signal Processing (WCSP)

作者： Ma, Yongsen Du, Pengyuan Mao, Xiaofeng Long, Chengnian Shanghai Jiao Tong Univ Minist Educ Dept Automat Key Lab Syst Control & Informat Proc Shanghai 200030 Peoples R China Shanghai Jiao Tong Univ Dept Elect Engn Shanghai Peoples R China

ISBN: (纸本)9781467358293;9781467358309

The on-line and dynamic estimation algorithm for Rician fading channels in GSM-R networks is proposed, which is an expansion of local mean power estimation of Rayleigh fading channels. The proper length of statistical interval and required number of averaging samples are determined which are adaptive to different propagation environments. It takes advantage of the sampling signals and Rician fading parameters of last estimation to reduce measurement overhead. The performance of this method was evaluated by measurement experiment along the Beijing-Shanghai high-speed railway. When it is NLOS propagation, the required sampling intervals can be increased from 1.1 lambda in Lee's method to 3.7 lambda of the on-line and dynamic algorithm. And the sampling interval can be set up to 12 lambda although the length of statistical interval decreases when there is LOS signal, which can reduce the measurement overhead significantly. The algorithm can be applied in coverage assessment with lower measurement overhead, and in dynamic and adaptive allocation of wireless resource.

关键词： Rician fading channels IN-LINE dynamic algorithms sampling interval Self tuning

来源：评论

学校读者我要写书评

暂无评论

A dynamic algorithm for palmprint recognition 3

A dynamic algorithm for palmprint recognition

引用

IEEE Conference Communications and Network Security CNS

作者： Palma, David Montessoro, Pier Luca Giordano, Giulia Blanchini, Franco Univ Udine Dept Elect Management & Mech Engn Udine Italy Univ Udine Dept Math & Comp Sci Udine Italy

ISBN: (纸本)9781467378765

Most of the existing techniques for palmprint recognition are based on metrics that evaluate the distance between a pair of features. These metrics are typically based on static functions. In this paper we propose a new technique for palmprint recognition based on a dynamical system approach, focusing on preliminary experimental results. The essential idea is that the procedure iteratively eliminates points in both images to be compared which do not have enough close neighboring points in the image itself and in the comparison image. As a result of the iteration, in each image the surviving points are those having enough neighboring points in the comparison image. Our preliminary experimental results show that the proposed dynamic algorithm is competitive and slightly outperforms some state-of-the-art methods by achieving a higher genuine acceptance rate.

关键词： Biometrics (access control) Databases Feature extraction Heuristic algorithms Security Yttrium biometrics (access control) dynamic algorithms Heuristic algorithms Rare earths yttrium Feature extraction Database images Imagery (Psychotherapy) Security point image Image Metronidazole

来源：评论

学校读者我要写书评

暂无评论

A Comprehensive Study of Load Balancing Approaches in Real-Time Multi-Core Systems for Mixed Real-Time Tasks

引用

IEEE ACCESS 2024年 12卷 53373-53395页

作者： Jadon, Shruti Kannan, Pradyuman Kavedi Kalaria, Urmil Varsha, K. R. Gupta, Karthik Honnavalli, Prasad B. PES Univ Dept Comp Sci Engn Bengaluru 560085 India

Real-time systems are becoming pervasive with the growing global connectivity and rising consumer demands. The need for real-time processing has become a crucial part of many business applications worldwide. A key factor that determines the time taken for an application to give out the result hinges on its ability to prioritize, manage, and execute real-time workloads. However, there are several difficulties and constraints connected with implementing tasks in a real-time context. This research study primarily focuses on load balancing for mixed real-time tasks on a multi-core system, one of the major challenges for executing real-time workloads. The purpose of load balancing is to distribute the load evenly among the processor(s) and maximize their utility while minimizing overall execution time. The goal of this paper is to present a critical analysis of existing load balancing techniques for both periodic and aperiodic tasks. The paper explores several factors including throughput, performance, migration time, response time, overhead, resource utilization, scalability, fault tolerance, power efficiency, and other variables that play a crucial role in assessing the efficacy of load balancing in real-time systems. The proposed has contributed in four folds. Firstly, the state-of-the-art of various load balancing algorithms are discussed followed by the architecture involved in real-time multi-core systems. Later, different load balancing based scheduling algorithms were compared on the basis of different schemas and metrics for algorithm evaluation is also provided. Finally, the paper also identifies areas that warrant further exploration or investigation, suggesting potential avenues for future research, and highlighting emerging trends or developments that may shape the field.

关键词： Task analysis Real-time systems Heuristic algorithms Scheduling Load management Partitioning algorithms Scheduling algorithms real-time systems priority-driven algorithms EDF (earliest deadline first) RM (rate-monotonic) LBPSA (load balanced partitioning and scheduling algorithm) homogeneous multi-core heterogeneous multi-core static algorithms dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

HORIZON COMPUTATION ON A HIERARCHICAL TRIANGULATED TERRAIN MODEL

引用

VISUAL COMPUTER 1995年第3期11卷 134-149页

作者： DEFLORIANI, L MAGILLO, P University of Genoa

Hierarchical terrain models describe a topographic surface at different levels of detail, thus providing a multiresolution surface representation as well as a data compression mechanism. We consider the horizon computation problem on a hierarchical polyhedral terrain (in particular, on a hierarchical triangulated irregular network), which involves extracting the horizon of a viewpoint at a given resolution and updating it as the resolution increases. We present an overview of horizon computation algorithms on a nonhierarchical polyhedral terrain. We extend such algorithms to the hierarchical case by describing a method which extracts the terrain edges at a given resolution, and proposing a randomized algorithm for dynamically updating a horizon under insertions and deletions of terrain edges

关键词： DIGITAL TERRAIN MODELS HIERARCHICAL MODELS VISIBILITY dynamic algorithms RANDOMIZED algorithms

来源：评论

学校读者我要写书评

暂无评论

Adaptive functional programming

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 2006年第6期28卷 990-1034页

作者： Acar, Umut A. Blelloch, Guy E. Harper, Robert Toyota Technol Inst Chicago IL USA Carnegie Mellon Univ Pittsburgh PA USA

We present techniques for incremental computing by introducing adaptive functional programming. As an adaptive program executes, the underlying system represents the data and control dependences in the execution in the form of a dynamic dependence graph. When the input to the program changes, a change propagation algorithm updates the output and the dynamic dependence graph by propagating changes through the graph and re-executing code where necessary. Adaptive programs adapt their output to any change in the input, small or large. We show that adaptivity techniques are practical by giving an efficient implementation as a small ML library. The library consists of three operations for making a program adaptive, plus two operations for making changes to the input and adapting the output to these changes. We give a general bound on the time it takes to adapt the output, and based on this, show that an adaptive Quicksort adapts its output in logarithmic time when its input is extended by one key. To show the safety and correctness of the mechanism we give a formal definition of AFL, a call-by-value functional language extended with adaptivity primitives. The modal type system of AFL enforces correct usage of the adaptivity mechanism, which can only be checked at run time in the ML library. Based on the AFL dynamic semantics, we formalize the change-propagation algorithm and prove its correctness. Categories and Subject Descriptors: D.1.0 [Programming Techniques]: General;D.1.1 [Programming Techniques]: Applicative (Functional) Programming;D.3.0 [Programming Languages]: General;D.3.1 [Programming Languages]: Formal Definitions and Theory;F.2.0 [Analysis of algorithms and Problem Complexity]: General;F.3.2 [Logics and Meanings of Programs]: Semantics of Programming Languages.

关键词： algorithms languages performance theory incremental computation adaptive computation dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

SCHEDULING HARD REAL-TIME SYSTEMS - A REVIEW

引用

SOFTWARE ENGINEERING JOURNAL 1991年第3期6卷 116-128页

作者： BURNS, A UNIV YORK DEPT COMP SCIYORK YO1 5DDN YORKSHIREENGLAND

Recent results in the application of scheduling theory to hard real-time systems are reviewed in this paper. The review takes the form of an analysis of the problems presented by different application requirements and characteristics. Issues covered include uniprocessor and multiprocessor systems, periodic and aperiodic processes, static and dynamic algorithms, transient overloads and resource usage. Protocols that limit and reduce blocking are discussed. Consideration is also given to scheduling Ada tasks.

关键词： multiprocessing systems transient overloads resource usage protocols periodic processes aperiodic processes Operating systems scheduling theory static algorithms dynamic algorithms multiprocessor systems scheduling Ada tasks Ada scheduling application requirements real-time systems uniprocessor hard real-time systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：