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

Online call control in cellular networks revisited

INFORMATION PROCESSING LETTERS 2012年第1-2期112卷 21-25页

作者： Zhang, Yong Chin, Francis Y. L. Ting, Hing-Fung Chan, Joseph Wun-Tat Han, Xin Lam, Ka-Cheong Hebei Univ Coll Math & Comp Sci Tianjin Peoples R China Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Hong Kong Baptist Univ Coll Int Educ Hong Kong Hong Kong Peoples R China Dalian Univ Technol Sch Software Dalian Peoples R China Chinese Univ Hong Kong Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China

Wireless communication networks based on frequency division multiplexing (FDM in short) play an important role in the field of communications, in which each request can be satisfied by assigning a frequency. To avoid interference, each assigned frequency must be different from the neighboring assigned frequencies. Since frequencies are scarce resources, the main problem in wireless networks is how to fully utilize the given bandwidth of frequencies. In this paper, we consider the online call control problem. Given a fixed bandwidth of frequencies and a sequence of communication requests arriving over time, each request must be either satisfied immediately after its arrival by assigning an available frequency, or rejected. The objective of the call control problem is to maximize the number of accepted requests. We study the asymptotic performance of this problem, i.e., the number of requests in the sequence and the bandwidth of frequencies are very large. In this paper, we give a 7/3-competitive algorithm, say CACO, for the call control problem in cellular networks, improving the previous 2.5-competitive result, and show that CACO is best possible among a class of HYBRID algorithms. (C) 2011 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Call control problem Cellular networks

来源：评论

学校读者我要写书评

暂无评论

Effective on-line algorithms for reliable due date quotation and large-scale scheduling

引用

JOURNAL OF SCHEDULING 2008年第3期11卷 187-204页

作者： Kaminsky, Philip Lee, Zu-Hsu Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA 94720 USA Montclair State Univ Dept Management & Informat Syst Montclair NJ 07043 USA

We consider the sequencing of a series of jobs that arrive at a single processor over time. At each job's arrival time, a due date must be quoted for the job, and the job must complete processing before its quoted due date. The objective is to minimize the sum (or average) of quoted due dates, or equivalently, the average quoted lead time. In this paper, we propose on-line heuristics for this problem and characterize the conditions under which these heuristics are asymptotically optimal. Computational testing further demonstrates the relative effectiveness of these heuristics under various conditions.

关键词： due date quotation scheduling on-line algorithms asymptotic analysis probabilistic analysis

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Offline file assignments for online load balancing

引用

INFORMATION PROCESSING LETTERS 2011年第4期111卷 178-183页

作者： Duetting, Paul Henzinger, Monika Weber, Ingmar Yahool Res Barcelona E-08003 Barcelona Spain Ecole Polytech Fed Lausanne Stn 14 CH-1015 Lausanne Switzerland Univ Vienna Fac Comp Sci A-1090 Vienna Austria

We study a novel load balancing problem that arises in web search engines. The problem is a combination of an offline assignment problem, where files need to be (copied and) assigned to machines, and an online load balancing problem, where requests ask for specific files and need to be assigned to a corresponding machine, whose load is increased by this. We present simple deterministic algorithms for this problem and exhibit an interesting trade-off between the available space to make file copies and the obtainable makespan. We also give non-trivial lower bounds for a large class of deterministic algorithms and present a randomized algorithm that beats these bounds with high probability. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Load balancing on-line algorithms Information retrieval File distribution

来源：评论

学校读者我要写书评

暂无评论

Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines

引用

COMPUTERS & OPERATIONS RESEARCH 2011年第8期38卷 1103-1108页

作者： Krumke, Sven O. Taudes, Alfred Westphal, Stephan Univ Kaiserslautern Dept Math D-67653 Kaiserslautern Germany Vienna Univ Econ & Business Adm Inst Prod Management Vienna Austria

We consider the problem of scheduling a maximum profit selection of equal length jobs on m identical machines. Jobs arrive online over time and the goal is to determine a non-preemptive schedule which maximizes the total profit of the scheduled jobs. Let the common processing requirement of the jobs be p > 0. For each job j(i), i = 1,...,n we are given a release time r(i) (at which the job becomes known) and a deadline r(i)+p+delta(i). If the job is scheduled and completed before the deadline, a profit of w(i) is earned. Upon arrival of a new job, an online algorithm must decide whether to accept the job or not. In case of acceptance, the online algorithms must provide a feasible starting date for the job. Competitive analysis has become a standard way of measuring the quality of online algorithms. For a maximization problem, an online algorithm is called c-competitive, if on every input instance it achieves at least a 1/c-fraction of the optimal ("offline") profit. We give lower bounds for the competitivity of online algorithms and propose algorithms which match this lower bound up to a constant factor. (C) 2010 Published by Elsevier Ltd.

关键词： Revenue management Scheduling on-line algorithms Competitiveness

来源：评论

学校读者我要写书评

暂无评论

A risk-reward model for the on-line leasing of depreciable equipment

引用

INFORMATION PROCESSING LETTERS 2011年第6期111卷 256-261页

作者： Zhang, Yong Zhang, Weiguo Xu, Weijun Li, Hongyi S China Univ Technol Sch Business Adm Guangzhou 510640 Guangdong Peoples R China Chinese Univ Hong Kong Fac Business Adm Shatin Hong Kong Peoples R China

The optimal deterministic strategy for the on-line leasing of depreciable equipment is presented here for cases with and without an interest rate. A risk-reward model in which the on-line investor can develop optimal strategies based on his/her risk tolerance and forecast is discussed. Numerical analysis shows that the competitive performance is significantly improved in the proposed model. (C) 2010 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Risk-reward model Depreciable equipment

来源：评论

学校读者我要写书评

暂无评论

A SURVEY ON COMBINATORIAL OPTIMIZATION IN DYNAMIC ENVIRONMENTS

引用

RAIRO-OPERATIONS RESEARCH 2011年第3期45卷 241-294页

作者： Boria, Nicolas Paschos, Vangelis T. CNRS LAMSADE UMR 7243 F-75775 Paris 16 France Univ Paris 09 F-75775 Paris France

This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The second framework is probabilistic optimization, where the instance to optimize is not fully known at the time when a solution is to be proposed, but results from a determined Bernoulli process. Then, the goal is to compute a solution with optimal expected value.

关键词： Approximation reoptimization hereditary problem complexity graph on-line algorithms probabilistic optimization

来源：评论

学校读者我要写书评

暂无评论

The ski-rental problem with multiple discount options

引用

INFORMATION PROCESSING LETTERS 2011年第18期111卷 903-906页

作者： Zhang, Guiqing Poon, Chung Keung Xu, Yinfeng Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China City Univ Hong Kong Hong Kong Hong Kong Peoples R China Minist Educ Key Lab Intelligent Networks & Network Secur Xian 710049 Peoples R China

We propose the ski-rental problem with multiple discount options in which there are n options to rent an equipment. Every option has a rental duration;the longer the duration, the more the discount. This generalizes the standard ski-rental problem where one can only rent or buy. We present a 4-competitive on-line algorithm for our problem and show that no deterministic algorithm can have a smaller competitive ratio when n is large enough. Comparing with the original ski-rental problem, the competitive ratio becomes larger when there are more options. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Ski-rental problem Multiple options on-line algorithms Competitive analysis Lower bound

来源：评论

学校读者我要写书评

暂无评论

Composite Iterative Algorithm and Architecture for q-th Root Calculation

Composite Iterative Algorithm and Architecture for <i>q</i>-...

引用

20th IEEE Symposium on Computer Arithmetic (ARITH)

作者： Vazquez, Alvaro Bruguera, Javier D. INRIA CNRS ENSL INRIA UCBL Lab LIP Paris France Univ Santiago de Compostela Ctr Invest Tecnol Informac Dept Elect & Comp Sci Santiago Spain

ISBN: (纸本)9780769543185

An algorithm for the q-th root extraction, q being any integer, is presented in this paper. The algorithm is based on an optimized implementation of X-1/q = 2((1/q) log2(X)) by a sequence of parallel and/or overlapped operations: (1) reciprocal, (2) digit-recurrence logarithm, (3) left-to-right carry-free multiplication and (4) on-line exponential. A detailed error analysis and two architectures are proposed, for low precision q and for higher precision q. The execution time and hardware requirements are estimated for single precision floating-point computations for several radices;this helps to determine which radices result in the most efficient implementations. The architectures proposed improve the features of other architectures for q-th root extraction.

关键词： Algorithm design and analysis Approximation methods Equations Integer rooting Mathematical model Piecewise linear approximation Table lookup composite iterative algorithm digit recurrence logarithm elementary function evaluation error analysis error analysis floating point arithmetic high-radix digit-by-digit algorithms iterative methods left-to-right carry-free multiplication on-line algorithms online exponential overlapped operation parallel operation q-th root calculation single precision floating point computation

来源：评论

学校读者我要写书评

暂无评论

The Cinderella Game on Holes and Anti-holes

The Cinderella Game on Holes and Anti-holes

引用

37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011)

作者： Bodlaender, Marijke H. L. Hurkens, Cor A. J. Woeginger, Gerhard J. Univ Utrecht Dept Informat & Comp Sci NL-3508 TC Utrecht Netherlands TU Eindhoven Dept Math & Comp Sci Eindhoven Netherlands

ISBN: (纸本)9783642258695;9783642258701

We investigate a two-player game on graphs, where one player (Cinderella) wants to keep the behavior of an underlying water-bucket system stable whereas the other player (the wicked Stepmother) wants to cause overflows. The bucket number of a graph G is the smallest possible bucket size with which Cinderella can win the game. We determine the bucket numbers of all perfect graphs, and we also derive results on the bucket numbers of certain non-perfect graphs. In particular, we analyze the game on holes and (partially) on anti-holes for the cases where Cinderella sticks to a simple greedy strategy.

关键词： Combinatorial game on-line algorithms perfect graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：