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

Tight online conflict-free coloring of intervals

SCIENTIA IRANICA 2021年第3期28卷 1493-1496页

作者： Abam, M. A. Sharif Univ Technol Dept Comp Engn Tehran Iran

This study revisited the problem of online conflict-free coloring of intervals on a line, where each newly inserted interval must be assigned a color upon insertion such that the coloring remains conflict-free, i.e., for each point p in the union of the current intervals, there must be an interval I with a unique color among all intervals covering p. The best-known algorithm uses O(log(3) n) colors, where n is the number of current intervals. A simple greedy algorithm was presented that used only O(log n) colors. Therefore, the open problem raised in [Abam, M.A., Rezaei Seraji, M.J., and Shaxlravan, M. "Online conflict-free coloring of intervals", Journal of Scientia Iranica, 21(6), pp. 2138-2141 (2014).] was resolved. (C) 2021 Sharif University of Technology. All rights reserved.

关键词： Frequency assignment Conflict-free coloring Intervals on-line algorithms Computational geometry

来源：评论

学校读者我要写书评

暂无评论

Online graph exploration on trees, unicyclic graphs and cactus graphs

引用

INFORMATION PROCESSING LETTERS 2021年 168卷 106096-106096页

作者： Fritsch, Robin Tech Univ Munich Munich Germany

We study the problem of exploring all vertices of an undirected weighted graph that is initially unknown to the searcher. An edge of the graph is only revealed when the searcher visits one of its endpoints. Beginning at some start node, the searcher's goal is to visit every vertex of the graph before returning to the start node on a tour as short as possible. We prove that the Nearest Neighbor algorithm's competitive ratio on trees with n vertices is O(logn), i.e. no better than on general graphs. Furthermore, we examine the algorithm Blocking for a range of parameters not considered previously and prove it is 3-competitive on unicyclic graphs as well as 5/2 + root 2 approximate to 3.91-competitive on cactus graphs. The best known lower bound for these two graph classes is 2. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Graph exploration on-line algorithms Nearest neighbor

来源：评论

学校读者我要写书评

暂无评论

A competitive analysis for the Start-Gap algorithm for online memory wear leveling

引用

INFORMATION PROCESSING LETTERS 2021年 166卷 106042-106042页

作者： Devanny, William E. Goodrich, Michael T. Irani, Sandy Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA Univ Calif Irvine Dept Comp Sci Irvine CA 92697 USA

Erase-limited memory, such as flash memory and phase change memory (PCM), has limitations on the number of times that any memory cell can be erased. The Start-Gap algorithm has shown a significant ability in practice to distribute updates across the cells of an erase-limited memory, but it has heretofore not been characterized in terms of its competitive ratio against an optimal offline algorithm that is given all the update addresses in advance. In this paper, we present a competitive analysis for the Start-Gap wear-leveling algorithm, showing that under reasonable assumptions about the sequence of update operations, the Start-Gap algorithm has a competitive ratio of 1/(1 - o(1)). (C) 2020 Elsevier B.V. All rights reserved.

关键词： Analysis of algorithms Data structures on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Competitive analysis of online revenue management with hierarchical resources

引用

INFORMATION PROCESSING LETTERS 2019年 142卷 41-45页

作者： Ni, Guanqun Zheng, Feifeng Xu, Yinfeng Fujian Agr & Forestry Univ Coll Management Fuzhou 350002 Fujian Peoples R China Donghua Univ Glorious Sun Sch Business & Management Shanghai 200051 Peoples R China

This paper studies an online revenue management problem of accepting and assigning two classes of customers to two levels of resources with capacity constraints. A customer's request may be either accepted or rejected immediately upon its arrival without the information of further demand. One class of customers can be served either by a low-level resource at the resource's regular price, or by a high-level resource at the customer's reservation price. Another class of customers can be served by either level of resource at the regular price of the corresponding resource. Given the capacities of both levels of resources, the objective is to accept appropriate customers and assign them to appropriate resources so as to maximize the total revenue. From the perspective of competitive analysis, we derive an upper bound of competitive ratio for the problem and develop an optimal online strategy whose competitive ratio matches the upper bound. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Revenue management Hierarchical resources on-line algorithms Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Hierarchical Overlap Graph

引用

INFORMATION PROCESSING LETTERS 2020年 155卷 105862-000页

作者： Cazaux, Bastien Rivals, Eric CNRS LIRMM CC 477161 Rue Ada F-34095 Montpellier 5 France Univ Montpellier CC 477161 Rue Ada F-34095 Montpellier 5 France CNRS Inst Biol Computat 860 Rue St Priest F-39095 Montpellier 5 France Univ Montpellier 860 Rue St Priest F-39095 Montpellier 5 France

Given a set of finite words, the Overlap Graph (OG) is a complete weighted digraph where each word is a node and where the weight of an arc equals the length of the longest overlap of one word onto the other (Overlap is an asymmetric notion). The OG serves to assemble DNA fragments or to compute shortest superstrings, which are a compressed representation of the input. The OG requires space that is quadratic in the number of words, which limits its scalability. The Hierarchical Overlap Graph (HOG) is an alternative graph that also encodes all maximal overlaps, but uses space that is linear in the sum of the lengths of the input words. We propose the first algorithm to build the HOG in linear space for words of equal length. (C) 2019 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Superstring Assembly Aho-Corasik Data structures

来源：评论

学校读者我要写书评

暂无评论

on-line algorithms for 2-space bounded 2-dimensional bin packing

引用

INFORMATION PROCESSING LETTERS 2012年第19期112卷 719-722页

作者： Januszewski, Janusz Univ Technol & Life Sci Inst Math & Phys PL-85796 Bydgoszcz Poland

In 2-space bounded model of on-line bin packing, there are 2 active bins, and each item can be packed only into one of the active bins. If it is impossible to pack an item into any active bin, we close one of the current active bins and open a new active bin to pack that item. In 2-space bounded 2-dimensional bin packing problem, each item is a rectangle of side lengths not greater than 1. The items are packed on-line into square bins of size 1 x 1 and 90 degrees-rotations are allowed. In this paper a 4-competitive 2-space bounded 2-dimensional on-line packing algorithm is presented. Furthermore, an on-line strategy with competitive ratio 3.8 is given for 2-space bounded square packing. (C) 2012 Elsevier B.V. All rights reserved.

关键词： on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Balanced allocation through random walk

引用

INFORMATION PROCESSING LETTERS 2018年 131卷 39-43页

作者： Frieze, Alan Petti, Samantha Carnegie Mellon Univ Dept Math Sci Pittsburgh PA 15213 USA Georgia Tech Sch Math Atlanta GA 30313 USA

We consider the allocation problem in which in <= (1 - epsilon)dn items are to be allocated to n bins with capacity d. The items x(1), x(2),..., x(m) arrive sequentially and when item xi arrives it is given two possible bin locations p(i) = h(1)(x(i)), q(i) = h(2)(x(i)) via hash functions h(1), h(2). We consider a random walk procedure for inserting items and show that the expected time insertion time is constant provided epsilon = Omega (root log/d). (C) 2017 Elsevier B.V. All rights reserved.

关键词： Balanced allocation Random walk Cuckoo hashing on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

A risk-reward model with compound interest rate for non-additive two-option ski rental

引用

INFORMATION PROCESSING LETTERS 2018年 135卷 9-13页

作者： Chen, Xiaoli Xu, Weijun South China Univ Technol Sch Business Adm Guangzhou 510641 Guangdong Peoples R China

We consider the non-additive two-option ski rental problem (NTSR), which includes two options such that each Option i (for i = 1, 2) is characterized by a one-time cost bi and a corresponding rental price Without loss of generality, we assume that a(1) > a(2) >= 0 and b(2) > b(1) >= 0. Besides, we have to pay a transition cost c if we switch from Option 1 to Option 2, where c >= b(2) - b(1). We introduce the compound interest rate into the continuous version of NTSR and obtain the optimal deterministic on-line strategy by competitive analysis. Moreover, considering the risk tolerance of decision makers, we present a risk-reward strategy. In addition, we use numerical analysis to analyze the influence of risk tolerance and compound interest rate on the restricted ratio and switching time of the optimal risk-reward strategy. The results demonstrate that the competitive performance is improved when the risk tolerance and compound interest rate are considered. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Compound interest rate Ski rental Risk-reward strategy on-line algorithms Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Fair resource allocation over time 17

Fair resource allocation over time

引用

17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)

作者： Bampis, Evripidis Escoffier, Bruno Mladenovic, Sasa Sorbonne Univ CNRS Lab Informat Paris 6 Paris France

ISBN: (纸本)9781450356497

We consider the over-time version of the MAX-MIN FAIR ALLOCATION problem. Given a time horizon t = 1, 2,..., T, with at each time t a set of demands and a set of available resources that may change over the time defining instance I-t, we seek a sequence of solutions S-1, S-2,, S-T that (1) are near-optimal at each time t, and (2) as stable as possible (inducing small modification costs). We focus on the impact of the knowledge of the future on the quality and the stability of the returned solutions by distinguishing three settings: the off-line setting where the whole set of instances through the time horizon is known in advance, the on-line setting where no future instance is known, and the k-lookahead setting where at time t, the instances at times t + 1,, t + k are known. We first consider the case without restrictions where the set of resources and the set of agents are the same for all instances and where every resource can be allocated to any agent. For the off-line setting, we show that the over-time version of the problem is much harder than the static one, since it becomes NP-hard even for families of instances for which the static problem is trivial. Then, we provide a rho/rho+1-approximation algorithm for the off-line setting using as subroutine a rho-approximation algorithm for the static version. We also give a rho/rho+1-competitive algorithm for the online setting using also as subroutine a p-approximation algorithm for the static version. Furthermore, for the case with restrictions, we show that in the off-line setting it is possible to get a polynomial-time algorithm with the same approximation ratio as in the case without restrictions. For the online setting, we prove that it is not possible to find an online algorithm with bounded competitive ratio. For the 1-lookahead setting however, we give a rho/2(2 rho +1) approximation algorithm using as subroutine a rho-approximation algorithm for the static version.

关键词： Resource allocation fairness Santa Claus approximation algorithms on-line algorithms scheduling

来源：评论

学校读者我要写书评

暂无评论

ODR: On-line Delay Reduction Approach for Transferring Dynamically-Generated Big Flows Leveraging Software-Defined Networks

ODR: On-line Delay Reduction Approach for Transferring Dynam...

引用

IEEE International Conference on Electro/Information Technology (EIT)

作者： Rahamneh, Samah Sawalha, Lina Western Michigan Univ Dept Elect & Comp Engn Kalamazoo MI 49008 USA

ISBN: (纸本)9781538653982

Data analytics techniques are changing the way businesses address core activities like planning, performance evaluation, and decision making. Recently, greater insights are reached as a result of applying such techniques to sets of data growing in diverse dimensions (big data). This attracted extensive research efforts to tackle big data transfer, processing, and storage challenges. Despite being similar in purpose to typical data transfer through the network, big data transfer poses significant changes. These changes warrant a new look at the techniques being used not limited to simple bandwidth increase. In this paper, we propose and implement an on-line algorithm to minimize the delay experienced by near real-time dynamically generated big data flows when traveling through diverse networks leveraging Software Defined Networking (SDN). The algorithm exploits a comprehensive network view and statistics gathered by SDN controller to move big flows adaptively. The objective function is to minimize the network delay constrained to Service Level Agreement (SLA), in addition to network status. The proposed On-line Delay Reduction (ODR) approach outperforms the de facto Equal Cost Multi-Path (ECMP) algorithm with 19% to 24% reduction in delay.

关键词： Big Data SDN on-line algorithms Network Optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：