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

Proceedings of the 33rd ACM Symposium on Parallelism in algorithms and Architectures

作者： Evgeniy Feder Ichha Rathod Punit Shyamsukha Robert Sama Vitaly Aksenov Iosif Salem Stefan Schmid ITMO University St. Petersburg Russian Fed. Indian Institute of Technology Delhi New Delhi India University of Vienna Vienna Austria

ISBN: (纸本)9781450380706

Self-adjusting networks (SANs) utilize novel optical switching technologies to support dynamic physical network topology reconfiguration. SANs rely on online algorithms to exploit this topological flexibility to reduce the cost of serving network traffic, leveraging locality in the demand. Models in prior work assign uniform cost for traversing and adjusting a single link (e.g. both cost 1). In this paper, we initiate the study of online algorithms for SANs in a more realistic cost model, the Matching Model (MM), in which the network topology is given by the union of a constant number of bipartite matchings (realized by optical switches), and in which changing an entire matching incurs a fixed cost a. The cost of routing is given by the number of hops packets need to traverse. We present online SAN algorithms in the MM with cost O(√α) times the cost of reference algorithms in the uniform cost model.

关键词： matching model self-adjusting networks online algorithms

来源：评论

学校读者我要写书评

暂无评论

Randomized qeue management for DiffServ 05

Randomized qeue management for DiffServ

引用

Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures

作者： Nir Andelman Tel-Aviv University Tel-Aviv Israel

ISBN: (纸本)9781581139860

We focus on the online problem of queue management in networks providing differentiated services. As in DiffServ, packets are divided into two priority groups. Low priority packets are assigned the value of 1 and high priority packets are assigned the value of α > 1. The goal is to maximize the total value of packets that are sent. Restricted to FIFO queues, the packets must be sent by the order of their arrival, however we are allowed to preempt packets from the *** deterministic online algorithms for this model have been presented in previous papers. Currently, the best online algorithm known for this problem has a competitive ratio of 1.304 for the worst case α [17]. In this work we consider randomized online algorithms. Our main result is an online policy that outperforms any deterministic policy and achieves a competitive ratio of 1.25, by using a single random bit. This result is lower than the deterministic lower bound of 1.281 [19]. We then derive a general lower bound for randomized algorithms of 1.197.A natural extension of this model is to assign arbitrary packet values to the input packets. Currently, the best competitive ratio achieved for a deterministic policy is 1.75 [7]. We present a randomized comparison based online policy with the same competitive ratio. Since no deterministic comparison based policy is known to have a competitive ratio better than 2, we believe that this result demonstrates the potential of using randomization to outperform deterministic policies, as in the two value model.

关键词： active queue management randomized algorithms online algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Profitable Scheduling on Multiple Speed-Scalable Processors 13

Profitable Scheduling on Multiple Speed-Scalable Processors

引用

Annual ACM Symposium on Parallel algorithms and Architectures

作者： Peter Kling Peter Pietrzyk Heinz Nixdorf Institute & Computer Science Department University of Paderborn

ISBN: (纸本)9781450315722

We present a new online algorithm for profit-oriented scheduling on multiple speed-scalable processors. Moreover, we provide a tight analysis of the algorithm's competitiveness. Our results generalize and improve upon work by Chan et al. [10], which considers a single speed-scalable processor. Using significantly different techniques, we can not only extend their model to multiprocessors but also prove an enhanced and tight competitive ratio for our algorithm. In our scheduling problem, jobs arrive over time and are preemptable. They have different workloads, values, and deadlines. The scheduler may decide not to finish a job but instead to suffer a loss equaling the job's value. However, to process a job's workload until its deadline the scheduler must invest a certain amount of energy. The cost of a schedule is the sum of lost values and invested energy. In order to finish a job the scheduler has to determine which processors to use and set their speeds accordingly. A processor's energy consumption is power P_α(s) integrated over time, where P_α(s) = s~α is the power consumption when running at speed s. Since we consider the online variant of the problem, the scheduler has no knowledge about future jobs. This problem was introduced by Chan et al. [10] for the case of a-single processor. They presented an online algorithm which is α~α + 2eα-competitive. We provide an online algorithm for the case of multiple processors with an improved competitive ratio of α~α.

关键词： scheduling energy online algorithms primal-dual convex programming PROCESSOR convex programming jobs scheduler program Energy sources energy capacity Multiprocessor algorithms analysis of algorithm

来源：评论

学校读者我要写书评

暂无评论

Budget smoothing for internet ad auctions: a game theoretic approach 13

Budget smoothing for internet ad auctions: a game theoretic ...

引用

Proceedings of the fourteenth ACM conference on Electronic commerce

作者： Denis Charles Deeparnab Chakrabarty Max Chickering Nikhil R. Devanur Lei Wang Microsoft Research Redmond WA USA Microsoft Research Bangalore India Microsoft adCenter Bellevue WA USA

ISBN: (纸本)9781450319621

In Internet ad auctions, search engines often throttle budget constrained advertisers so as to spread their spends across the specified time period. Such policies are known as budget smoothing policies. In this paper, we perform a principled, game-theoretic study of what the outcome of an ideal budget smoothing algorithm should be. In particular, we propose the notion of regret-free budget smoothing policies whose outcomes throttle each advertiser optimally, given the participation of the other advertisers. We show that regret-free budget smoothing policies always exist, and in the case of single slot auctions we can give a polynomial time smoothing algorithm. Inspired by the existence proof, we design a heuristic for budget smoothing which performs considerably better than existing benchmark heuristics.

关键词： ad auctions equilibrium budget smoothing online algorithms

来源：评论

学校读者我要写书评

暂无评论

Minimizing Weighted Flow Time

引用

ACM TRANSACTIONS ON algorithms 2007年第4期3卷 39–es页

作者： Bansal, Nikhil Dhamdhere, Kedar IBM TJ Watson Res Yorktown Hts NY USA Google Inc Mountain View CA 94043 USA

We consider the problem of minimizing the total weighted flow time on a single machine with preemptions. We give an online algorithm that is O(k)-competitive for k weight classes. This implies an O(log W)-competitive algorithm, where W is the maximum to minimum ratio of weights. This algorithm also implies an O(log n + log P)-approximation ratio for the problem, where P is the ratio of the maximum to minimum job size and n is the number of jobs. We also consider the nonclairvoyant setting where the size of a job is unknown upon its arrival and becomes known to the scheduler only when the job meets its service requirement. We consider the resource augmentation model, and give a (1 + epsilon)-speed, (1 + 1/epsilon)-competitive online algorithm.

关键词： Scheduling online algorithms response time nonclairvoyant scheduling

来源：评论

学校读者我要写书评

暂无评论

An Optimal Lower Bound for Buffer Management in Multi-Queue Switches 11

An Optimal Lower Bound for Buffer Management in Multi-Queue ...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Marcin Bienkowski Institute of Computer Science University of Wroclaw

ISBN: (纸本)9780898719932

In the online packet buffering problem (also known as the unweighted FIFO variant of buffer management), we focus on a single network packet switching device with several input ports and one output port. This device forwards unit-size, unit-value packets from input ports to the output port. Buffers attached to input ports may accumulate incoming packets for later transmission; if they cannot accommodate all incoming packets, the excess is lost. A packet buffering algorithm has to choose from which buffers to transmit packets in order to minimize the number of lost packets and thus maximize the throughput. We present a tight lower bound of e/(e - 1) ≈ 1.582 on the competitive ratio of the throughput maximization, which holds even for randomized algorithms. This improves the previously best known lower bound of 1.4659 and matches the performance of the algorithm Random Schedule. Our result contradicts the claimed performance of the Random Permutation algorithm; we point out a flaw in its original analysis.

关键词： online algorithms Packet buffering Buffer management Multi-queue switches input port Packet Lower bound buffers output ports randomized algorithms Throughput

来源：评论

学校读者我要写书评

暂无评论

The Generalized Magician Problem under Unknown Distributions and Related Applications 22

The Generalized Magician Problem under Unknown Distributions...

引用

Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems

作者： Aravind Srinivasan Pan Xu University of Maryland College Park College Park MD USA New Jersey Institute of Technology Newark NJ USA

ISBN: (纸本)9781450392136

The Magician Problem (MP) and its generalization, the Generalized Magician Problem (GMP), were introduced by Alaei et al. (APPROX-RANDOM 2013) and Alaei (SICOMP 2014) and have been used as powerful ingredients in online-algorithm design for many hard problems such as the k-choice prophet inequality, mechanism design in Bayesian combinatorial auctions, and the generalized assignment problem. The adversarial model here is essentially that of an oblivious adversary. In this paper, we introduce generalizations of GMP (MP) under two different arrival settings (by making the adversary stronger): unknown independent identical distributions (UIID) and unknown adversarial distributions (UAD). Different adversary models capture a range of arrival patterns. For GMP under UIID, we show that a natural greedy algorithm Greedy is optimal. For the case of MP under UIID, we show that Greedy has an optimal performance of 1 - BB/B! eB ≥ 1 - 1/√2π B, where B is the budget, and show an application to online B-matching with stochastic rewards. For GMP under UAD, we present a simple algorithm, which is near-optimal among all non-adaptive algorithms. We consider the simple case of MP under UAD with B=1, and give an exact characterization of the respective optimal adaptive and optimal non-adaptive algorithms for any finite time horizon. We offer an example of MP under UAD on which there is a provable gap between the classical MP under adversarial order and MP under UAD even with a time horizon T=4.

关键词： prophet inequality magician problem online algorithms

来源：评论

学校读者我要写书评

暂无评论

algorithms for Power Savings

引用

ACM TRANSACTIONS ON algorithms 2007年第4期3卷 41–es页

作者： Irani, Sandy Shukla, Sandeep Gupta, Rajesh Univ Calif Irvine Comp Sci Dept Irvine CA 92697 USA Virginia Tech Dept Elect & Comp Engn Blacksburg VA 24061 USA Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA

This article examines two different mechanisms for saving power in battery-operated embedded systems. The first strategy is that the system can be placed in a sleep state if it is idle. However, a fixed amount of energy is required to bring the system back into an active state in which it can resume work. The second way in which power savings can be achieved is by varying the speed at which jobs are run. We utilize a power consumption curve P(s) which indicates the power consumption level given a particular speed. We assume that P(s) is convex, nondecreasing, and nonnegative for s >= 0. The problem is to schedule arriving jobs in a way that minimizes total energy use and so that each job is completed after its release time and before its deadline. We assume that all jobs can be preempted and resumed at no cost. Although each problem has been considered separately, this is the first theoretical analysis of systems that can use both mechanisms. We give an offline algorithm that is within a factor of 2 of the optimal algorithm. We also give an online algorithm with a constant competitive ratio.

关键词： Power savings dynamic speed scaling online algorithms

来源：评论

学校读者我要写书评

暂无评论

Cloud Scheduling with Setup Cost 13

Cloud Scheduling with Setup Cost

引用

Annual ACM Symposium on Parallel algorithms and Architectures

作者： Yossi Azar Naama Ben-Aroya Nikhil R. Devanur Navendu Jain Blavatnik School of Computer Science Tel-Aviv University Microsoft Research Redmond WA

ISBN: (纸本)9781450315722

In this paper, we investigate the problem of online task scheduling of jobs such as MapReduce jobs, Monte Carlo simulations and generating search index from web documents, on cloud computing infrastructures. We consider the virtualized cloud computing setup comprising machines that host multiple identical virtual machines (VMs) under pay-as-you-go charging, and that booting a VM requires a constant setup time. The cost of job computation depends on the number of VMs activated, and the VMs can be activated and shutdown on demand. We propose a new bi-objective algorithm to minimize the maximum task delay, and the total cost of the computation. We study both the clairvoyant case, where the duration of each task is known upon its arrival, and the more realistic non-clairvoyant case.

关键词： online algorithms scheduling cloud computing competitive ratio clairvoyant non-clairvoyant Cloud Computing jobs virtual machines setting time Total Costs

来源：评论

学校读者我要写书评

暂无评论

Energy-Efficient algorithms for Flow Time Minimization

引用

ACM TRANSACTIONS ON algorithms 2007年第4期3卷 49–es页

作者： Albers, Susanne Fujiwara, Hiroshi Univ Freiburg Dept Comp Sci Georges Kohler Allee 79 D-79110 Freiburg Germany Kwansei Gakuin Univ Sch Sci & Technol Dept Informat Sanda 6691337 Japan

We study scheduling problems in battery-operated computing devices, aiming at schedules with low total energy consumption. While most of the previous work has focused on finding feasible schedules in deadline-based settings, in this article we are interested in schedules that guarantee good response times. More specifically, our goal is to schedule a sequence of jobs on a variable-speed processor so as to minimize the total cost consisting of the energy consumption and the total flow time of all jobs. We first show that when the amount of work, for any job, may take an arbitrary value, then no online algorithm can achieve a constant competitive ratio. Therefore, most of the article is concerned with unit-size jobs. We devise a deterministic constant competitive online algorithm and show that the offline problem can be solved in polynomial time.

关键词： Variable-speed processor flow time online algorithms competitive analysis offline algorithms dynamic programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：