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

Bin-Packing-Based online Dynamic Bandwidth and Wavelength Allocation algorithm in Super-PON

IEEE ACCESS 2021年 9卷 139379-139392页

作者： Garg, Sukriti Dixit, Abhishek Bharti Sch Telecommun Technol & Management Indian Inst Technol Delhi New Delhi 110016 India

Super passive optical network (Super-PON) is a next-generation Ethernet PON (NG-EPON) candidate that is envisaged to provide high data rate and low latency. For NG-EPON, there are two types of algorithms that manages bandwidth and wavelength scheduling, namely offline and online. The latter method is more scalable and efficient than the former method. Several online algorithms exist that propose schemes to manage wavelength and bandwidth scheduling. However, these algorithms lack in efficient wavelength utilization and switching. In this work, we propose a novel online bin-packing based dynamic bandwidth and wavelength allocation (DBWA) algorithm for Super-PON, namely updated best fit bin-packing (UBF-BP). This algorithm limits the wavelength switching per cycle, and uses the modified version of best fit bin-packing (BF-BP) technique for optimal wavelength allocation. Simulation results show that the proposed DBWA algorithm has a low complexity and overcomes the inefficiencies of wavelength utilization and switching. This results in lower network delay and higher channel utilization than the state-of-the-art DBWA. Furthermore, to verify the correctness of the proposed algorithm, we propose an analytical model and validate these simulation results with the analytical results.

关键词： Optical network units Heuristic algorithms Delays Bandwidth Resource management Prediction algorithms Passive optical networks Bin-packing DBWA delay analysis NG-EPON online algorithm super-PON

来源：评论

学校读者我要写书评

暂无评论

An Optimal Preemptive algorithm for online MapReduce Scheduling on Two Parallel Machines

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2018年第3期35卷 1850013.1-1850013.1页

作者： Jiang, Yiwei Zhou, Wei Zhou, Ping Zhejiang Congshang Univ Contemporary Business & Trade Res Ctr Sch Management & E Business Hangzhou 310018 Zhejiang Peoples R China Zhejiang Sci Tech Univ Dept Math Hangzhou 310018 Zhejiang Peoples R China Zhejiang Business Coll Coll Humanities Hangzhou 310053 Zhejiang Peoples R China

In this paper, we study an online scheduling on two parallel machines in MapReduce-like system where each job contains two kinds of tasks: map tasks and reduce tasks. A job's reduce tasks can only be processed after all its map tasks are finished. We assume that the map tasks are fractional and the reduce tasks are preemptive. Our objective is to minimize makespan. We show that the lower bound for this MapReduce scheduling problem is root 2. We then present an online algorithm with competitive ratio of root 2 and thus it is optimal.

关键词： MapReduce online algorithm competitive ratio makespan

来源：评论

学校读者我要写书评

暂无评论

A design framework for online algorithms solving the object replacement problem

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2001年第9期E84D卷 1135-1143页

作者： Tani, S Miyazaki, T Nippon Telegraph & Tel Corp Network Innovat Labs Yokosuka Kanagawa 2390847 Japan

Network caches reduce network traffic as well as user response time. When implementing network caches, the object replacement problem is one of the core problems;The problem is to determine which objects should be evicted from a cache when there is insufficient space. This paper first formalizes the problem and gives a simple but sufficient condition for deterministic online algorithms to be competitive. Based on the condition, a general framework to make a non-competitive algorithm competitive is constructed. As an application of the framework, an online algorithm, called Competitive-SIZE, is proposed. Both event-driven and trace-driven simulations show that Competitive-SIZE is better than previously proposed algorithms such as LRU (Least Recently Used).

关键词： network cache competitive online algorithm

来源：评论

学校读者我要写书评

暂无评论

Best-Possible online algorithms for Single Machine Scheduling to Minimize the Maximum Weighted Completion Time

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2018年第6期35卷

作者： Chai, Xing Lu, Lingfa Li, Wenhua Zhang, Liqi Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China Henan Agr Univ Coll Informat & Management Sci Zhengzhou 450003 Henan Peoples R China

In this paper, we consider the online single machine scheduling problem to minimize the maximum weighted completion time of the jobs. For the preemptive problem, we show that the LW (Largest Weight first) rule yields an optimal schedule. For the non-preemptive problem, Li [Li, W (2015). A best possible online algorithm for the parallel-machine scheduling to minimize the maximum weighted completion time. Asia-Pacific Journal of Operational Research, 32(4), 1550030 (10 pages)] presented a lower bound 2, and then provided an online algorithm with a competitive ratio of 3. In this paper, we present two online algorithms with the best-possible competitive ratio of 2 for the non-preemptive problem.

关键词： Scheduling online algorithm best-possible competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Linear time online algorithms for constructing linear-size suffix trie

引用

THEORETICAL COMPUTER SCIENCE 2024年 1015卷

作者： Hendrian, Diptarama Takagi, Takuya Inenaga, Shunsuke Goto, Keisuke Funakoshi, Mitsuru Tohoku Univ Grad Sch Informat Sci Sendai Japan Fujitsu Labs Ltd Kawasaki Japan Kyushu Univ Dept Informat Fukuoka Japan Tokyo Med & Dent Univ M&D Data Sci Ctr Tokyo Japan NTT Commun Sci Labs Kyoto Japan

The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a text string T of length n has O(n) nodes and edges, and the string label of each edge is encoded by a pair of positions in T. Thus, even after the tree is built, the input string.. needs to be kept stored and random access to T is still needed. The linear-size suffix tries (LSTs), proposed by Crochemore et al. [Linear-size suffix tries, TCS 638:171-178, 2016], are a "stand-alone" alternative to the suffix trees. Namely, the LST of an input text string T of length n occupies O(n) total space, and supports pattern matching and other tasks with the same efficiency as the suffix tree without the need to store the input text string T. Crochemore et al. proposed an offline algorithm which transforms the suffix tree of T into the LST of T in O(n log sigma) time and O(n) space, where sigma is the alphabet size. In this paper, we present two types of online algorithms which "directly" construct the LST, from right to left, and from left to right, without constructing the suffix tree as an intermediate structure. Both algorithms construct the LST incrementally when a new symbol is read, and do not access the previously read symbols. Both of the right-to-left construction algorithm and the left-to-right construction algorithm work in O(n log sigma) time and O(n) space. The main feature of our algorithms is that the input text string does not need to be stored.

关键词： Indexing structure Linear-size suffix trie online algorithm Pattern matching Nearest marked ancestor

来源：评论

学校读者我要写书评

暂无评论

online Kernel Principal Component Analysis: A Reduced-Order Model

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2012年第9期34卷 1814-1826页

作者： Honeine, Paul Univ Technol Troyes Inst Charles Delaunay Lab Modelisat & Surete Syst CNRSUMR 6279 F-10010 Troyes France

Kernel principal component analysis (kernel-PCA) is an elegant nonlinear extension of one of the most used data analysis and dimensionality reduction techniques, the principal component analysis. In this paper, we propose an online algorithm for kernel-PCA. To this end, we examine a kernel-based version of Oja's rule, initially put forward to extract a linear principal axe. As with most kernel-based machines, the model order equals the number of available observations. To provide an online scheme, we propose to control the model order. We discuss theoretical results, such as an upper bound on the error of approximating the principal functions with the reduced-order model. We derive a recursive algorithm to discover the first principal axis, and extend it to multiple axes. Experimental results demonstrate the effectiveness of the proposed approach, both on synthetic data set and on images of handwritten digits, with comparison to classical kernel-PCA and iterative kernel-PCA.

关键词： Principal component analysis online algorithm machine learning reproducing kernel Oja's rule recursive algorithm

来源：评论

学校读者我要写书评

暂无评论

Competitiveness of Dynamic Bin Packing for online Cloud Server Allocation

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2017年第3期25卷 1324-1331页

作者： Ren, Runtian Tang, Xueyan Li, Yusen Cai, Wentong Nanyang Technol Univ Sch Comp Sci & Engn Singapore 639798 Singapore Nankai Univ Dept Comp Sci & Secur Tianjin Peoples R China

Cloud-based systems often face the problem of dispatching a stream of jobs to run on cloud servers in an online manner. Each job has a size that defines the resource demand for running the job. Each job is assigned to run on a cloud server upon its arrival and the job departs after it completes. The departure time of a job, however, is not known at the time of its arrival. Each cloud server has a fixed resource capacity and the total resource demand of all the jobs running on a server cannot exceed its capacity at all times. The objective of job dispatching is to minimize the total cost of the servers used, where the cost of renting each cloud server is proportional to its running hours by "pay-as-you-go" billing. The above job dispatching problem can be modeled as a variant of the dynamic bin packing (DBP) problem known as MinUsageTime DBP. In this paper, we study the competitiveness bounds of MinUsageTime DBP. We establish an improved lower bound on the competitive ratio of Any Fit family of packing algorithms, and a new upper bound of mu+3 on the competitive ratio of the commonly used First Fit packing algorithm, where mu is the max/min job duration ratio. Our result significantly reduces the gap between the upper and lower bounds for the MinUsageTime DBP problem to a constant value independent of mu, and shows that First Fit packing is near optimal for MinUsageTime DBP.

关键词： Dynamic bin packing online algorithm competitive ratio cloud server allocation

来源：评论

学校读者我要写书评

暂无评论

Asymptotic Approximation Ratios for Certain Classes of online Bin Packing algorithms

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2021年第3期E104D卷 362-369页

作者： Fujiwara, Hiroshi Wanikawa, Yuta Yamamoto, Hiroaki Shinshu Univ Dept Elect & Comp Engn Nagano 3808553 Japan VOYAGE GRP Inc Tokyo Japan

The performance of online algorithms for the bin packing problem is usually measured by the asymptotic approximation ratio. However, even if an online algorithm is explicitly described, it is in general difficult to obtain the exact value of the asymptotic approximation ratio. In this paper we show a theorem that gives the exact value of the asymptotic approximation ratio in a closed form when the item sizes and the online algorithm satisfy some conditions. Moreover, we demonstrate that our theorem serves as a powerful tool for the design of online algorithms combined with mathematical optimization.

关键词： bin packing problem online algorithm competitive analysis mathematical optimization

来源：评论

学校读者我要写书评

暂无评论

SOAR: Smart online Aggregated Reservation for Mobile Edge Computing Brokerage Services

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2023年第1期22卷 527-540页

作者： Zang, Shizhe Bao, Wei Yeoh, Phee Lep Vucetic, Branka Li, Yonghui Univ Sydney Fac Engn & Informat Technol Sch Elect & Informat Engn Sydney NSW 2006 Australia Univ Sydney Fac Engn & Informat Technol Sch Comp Sci Sydney NSW 2006 Australia

With the development of MEC services, MEC brokers will emerge to facilitate the purchase and management of resources for individual MEC users. Both data communication and computing resources offered by MEC service providers can be purchased by pay-as-you-go (PAYG) or reserved plans. Besides data and computing plans for each type of resource, we also consider combo plans specifically designed for MEC services covering both resources. In this paper, we propose a smart online aggregated reservation (SOAR) framework for MEC brokers to minimize their cost of reserving resources for multiple users without the knowledge of future demands. In our framework, a task aggregation algorithm is designed to aggregate the users' demands in each PAYG billing cycle to improve the plan utilization, and plan reservation algorithms are proposed to decide when to reserve which plans. The performance gap (competitive ratio) between SOAR and optimal solution which knows all future demands in advance, is analyzed and derived in closed-form. The performance gap is proved to be the minimum among all deterministic online algorithms. Trace-driven simulations verify the cost advantage of our SOAR framework, which can save nearly 40 percent of cost for users through the brokerage service.

关键词： Mobile edge computing resource reservation resource brokerage competitive analysis online algorithm

来源：评论

学校读者我要写书评

暂无评论

Near-optimal stochastic approximation for online principal component estimation

引用

MATHEMATICAL PROGRAMMING 2018年第1期167卷 75-97页

作者： Li, Chris Junchi Wang, Mengdi Liu, Han Zhang, Tong Princeton Univ Dept Operat Res & Financial Engn Princeton NJ 08544 USA Rutgers State Univ Dept Stat Piscataway NJ 08854 USA

Principal component analysis (PCA) has been a prominent tool for high-dimensional data analysis. online algorithms that estimate the principal component by processing streaming data are of tremendous practical and theoretical interests. Despite its rich applications, theoretical convergence analysis remains largely open. In this paper, we cast online PCA into a stochastic nonconvex optimization problem, and we analyze the online PCA algorithm as a stochastic approximation iteration. The stochastic approximation iteration processes data points incrementally and maintains a running estimate of the principal component. We prove for the first time a nearly optimal finite-sample error bound for the online PCA algorithm. Under the subgaussian assumption, we show that the finite-sample error bound closely matches the minimax information lower bound.

关键词： Principal component analysis Stochastic approximation Nonconvex optimization Stochastic gradient method High-dimensional data online algorithm Finite-sample analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：