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

Better online algorithms for scheduling with machine cost

SIAM JOURNAL ON COMPUTING 2004年第5期33卷 1035-1051页

作者： Dósa, G He, Y Univ Veszprem Dept Math Veszprem Hungary Zhejiang Univ Dept Math State Key Lab CAD & CG Hangzhou 310027 Peoples R China

For most scheduling problems the set of machines is fixed initially and remains unchanged for the duration of the problem. Recently Imreh and Noga proposed adding the concept of machine cost to scheduling problems and considered the so-called list model problem. For this problem, we are given a sequence of independent jobs with positive sizes, which must be processed nonpreemptively on a machine. No machines are initially provided, and when a job is revealed the algorithm has the option to purchase new machines. The objective is to minimize the sum of the makespan and cost of machines. In this paper, we first present an online algorithm with a competitive ratio at most 1.5798, which improves the known upper bound 1.618. Then for a special case where every job size is no greater than the machine cost, we present an optimal online algorithm with a competitive ratio 4/3. Last, we present an algorithm with a competitive ratio at most 3/2 for the semionline problem with known largest size, which improves the known upper bound 1.5309.

关键词： parallel machine scheduling machine cost online algorithm competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Best semi-online algorithms for unbounded parallel batch scheduling

引用

DISCRETE APPLIED MATHEMATICS 2011年第8期159卷 838-847页

作者： Yuan, Jinjiang Ng, C. T. Cheng, T. C. E. Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Zhengzhou Univ Dept Math Zhengzhou 450001 Henan Peoples R China

We consider semi-online scheduling of an unbounded parallel batch machine to minimize the makespan where, at the present time instant t, information on the first longest job arriving after t is known. In this paper online means that jobs arrive over time, J*(t) denotes the first longest job arriving after t, and p*(t) and r*(t) denote the processing time and arrival time of J*(t), respectively. Given information p*(t), we present an online algorithm with a competitive ratio (5 - root 5)/2 approximate to 1.382, and show that the algorithm is the best possible;furthermore, this algorithm generates at most two batches. This algorithm is also the best possible given information J*(t). Given information r*(t), we present an online algorithm with a competitive ratio 3/2, and show that any online algorithm cannot have a competitive ratio less than 3 root 3 approximate to 1.442;furthermore, this algorithm generates at most three batches. Given information r*(t) with the restriction that an online algorithm generates at most two batches, we present an online algorithm with a competitive ratio (root f + 1)/2 approximate to 1.618, and show that the algorithm is the best possible. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Parallel batch scheduling online algorithm Information in advance Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Distribution-Oblivious online algorithms for Age-of-Information Penalty Minimization

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2023年第4期31卷 1779-1794页

作者： Tsai, Cho-Hsin Wang, Chih-Chun Purdue ECE W Lafayette IN 47907 USA MathWorks Inc Natick MA 01760 USA

The ever-increasing needs of supporting real-time applications have spurred new studies on minimizing Age-of-Information (AoI), a novel metric characterizing the data freshness of the system. This work studies the single-queue information update system and strengthens the seminal results of Sun et al. on the following fronts: (i) When designing the optimal offline schemes with full knowledge of the delay distributions, a new fixed-point-based method is proposed with quadratic convergence rate, an order-of-magnitude improvement over the state-of-the-art;(ii) When the distributional knowledge is unavailable (which is the norm in practice), two new low-complexity online algorithms are proposed, which provably attain the optimal average AoI penalty;and (iii) the online schemes also admit a modular architecture, which allows the designer to upgrade certain components to handle additional practical challenges. Two such upgrades are proposed for the situations: (iii.1) The AoI penalty function is also unknown and must be estimated on the fly, and (iii.2) the unknown delay distribution is Markovian instead of i.i.d. The performance of our schemes is either provably optimal or within 3% of the omniscient optimal offline solutions in all simulation scenarios.

关键词： Age-of-information online algorithm fixed-point equation stochastic approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal online algorithms for an electronic commerce money distribution system

引用

algorithmICA 2002年第3期33卷 287-299页

作者： Kawazoe, H Shibuya, T Tokuyama, T IBM Japan Ltd Ind eApplicat Sales eBusiness Solut Chuo Ku Tokyo 1038510 Japan Tokyo Res Lab IBM Res Div Yamato Kanagawa 2428502 Japan Tohoku Univ Grad Sch Informat Sci Aoba Ku Sendai Miyagi 9808577 Japan

We consider the money distribution problem for a micro-payment scheme using a distributed server system: in particular, for an automatic charging scheme named PayPerClick that allows Internet users to view Web pages for which access charges are levied without tedious payment procedures. A major bottleneck in the scheme is the network traffic caused by the distribution of electronic money to many different servers. We propose a simple online algorithm for distributing electronic money to servers, so that the network traffic is minimized. The algorithm achieves the optimal online competitive ratio. We also consider a weighted version, for which we give an asymptotically optimal online algorithm within a constant factor.

关键词： online algorithm algorithm analysis electronic commerce money distribution system PayPerClick

来源：评论

学校读者我要写书评

暂无评论

An algorithm with performance guarantee for the online Container Relocation Problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2017年第1期259卷 48-62页

作者： Zehendner, Elisabeth Feillet, Dominique Jaillet, Patrick Ecole Mines St Etienne F-13541 Gardanne France CMP Georges Charpak LIMOS UMR CNRS 6158 F-13541 Gardanne France MIT Dept Elect Engn & Comp Sci Lab Informat & Decis Syst 77 Massachusetts Ave Cambridge MA 02139 USA MIT Ctr Operat Res 77 Massachusetts Ave Cambridge MA 02139 USA

This paper introduces and investigates the online Container Relocation Problem, where containers have to be retrieved from a bay in a container terminal so as to minimize the number of relocations. Unlike the offline version of the problem, the order of container retrievals is revealed one at a time in an online fashion. We analyze the so-called leveling heuristic using the perspective of worst-case competitive analysis of online algorithms and derive its competitive ratio. We then provide some computational experiments which give insights on the actual average performance of the heuristic. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Container terminal algorithm with performance guarantee Container relocation online algorithm

来源：评论

学校读者我要写书评

暂无评论

Complexity and online algorithms for minimum skyline coloring of intervals

引用

THEORETICAL COMPUTER SCIENCE 2019年 788卷 66-78页

作者： Erlebach, Thomas Liu, Fu-Hong Liu, Hsiang-Hsuan Shalom, Mordechai Wong, Prudence W. H. Zaks, Shmuel Univ Leicester Dept Informat Leicester Leics England Natl Tsing Hua Univ Dept Comp Sci Hsinchu Taiwan Univ Wroclaw Inst Comp Sci Wroclaw Poland TelHai Coll IL-12210 Upper Galilee Israel Univ Liverpool Dept Comp Sci Liverpool Merseyside England Technion Dept Comp Sci Haifa Israel Ruppin Acad Ctr Sch Engn Netanya Israel

Motivated by applications in optical networks and job scheduling, we consider the interval coloring problem in a setting where an increasing cost is associated with using a higher color index. The cost of a coloring at any point of the line is the cost of the maximum color index used at that point, and the cost of the overall coloring is the integral of the cost over all points on the line. A coloring of minimum cost is called a minimum skyline coloring. We prove that the problem of computing a minimum skyline coloring is NP-hard and initiate the study of the online setting, where intervals arrive one by one. We give an asymptotically optimal online algorithm for the case of linear color costs and present further results for some variations and generalizations of the problem. Furthermore, we consider the variant of the minimum skyline coloring problem where the intervals are already partitioned into color classes and we only need permute the colors so as to minimize the cost of the coloring. We show that this problem variant is NP-hard and present a 2-approximation algorithm for it. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Skyline coloring of intervals online algorithm NP-hardness Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Primal Dual Gives Almost Optimal Energy-Efficient online algorithms

引用

ACM TRANSACTIONS ON algorithmS 2018年第1期14卷 1–30页

作者： Devanur, Nikhil R. Huang, Zhiyi Microsoft Res 1 Microsoft Way Redmond WA 98052 USA Univ Hong Kong 423 Chow Yei Ching Bldg Pokfulam Hong Kong Peoples R China

We consider the problem of online scheduling of jobs on unrelated machines with dynamic speed scaling to minimize the sum of energy and weighted flow-time. We give an algorithm with an almost optimal competitive ratio for arbitrary power functions. (No earlier results handled arbitrary power functions for unrelated machines.) For power functions of the form f (s) = s(alpha) for some constant alpha > 1, we get a competitive ratio of O(alpha/log alpha), improving upon a previous competitive ratio of O(alpha(2)) by Anand et al. (2012), along with a matching lower bound of Omega(alpha/log alpha). Further, in the resource augmentation model, with a 1+epsilon speed up, we give a 2(1/epsilon + 1) competitive algorithm, with essentially the same techniques, improving the bound of 1 + O(1/epsilon(2)) by Gupta et al. (2010) and matching the bound of Anand et al. (2012) for the special case of fixed speed unrelated machines. Unlike the previous results most of which used an amortized local competitiveness argument or dual fitting methods, we use a primal-dual method, which is useful not only to analyze the algorithms but also to design the algorithm itself.

关键词： online algorithm scheduling flow-time energy efficiency

来源：评论

学校读者我要写书评

暂无评论

Optimal online algorithms for MapReduce scheduling on two uniform machines

引用

OPTIMIZATION LETTERS 2019年第7期13卷 1663-1676页

作者： Jiang, Yiwei Zhou, Ping Cheng, T. C. E. Ji, Min Zhejiang Gongshang Univ Contemporary Business & Trade Res Ctr Sch Management & & Business Hangzhou 310018 Zhejiang Peoples R China Zhejiang Business Coll Coll Humanities Hangzhou 310053 Zhejiang Peoples R China Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China

We study online scheduling on two uniform machines in the MapReduce system. Each job consists of two sets of tasks, namely the map tasks and reduce tasks. A job's reduce tasks can only be processed after all its map tasks are finished. The map tasks are fractional, i.e., they can be arbitrarily split and processed on different machines in parallel. Our goal is to find a schedule that minimizes the makespan. We consider two variants of the problem, namely the cases involving preemptive reduce tasks and non-preemptive reduce tasks. We provide lower bounds for both variants. For preemptive reduce tasks, we present an optimal online algorithm with a competitive ratio of s2+2s+5+1-s/2 where s = 1 is the ratio between the speeds of the two machines. For non-preemptive reduce tasks, we show that the LS-like algorithm is optimal and its competitive ratio is 2s+1/s+1 if s < 1+root 5/2 and s+1/s if s >= 1+root 5/2.

关键词： Big data MapReduce scheduling online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Global implicit function theorems and the online expectation-maximisation algorithm

引用

AUSTRALIAN & NEW ZEALAND JOURNAL OF STATISTICS 2022年第2期64卷 255-281页

作者： Hien Duy Nguyen Forbes, Florence Univ Queensland Sch Math & Phys St Lucia Qld 4067 Australia La Trobe Univ Dept Math & Stat Bundoora Vic 3086 Australia Univ Grenoble Alpes LJK Grenoble INP CNRSInria F-38000 Grenoble France

The expectation-maximisation (EM) algorithm framework is an important tool for statistical computation. Due to the changing nature of data, online and mini-batch variants of EM and EM-like algorithms have become increasingly popular. The consistency of the estimator sequences that are produced by these EM variants often rely on an assumption regarding the continuous differentiability of a parameter update function. In many cases, the parameter update function is not in closed form and may only be defined implicitly, which makes the verification of the continuous differentiability property difficult. We demonstrate how a global implicit function theorem can be used to verify such properties in the cases of finite mixtures of distributions in the exponential family, and more generally, when the component-specific distributions admit data augmentation schemes, within the exponential family. We then illustrate the use of such a theorem in the cases of mixtures of beta distributions, gamma distributions, fully visible Boltzmann machines and Student distributions. Via numerical simulations, we provide empirical evidence towards the consistency of the online EM algorithm parameter estimates in such cases.

关键词： expectation-maximisation algorithm global implicit function theorem mixture models online algorithm student distribution

来源：评论

学校读者我要写书评

暂无评论

Optimal online algorithms for scheduling on two identical machines under a grade of service

引用

Journal of Zhejiang University-Science A(Applied Physics & Engineering) 2006年第3期7卷 309-314页

作者：蒋义伟何勇唐春梅 Laboratory of Information and Optimization Technologies Ningbo Institute of Technology Zhejiang University Ningbo 315100 China Department of Mathematics Zhejiang University Hangzhou 310027 China Department of Mathematics Zhejiang University Hangzhou 310027 China

This work is aimed at investigating the online scheduling problem on two parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels, so each job and machine are labelled with the GoS levels, and each job can be processed by a particular machine only when its GoS level is no less than that of the machine. The goal is to minimize the makespan. For non-preemptive version, we propose an optimal online al-gorithm with competitive ratio 5/3. For preemptive version, we propose an optimal online algorithm with competitive ratio 3/2.

关键词： online algorithm Competitive analysis Parallel machine scheduling Grade of service (GoS)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：