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

A clique-based online algorithm for constructing optical orthogonal codes

APPLIED SOFT COMPUTING 2016年第0期47卷 21-32页

作者： Zhang, Yuan Peng, Mao Yang, Shengxiang Nanjing Univ Informat Sci & Technol Sch Math & Stat Nanjing 210044 Jiangsu Peoples R China De Montfort Univ Sch Comp Sci & Informat CCI Leicester LE1 9BH Leics England

An optical orthogonal code (OOC) is a family of binary sequences with good auto- and cross-correlation properties. In the literature, various mathematical tools have been used to construct OOCs with specific parameters. But, to find a complete solution for constructing OOCs with an arbitrary setting of parameters is still difficult at the moment. In this paper, a clique-based online algorithm is proposed to construct OOCs of relatively large sizes. In the proposed algorithm, the construction of OOCs is reduced to the maximum clique problem based on specially generated graphs, where vertices represent the codewords of an OOC and edges represent the cross-correlation relationships between codeword pairs. In order to overcome the limitation of computer memory for storing large graphs, part of the graph vertices are supposed to arrive sequentially to be fed into the proposed algorithm, and a specially designed evolutionary algorithm is used to find the maximum clique of the current graph when new vertices arrive. The proposed algorithm does not use parameter-specific techniques and hence can be used for different code weight and correlation constraints. Experiments show that the proposed algorithm outperforms an offline evolutionary algorithm with guided mutation on constructing OOCs. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Optical orthogonal codes Evolutionary algorithm Maximum clique problem online algorithm

来源：评论

学校读者我要写书评

暂无评论

An optimal online algorithm for single-processor scheduling problem with learning effect

引用

THEORETICAL COMPUTER SCIENCE 2022年 928卷 1-12页

作者： Ma, Ran Guo, Sainan Zhang, Xiaoyan Qingdao Univ Technol Sch Management Engn Qingdao 266525 Peoples R China Nanjing Normal Univ Sch Math Sci Nanjing 210023 Peoples R China Nanjing Normal Univ Inst Math Nanjing 210023 Peoples R China

This paper deals with the canonical single-processor online scheduling problem with the position-based learning effect. Specially speaking, a round of jobs arriving online over time will be processed on a single processor. Noticeably, in this model, for each job Jk, the actual processing time pkl is defined as a power function of its position l, i.e., pkl = pkl/3, where pk indicates its normal processing time and beta <= 0 is the learning index. Our goal is to make the sum of completion times as small as possible. For this problem, we testify that there is no online algorithm with a competitive ratio of less than 2. Most notably, we design an online algorithm entitled as Delayed Shortest Normal Processing Time (DSNPT), matching the lower bound proposed by us, and hence DSNPT is optimal.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Scheduling online algorithm Learning effect Position-based Single processor

来源：评论

学校读者我要写书评

暂无评论

New online algorithm for dynamic speed scaling with sleep state

引用

THEORETICAL COMPUTER SCIENCE 2015年 593卷 79-87页

作者： Kumar, Gunjan Shannigrahi, Saswata Indian Inst Technol Guwahati Dept Comp Sci & Engn Gauhati Assam India

We consider an energy-efficient scheduling problem where n jobs J(1), J(2), ..., J(n) in need to be executed such that the total energy usage by these jobs is minimized while ensuring that each job is finished within its deadline. The processor executing these jobs can be in either active or sleep state at any point of time. The speed of the processor in an active state can be arbitrary. If the processor is running at a speed s >= 0, the required power P(s) is assumed to be equal to s(alpha) + g where alpha > 1, g > 0 are constants. On the other hand, the required power is zero when the processor is in the sleep state. However, L > 0 amount of wake-up energy is needed to wake-up the processor from the sleep state to the active state. In this paper, we work in an online setting where a job is known only at its arrival time, along with its processing volume and deadline. In such a setting, the currently best-known algorithm by Han et al. (2010) [3] provides a competitive ratio max{4, 2 + alpha(alpha)} of energy usage. We present a new online algorithm SqOA which provides a competitive ratio max{4, 2 + (2 - 1/alpha)(alpha)2(alpha-1)} of energy usage. For alpha >= 2.34, the competitive ratio of our algorithm is better than that of any other existing algorithm for this problem. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Energy efficient algorithm online algorithm Scheduling algorithm

来源：评论

学校读者我要写书评

暂无评论

A near-optimal memoryless online algorithm for FIFO buffering two packet classes

引用

THEORETICAL COMPUTER SCIENCE 2013年 497卷 164-172页

作者： Li, Fei George Mason Univ Dept Comp Sci Fairfax VA 22030 USA

We consider scheduling packets with values in a capacity-bounded buffer in an online setting. In this model, there is a buffer with limited capacity B. At any time, the buffer cannot accommodate more than B packets. Packets arrive overtime. Each packet has a non-negative value. Packets leave the buffer only because they are either sent or dropped. Those packets that have left the buffer will not be reconsidered for delivery any more. In each time step, at most one packet in the buffer can be sent. The order in which the packets are sent should comply with the order of their arrival time. The objective is to maximize the total value of the packets sent in an online manner. In this paper, we study a variant of this FIFO buffering model in which a packet's value is either 1 or alpha > 1. We present a deterministic memoryless 1.304-competitive algorithm. This algorithm has the same competitive ratio as the one presented in Lotker and Patt-Shamir [Z. Lotker, B. Patt-Shamir, Nearly optimal FIFO buffer management for DiffServ, in: Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing, PODC, 2002, pp. 134-142;Z. Lotker, B. Patt-Shamir, Nearly optimal FIFO buffer management for DiffServ, Computer Networks 17 (1) (2003) 77-89]. However, our algorithm is simpler and does not employ any marking bits. The idea used in our algorithm is novel and different from all previous approaches that have been applied for the general model and its variants. We do not proactively preempt one packet when a new packet arrives. Instead, we may preempt more than one 1-value packet at the time when the buffer contains sufficiently many alpha-value packets. (C) 2011 Elsevier B.V. All rights reserved.

关键词： online algorithm Competitive analysis Buffer management Packet scheduling

来源：评论

学校读者我要写书评

暂无评论

An online algorithm for optimally releasing multiple on-demand instances in IaaS clouds

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2022年 136卷 311-321页

作者： Song, Xurui Pan, Li Liu, Shijun Shandong Univ Sch Software Jinan Peoples R China

With the popularity of cloud computing increasing rapidly in recent years, the use of cloud, represented by IaaS and SaaS, is being embraced by more and more users. One of the flexibility of the cloud lies in its pay-as-you-go usage model, which allows users to purchase and release cloud instances on their own demand, reducing the possible financial loss caused by wasted resources. For a SaaS provider that uses the pay-as-you-go payment model to purchase cloud instances, it is important to make a reasonable decision on when to release as many as idle on-demand cloud instances to achieve cost savings when the number of incoming user demands is in a declining phase, taking into account the cost of the start-up time to acquire new cloud instances and the penalty cost that may be incurred while SaaS users wait. In order to make optimal decisions when there is not enough knowledge to predict the future trend of incoming demands, we propose an online instance releasing algorithm which can effectively help SaaS providers to reduce the cost when using on-demand instances. Through theoretical analysis we show our online algorithm can achieve a competitive ratio of less than 2 for a variety of penalty functions. Our extensive simulation experiments based on both real Google workload data and simulated demand sequences demonstrate that the proposed online algorithm is stable and efficient.

关键词： Cloud computing Cost optimization online algorithm IaaS instance releasing Competitive analysis Cost management

来源：评论

学校读者我要写书评

暂无评论

A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints

引用

THEORETICAL COMPUTER SCIENCE 2012年 457卷 174-180页

作者： Yuan, Junling Li, Wenhua Yuan, Jinjiang Zhengzhou Univ Dept Math Zhengzhou 450001 Henan Peoples R China Univ Sci & Technol Beijing Sch Comp & Commun Engn Beijing 10008 Peoples R China

We consider the online scheduling on two identical parallel machines with chain precedence constraints to minimize makespan, where jobs arrive over time and have identical processing times. For this online scheduling problem, Huo and Leung [Y. Huo and J.Y.-T. Leung, online scheduling of precedence constrained tasks, SIAM Journal on Computing, 34 (2005), 743-762] proved that it is impossible to have an online algorithm of a competitive ratio 1. We provide a best possible online algorithm of competitive ratio root 13-1/2. (C) 2012 Elsevier B.V. All rights reserved.

关键词： online algorithm Parallel-machine scheduling Equal-length jobs Chain precedence constraints Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

An Optimal online algorithm for Scheduling on Two Parallel Machines with GoS Eligibility Constraints

引用

Journal of the Operations Research Society of China 2016年第3期4卷 371-377页

作者： Jia Xu Zhao-Hui Liu Department of Mathematics East China University of Science and TechnologyShanghai 200237China

We consider the online scheduling problem on two parallel machines with the Grade of Service(GoS)eligibility *** jobs arrive over time,and the objective is to minimize the *** develop a(1+α)-competitive optimal algor... 详细信息

关键词： Scheduling Parallel machine Eligibility constraint online algorithm

来源：评论

学校读者我要写书评

暂无评论

An online algorithm for Least-Square Spectral Analysis: Applied to Time-Frequency Analysis of Heart Rate 37

An Online Algorithm for Least-Square Spectral Analysis: Appl...

引用

37th Annual International Conference of the IEEE-Engineering-in-Medicine-and-Biology-Society (EMBC)

作者： Zhang, Zhe Leong, Philip H. W. Univ Sydney Dept Elect & Informat Engn Sydney NSW 2006 Australia

ISBN: (纸本)9781424492701

We propose a novel online algorithm for computing least-square based periodograms, otherwise known as the Lomb-Scargle Periodogram. Our spectral analysis technique has been shown to be superior to traditional discrete Fourier transform (DFT) based methods, and we introduce an algorithm which has O(N) time complexity per input sample. The technique is suitable for real-time embedded implementations and its utility is demonstrated through an application to the high resolution time-frequency domain analysis of heart rate variability (HRV).

关键词： cardiology discrete Fourier transforms least squares approximations spectral analysis time-frequency analysis DFT based methods HRV Lomb-Scargle periodogram discrete Fourier transform based methods heart rate variability high resolution time-frequency domain analysis least-square based periodograms least-square spectral analysis online algorithm real-time embedded implementations time complexity per input sample algorithm design and analysis Discrete Fourier transforms Heart rate variability Spectral analysis Time-frequency analysis Yttrium

来源：评论

学校读者我要写书评

暂无评论

online algorithm for data retrieval with multiple antennae in wireless communication

引用

INTERNATIONAL JOURNAL OF SENSOR NETWORKS 2019年第2期31卷 78-89页

作者： He, Ping Li, Weidong Cao, Shufu Ma, Siyuan Shi, Kaihua Hebei Univ Econ & Business Inst Informat Technol Shijiazhuang 050000 Hebei Peoples R China Shijiazhuang Business Bur Shijiazhuang 050000 Hebei Peoples R China

Given a set of requested data items and a set of multiple channels, online multi-antennae data retrieval problem (OMAP) is to download all requested data items from these channels when the clients are equipped with multiple antennae and do not know any a-prior knowledge of wireless data broadcast system, such that the total access latency is minimised and the access latency among all antennae keeps balance. So this paper proposes online multiple antennae data retrieval algorithm based on requested ratio (OMR) and online multiple antennae retrieval algorithm for equal data items based on unretrieved ratio (OMU) that introduces the requested ratio and unretrieved ratio respectively when the length of data items is equal. In addition, when the length of data items is unequal, the paper proposes online multiple antennae retrieval algorithm for unequal data items based on length ratio (OML) that introduces the length to compute the length ratio. Finally, we analyse the competitive rates of three algorithms. Through experiments, the proposed schemes can have currently better efficiency by comparing with some existing schemes and solve OMAP.

关键词： mobile computing wireless communication data retrieval multiple antennae online algorithm

来源：评论

学校读者我要写书评

暂无评论

Constraint Projection Adaptive Natural Gradient online algorithm for SVM

Constraint Projection Adaptive Natural Gradient Online Algor...

引用

International Conference on Manufacturing Engineering and Automation

作者： Sun, Zonghai S China Univ Technol Coll Automat Sci & Engn Guangzhou 510640 Guangdong Peoples R China

ISBN: (纸本)9780878492268

The training of Support Vector Machine (SVM) is an optimization problem of quadratic programming which can not be applied to the online training in real time applications or time-variant data source. The online algorithms proposed by other researchers have high computational complexity and slow training speed, which can not be well applied to the time-variant problems as well. In this paper the projection gradient and adaptive natural gradient is combined. The constraint projection adaptive natural gradient online algorithm for SVM is proposed. The computation complexity of the constraint projection adaptive natural gradient algorithm is O(L(2)). The learning performance is compared via prediction of the concentration of component A of Continuous Stirred Tank Reactor. The results of simulation demonstrate that the time taken by the constraint projection adaptive natural gradient online algorithm for SVM is far less than that of incremental algorithm, while keep higher prediction precision.

关键词： Natural Gradient online algorithm Projection Support Vector Machine

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：