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

A 2.79 COMPETITIVE on-line algorithm FOR TWO PROCESSOR REAL-TIME SYSTEMS WITH UNIFORM VALUE DENSITY

Applied Mathematics(A Journal of Chinese Universities) 1997年第3期12卷 333-342页

作者： YANGQIFAN DepartmentofAppliedMathematics ZhejiangUniversityHangthou310027.

We consider the problem of competitive on-liae scheduling in two processor real-timesystems. In our model all tasks have common value density. Each task has a release time. an exe-cution time and a deadline. The scheduler is given no information about a task until it is *** the value will be achieved if and only if the task is completed by its deadlirte. Moreover. wesuppose that migratbn is not allowed. The goal of the scheduler is to obtain as much value as pos-sible. In this paper we show that the competitive multipber of Safe-Risky-fixed algorithm irt [4]is really 3 and presents a modified algorithm (Safe-Risky-unfixed algorithm) that achieves a com-petitive mukiplier of 2. 79.

关键词： Real-time system on-line algorithm value density competitive multiplier covered tasks uncovered tasks maxcover

来源：评论

学校读者我要写书评

暂无评论

An on-line algorithm to Determine the Location of the Server in a Server Migration Service 12

An On-line Algorithm to Determine the Location of the Server...

引用

2015 12th Annual IEEE Consumer Communications and Networking Conference (CCNC)

作者： Hoshino, Yuta Fukushima, Yukinobu Murase, Tutomu Yokohira, Tokumi Suda, Tatsuya Okayama Univ Grad Sch Nat Sci & Technol Okayama Japan NEC Corp Ltd Cloud Syst Res Labs Kawasaki Kanagawa Japan Univ Netgrp Inc Fallbrook CA USA

ISBN: (纸本)9781479963904

In IaaS cloud services, QoS of network applications (NW-Apps) may degrade due to location factors such as significant distance between a server-side application (server) of a NW-App at a data center and a client-side application (client) of the NW-App at a client terminal. In order to shorten the distance and to improve the QoS, server migration services (SMSes) have been proposed. In SMSes, servers may migrate between different computers (called work places, WPs) on a network to prevent QoS degradation caused by the changes of client locations. Although server migrations can improve QoS of NW-Apps, they also generate a huge amount of traffic (server migration traffic) in the network. This paper focuses on a server location decision problem where the location of a server is decided in an on-line manner so that QoS of a NW-App is improved under the constraint that the server migration traffic has to be suppressed below an acceptable level. For the problem, we propose a practical on-line algorithm. The key idea behind the proposed algorithm is that the location of the server is decided with consideration of the QoS degradation in the future. The algorithm defines the averagely good location for the server where the QoS is expected to be relatively good for various client locations. Then, it keeps the range of the server's migration within the returnable range where the server can soon come back to the averagely good location. As a result, the QoS can be always kept as good as the one under the averagely good location. Simulation results show that the proposed algorithm improves QoS of the NW-App by up to 30% compared to a greedy algorithm.

关键词： IaaS cloud service server migration service server location decision problem on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

An optimal on-line algorithm for preemptive scheduling on two uniform machines in the l_p norm

引用

4th International Conference on algorithmic Aspects in Information and Management

作者： Shuai, Tianping Du, Donglei Jiang, Xiaoyue Beijing Univ Posts & Telecommun Sch Sci Beijing Peoples R China Univ New Brunswick Fac Business Adm Fredericton NB Canada Louisiana State Univ Engn Coll Baton Rouge LA USA

ISBN: (纸本)9783540688655

One of the basic and fundamental problems in scheduling is to minimize the machine completion time vector in the l(p) norm (a direct extension of the l(infinity) norm: the makespan) on uniform parallel machines. We concentrate on the on-line and preemptive version of this problem where jobs arrive one by one over a list and are allowed to be preempted. We present a best possible deterministic on-line scheduling algorithm along with a matching lower bound when there are two machines, generalizing existing results for the identical machines scheduling problem in the literature. The main difficulty in the design of the algorithm and the analysis of the resultant competitive ratio as well as the proof of the lower bound is that the competitive ratio is only known to be the root of some equation systems, which admits no analytic solution-a distinct feature from most existing literature on competitive analysis. As a consequence, we develop some new ideas to tackle this difficulty. Specifically we need to exploit the properties of the equations system that defines the competitive ratio.

关键词： on-line algorithm scheduling preemption l(p) norm

来源：评论

学校读者我要写书评

暂无评论

To reorient is easier than to orient: An on-line algorithm for reorientation of graphs

引用

COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE 2021年第3期10卷 215-233页

作者： Fiori-Carones, Marta Marcone, Alberto Univ Udine Dipartimento Sci Matemat Informat & Fis Via Sci 208 I-33100 Udine Italy

We define an on-line (incremental) algorithm that, given a (possibly infinite) pseudo-transitive oriented graph, produces a transitive reorientation. This implies that a theorem of Ghouila-Houri is provable in RCA(0) ... 详细信息

关键词： on-line algorithm reverse mathematics comparability graphs pseudo-transitive graphs reorientations

来源：评论

学校读者我要写书评

暂无评论

A Best on-line algorithm for Single Machine Scheduling the Equal Length Jobs with the Special Chain Precedence and Delivery Time

A Best On-line Algorithm for Single Machine Scheduling the E...

引用

4th International Conference on Graphic and Image Processing (ICGIP)

作者： Gu, Cunchang Mu, Yundong Henan Univ Technol Coll Sci Zhengzhou 450000 Peoples R China

ISBN: (纸本)9780819495662

In this paper, we consider a single machine on-line scheduling problem with the special chains precedence and delivery time. All jobs arrive over time. The chains(i) chains arrive at time r(i), it is known that the processing and delivery time of each job on the chain satisfy one special condition CD aforehand: if the job J(j)((i)) is the predecessor of the job J(k)((i)) on the chain chains(i), then they satisfy p(j)((i)) = p(k)((i)) = p >= q(j) >= q(k), i = 1,2, ..., n, where p(j) and q(j) denote the processing time and the delivery time of the job J(j) respectively. Obviously, if the arrival jobs have no chains precedence, it shows that the length of the corresponding chain is 1. The objective is to minimize the time by which all jobs have been delivered. We provide an on-line algorithm with a competitive ratio of root 2, and the result is the best possible.

关键词： Chain precedence equal length job single machine delivery time on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

An on-line algorithm for Music-to-Score Alignment of Guzheng Performance 23

An On-line Algorithm for Music-to-Score Alignment of Guzheng...

引用

23rd IEEE International Conference on Digital Signal Processing (DSP)

作者： Wang, Ziyi Cao, Yin Tsinghua Univ Dept Elect Engn Beijing Peoples R China Chinese Acad Sci Inst Acoust Key Lab Noise & Vibrat Res Beijing Peoples R China

ISBN: (纸本)9781538668122;9781538668115

There are many obstacles preventing new learners of the Guzheng from getting faster improvements. For example, the need to flip the music sheet with one hand interrupts the consistency of the performance. To overcome these difficulties, an on-line algorithm for music-to-score alignment is proposed in this paper, whose function is to detect and trace the progress of the music signal recorded by a microphone. The use of Dynamic Time Warping (DTW) technique helps to align the standard music and the recording. Therefore, it is possible to show the progress on the screen in the real time and flip the page automatically when it is required. Furthermore, the errors of the player's performance can also be detected with further improvements of the algorithm.

关键词： Music-to-score Alignment on-line algorithm Guzheng

来源：评论

学校读者我要写书评

暂无评论

An on-line algorithm for generation of stable mappings in a generalized modular network SOM

引用

International Congress Series 2007年 1301卷 164-167页

作者： Tokunaga, Kazuhiro Furukawa, Tetsuo Kyushu Institute of Technology Kitakyushu 808-0196 Japan

Recently, we proposed a modular network SOM (mnSOM) in which each nodal unit of the conventional SOM is replaced by a neural network module. In the mnSOM, the learning algorithm is based on the batch learning SOM for generation of stability mapping, since the on-line algorithm of the SOM depends on initial condition and the scheduling of the neighborhood function. However, when the mnSOM is applied to an autonomous robot or a control system in which the unlabeled episode data are observed from sensors one after another, then the mnSOM should be used with on-line mode. In this paper, we propose an on-line mnSOM algorithm based on Bayesian theory in order to generate a stable map. Moreover, the availability of our proposed algorithm is shown with a result of a simulation. © 2007 Elsevier B.V. All rights reserved.

关键词： Modular network on-line algorithm Self-organizing map Unlabeled episode

来源：评论

学校读者我要写书评

暂无评论

A fast on-line algorithm for the longest common subsequence problem with constant alphabet

A fast On-Line algorithm for the longest common subsequence ...

引用

作者： Sakai, Yoshifumi Graduate School of Agricultural Science Tohoku University Sendai-shi 981-8555 Japan

This article presents an algorithm that solves an on-line version of the longest common subsequence (LCS) problem for two strings over a constant alphabet in O(d+n) time and O(m+d) space, where m is the length of the shorter string, the whole of which is given to the algorithm in advance, n is the length of the longer string, which is given as a data stream, and d is the number of dominant matches between the two strings. A new upper bound, O(p(m - q)), of d is also presented, where p is the length of the LCS of the two strings, and q is the length of the LCS of the shorter string and the m-length prefix of the longer string. © 2012 The Institute of Electronics, Information and Communication Engineers.

关键词： algorithm Longest common subsequence on-line algorithm String comparison

来源：评论

学校读者我要写书评

暂无评论

An On-line Competitive algorithm for Coloring Bipartite Graphs Without Long Induced Paths

引用

algorithmICA 2017年第4期77卷 1060-1070页

作者： Micek, Piotr Wiechert, Veit Jagiellonian Univ Theoret Comp Sci Dept Fac Math & Comp Sci Krakow Poland Tech Univ Berlin Inst Math Berlin Germany

The existence of an on-line competitive algorithm for coloring bipartite graphs is a tantalizing open problem. So far there are only partial positive results for bipartite graphs with certain small forbidden graphs as... 详细信息

关键词： on-line algorithm Graph coloring Bipartite graphs

来源：评论

学校读者我要写书评

暂无评论

A Novel On-line Association algorithm for Supporting Load Balancing in Multiple-AP Wireless LAN

引用

MOBILE NETWORKS & APPLICATIONS 2018年第3期23卷 395-406页

作者： Sun, Liang Wang, Lei Qin, Zhenquan Yuan, Zhuxiu Chen, Yuanfang Dalian Univ Technol Sch Software Dalian Peoples R China Hangzhou Dianzi Univ Sch Cyberspace Hangzhou Zhejiang Peoples R China

Nowadays, wireless LAN has become the most widely deployed technology in mobile devices for providing Internet access. Operators and service providers remarkably increase the density of wireless access points in order to provide their subscribers with better connectivity and user experience. As a result, WLAN users usually find themselves covered by multiple access points and have to decide which one to associate with. In traditional implementations, most wireless stations would select the access point with the strongest signal, regardless of traffic load on that access point, which might result in heavy congestion and unfair load. In this paper, we propose a novel on-line association algorithm to deal with any sequence of STAs during a long-term time such as one day. the performance of our algorithm is evaluated through simulation and experiments. Simulation results show that our algorithm improves the overall WLAN throughput by up to 37%, compared with the conventional RSSI-based approach. Our algorithm also performs better than SSF (Strongest Signal First) and LAB (Largest Available Bandwidth) in the experiments.

关键词： on-line algorithm Competitive ratio Association algorithm Wireless LAN

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：