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

Semi-on-line multiprocessor scheduling with given total processing time

THEORETICAL COMPUTER SCIENCE 2005年第1-3期337卷 134-146页

作者： Cheng, TCE Kellerer, H Kotov, V Graz Univ Inst Stat & Operat Res A-8010 Graz Austria Hong Kong Polytech Univ Dept Logist Kowloon Hong Kong Peoples R China Belarusian State Univ Fac Appl Math & Comp Sci Minsk 220050 BELARUS

We are given a set of identical machines and a sequence of jobs, the sum of whose weights is known in advance. The jobs are to be assigned on-line to one of the machines and the objective is to minimize the makespan. An algorithm with performance ratio 1.6 and a lower bound of 1.5 is presented. These results improve on the recent results by Azar and Regev, who proposed an algorithm with performance ratio 1.625 for the less general problem that the optimal makespan is known in advance. (c) 2005 Elsevier B.V. All rights reserved.

关键词： on-line algorithms semi-on-line algorithms bin stretching multiprocessor scheduling approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Management of multi-queue switches in QoS networks

引用

ALGORITHMICA 2005年第1-2期43卷 81-96页

作者： Azar, Y Richter, Y Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

The concept of Quality of Service (QoS) networks has gained growing attention recently, as the traffic volume in the Internet constantly increases, and QoS guarantees are essential to ensure proper operation of most communication-based applications. A QoS switch serves m incoming queues by transmitting packets arriving to these queues through one output port, one packet per time step. Each packet is marked with a value indicating its priority in the network. Since the queues have bounded capacities and the rate of arriving packets can be much higher than the transmission rate, packets can be lost due to insufficient queue space. The goal is to maximize the total value of transmitted packets. This problem encapsulates two dependent questions: buffer management, namely which packets to admit into the queues, and scheduling, i.e. which queue to use for transmission in each time step. We use competitive analysis to study online switch performance in QoS-based networks. Specifically, we provide a novel generic technique that decouples the buffer management and scheduling problems. Our technique transforms any single-queue buffer management policy (preemptive or non-preemptive) to a scheduling and buffer management algorithm for our general m queues model, whose competitive ratio is at most twice the competitive ratio of the given buffer management policy. We use our technique to derive concrete algorithms for the general preemptive and non-preemptive cases, as well as for the interesting special cases of the 2-value model and the unit-value model. We also provide a 1.58-competitive randomized algorithm for the unit-value case. This case is interesting by itself since most current networks (e.g. IP networks) do not yet incorporate full QoS capabilities, and treat all packets equally.

关键词： on-line algorithms competitive ratio competitiveness multi-queue switch packet switching buffer management quality of Service

来源：评论

学校读者我要写书评

暂无评论

Tight bounds for bandwidth allocation on two links

引用

DISCRETE APPLIED MATHEMATICS 2005年第2期148卷 181-188页

作者： Epstein, L Univ Haifa Dept Math IL-31905 Haifa Israel

We study on-line bandwidth allocation on two parallel links. Motivated by issues of quality of service and fair resource allocation, the goal is to maximize the load of the least loaded link. We analyze several models... 详细信息

关键词： on-line algorithms scheduling related machines bandwidth allocation

来源：评论

学校读者我要写书评

暂无评论

Low bandwidth dynamic traitor tracing schemes

引用

JOURNAL OF CRYPTOLOGY 2005年第2期18卷 167-183页

作者： Tassa, T Open Univ Div Comp Sci Raanana Israel

Dynamic traitor tracing schemes were introduced by Fiat and Tassa in order to combat piracy in active broadcast scenarios. In such settings the data provider supplies access control keys to its legal customers on a periodical basis. A number of users may collude in order to publish those keys via the Internet or any other network. Dynamic traitor tracing schemes rely on the feedback from the pirate network in order to modify their key allocation until they are able either to incriminate and disconnect all traitors or force them to stop their illegal activity. Those schemes are deterministic in the sense that incrimination is always certain. As such deterministic schemes must multiply the critical data by at least p + 1, where p is the number of traitors, they may impose a too large toll on bandwidth. We suggest here probabilistic schemes that enable one to trace all traitors with almost certainty, where the critical data is multiplied by two, regardless of the number of traitors. These techniques are obtained by combining dynamic traitor tracing schemes with binary fingerprinting techniques, such as those proposed by Boneh and Shaw.

关键词： broadcast encryption traitor tracing fingerprinting watermarking binary codes Pay-TV on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

On-line seat reservations via off-line seating arrangements

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2005年第2期16卷 381-397页

作者： Kohrt, JS Larsen, KS Univ So Denmark Dept Math & Comp Sci Odense Denmark

When reservations are made to for instance a train, it is an on-line problem to accept or reject, i.e., decide if a person can be fitted in given all earlier reservations. However, determining a seating arrangement, implying that it is safe to accept, is an off-line problem with the earlier reservations and the current one as input. We develop algorithms with optimal running time to handle problems of this nature.

关键词： channel-assignment problem seat reservation problem on-line algorithms fairness

来源：评论

学校读者我要写书评

暂无评论

Work-competitive scheduling for cooperative computing with dynamic groups

引用

SIAM JOURNAL ON COMPUTING 2005年第4期34卷 848-862页

作者： Georgiou, C Russell, A Shvartsman, AA Univ Cyprus Dept Comp Sci Nicosia Cyprus Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA MIT Lab Comp Sci & Artificial Intelligence Cambridge MA 02139 USA

The problem of cooperatively performing a set of t tasks in a decentralized computing environment subject to failures is one of the fundamental problems in distributed computing. The setting with partitionable networks is especially challenging, as algorithmic solutions must accommodate the possibility that groups of processors become disconnected ( and, perhaps, reconnected) during the computation. The efficiency of task-performing algorithms is often assessed in terms of work: the total number of tasks, counting multiplicities, performed by all of the processors during the computation. In general, the scenario where the processors are partitioned into g disconnected components causes any task-performing algorithm to have work Omega( t center dot g) even if each group of processors performs no more than the optimal number of Theta(t) tasks. Given that such pessimistic lower bounds apply to any scheduling algorithm, we pursue a competitive analysis. Specifically, this paper studies a simple randomized scheduling algorithm for p asynchronous processors, connected by a dynamically changing communication medium, to complete t known tasks. The performance of this algorithm is compared against that of an omniscient off-line algorithm with full knowledge of the future changes in the communication medium. The paper describes a notion of computation width, which associates a natural number with a history of changes in the communication medium, and shows both upper and lower bounds on work-competitiveness in terms of this quantity. Specifically, it is shown that the simple randomized algorithm obtains the competitive ratio ( 1 + cw/ e), where cw is the computation width and e is the base of the natural logarithm ( e = 2.7182...);this competitive ratio is then shown to be tight.

关键词： on-line algorithms competitive analysis partitionable networks distributed computation independent tasks randomized algorithms work complexity

来源：评论

学校读者我要写书评

暂无评论

On-line Chain Partitioning as a Model for Real-time Scheduling

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2005年 140卷 15-29页

作者： Broniek, Przemyslaw Jagiellonian Univ Dept Comp Sci Krakow Poland

We consider on-line chain partitioning of a poset as a theoretical model for some variant of tasks scheduling. Restricting ourselves to interval orders given by its representation the problem is equivalent to the coloring problem of interval graphs. We prove that up-growing variant of on-line chain partitioning of interval orders given by its representation has an optimal solution (Nearest-Fit algorithm). We also consider on-line chain partitioning of interval orders without representation and prove the lower bound for the up-growing version (3w/2). Moreover we show that there is no on-line algorithm constructing the representation of interval orders and graphs.

关键词： on-line algorithms scheduling chain partitioning up-growing interval orders

来源：评论

学校读者我要写书评

暂无评论

algorithms for on-line bin-packing problems with cardinality constraints

引用

DISCRETE APPLIED MATHEMATICS 2004年第1-3期143卷 238-251页

作者： Babel, L Chen, B Kellerer, H Kotov, V Graz Univ Inst Stat & Operat Res A-8010 Graz Austria Univ Warwick Warwick Business Sch Coventry CV4 7AL W Midlands England EADS Germany D-5705 Unterschleissheim Germany Univ Minsk Fac Appl Math & Comp Sci Minsk 220080 BELARUS

The bin-packing problem asks for a packing of a list of items of sizes from (0, 1) into the smallest possible number of bins having unit capacity. The k-item bin-packing problem additionally imposes the constraint that at most k items are allowed in one bin. We present two efficient on-line algorithms for this problem. We show that, for increasing values of k, the bound on the asymptotic worst-case performance ratio of the first algorithm tends towards 2 and that the second algorithm has a ratio of 2. Both algorithms considerably improve upon the best known result of an algorithm, which has an asymptotic bound of 2.7 on its ratio. Moreover, we improve known bounds for all values of k by presenting on-line algorithms for k = 2 and 3 with bounds on their ratios close to optimal. (C) 2004 Elsevier B.V. All rights reserved.

关键词： bin packing on-line algorithms cardinality constraint

来源：评论

学校读者我要写书评

暂无评论

algorithms for the on-line Quota Traveling Salesman Problem

引用

INFORMATION PROCESSING LETTERS 2004年第2期92卷 89-94页

作者： Ausiello, G Demange, M Laura, L Paschos, V Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy Univ Paris 09 F-75775 Paris 16 France ESSEC Dept SID F-95021 Cergy Pontoise France

The Quota Traveling Salesman Problem is a generalization of the well-known Traveling Salesman Problem. The goal of the traveling salesman is, in this case, to reach a given quota of sales, minimizing the amount of time. In this paper we address the on-line version of the problem, where requests are given over time. We present algorithms for various metric spaces, and analyze their performance in the usual framework of competitive analysis. In particular we present a 2-competitive algorithm that matches the lower bound for general metric spaces. In the case of the halfline metric space, we show that it is helpful not to move at full speed, and this approach is also used to derive the best on-line polynomial time algorithm known so far for the On-line TSP (in the homing version). (C) 2004 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Traveling Salesman Problem Quota TSP

来源：评论

学校读者我要写书评

暂无评论

Visibility-based pursuit-evasion in an unknown planar environment

引用

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH 2004年第1期23卷 3-26页

作者： Sachs, S LaValle, SM Rajko, S Univ Illinois Dept Comp Sci Urbana IL 61801 USA Iowa State Univ Dept Comp Sci Ames IA 50011 USA

We address an on-line version of the visibility-based pursuit-evasion problem. We take a minimalist approach in modeling the capabilities of a pursuer robot. A point pursuer moves in an unknown, simply-connected, piecewise-smooth planar environment, and is given the task of locating any unpredictable, moving evaders that have unbounded speed. The evaders are assumed to be points that move continuously. To solve the problem, the pursuer must for each target have an unobstructed view of it at some time during execution. The pursuer is equipped with a range sensor that measures the direction of depth discontinuities, but cannot provide precise depth measurements. All pursuer control is specified either in terms of this sensor or wall-following movements. The pursuer does not have localization capability or perfect control. We present a complete algorithm that enables the limited pursuer to clear the same environments that a pursuer with a complete map, perfect localization, and perfect control can clear (under certain general position assumptions). Theoretical guarantees that the evaders will be found are provided. The resulting algorithm to compute this strategy has been implemented in simulation. Results arc shown for several examples. The approach is efficient and simple enough to be useful towards the development of real robot systems that perform visual searching.

关键词： sensor-based planning visibility pursuit-evasion on-line algorithms surveillance bug algorithms sensing uncertainty

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：