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

Incremental learning of approximations from positive data

INFORMATION PROCESSING LETTERS 2004年第1期89卷 37-42页

作者： Grieser, G Lange, S Tech Univ Darmstadt FB Informat D-64283 Darmstadt Germany Deutsch Forschungszentrum Kunstliche Intelligenz D-66123 Saarbrucken Germany

Three different types of incremental learning are systematically studied: iterative learning, feedback inference, and bounded example-memory learning. In contrast to exact learning, where a learner is required to stabilize on a correct description of the target concept, approximate learning deals with scenarios in which a learner is successful if its final hypothesis describes a finite variant of the target concept. The considered models of approximate incremental learning are related to one another. The results achieved are compared to those obtained for exact learning. (C) 2003 Elsevier B.V. All rights reserved.

关键词： inductive inference incremental learning formal languages theory of computation on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

The orthogonal CNN problem

引用

INFORMATION PROCESSING LETTERS 2004年第3期90卷 115-120页

作者： Iwama, K Yonezawa, K Kyoto Univ Sch Informat Kyoto 6068501 Japan

The online CNN problem had no known competitive algorithms for a long time. Sitters, Stougie and de Paepe showed that there exists a competitive online algorithm for this problem. However, both their algorithm and analysis are quite complicated, and above all, their upper bound for the competitive ratio is 10(5). In this paper, we examine why this problem seems so difficult. To this end we introduce a nontrivial restriction, orthogonality, against this problem and show that it decreases the competitive ratio dramatically, down to at most 9. (C) 2004 Elsevier B.V. All rights reserved.

关键词： on-line algorithms competitive analysis server problems

来源：评论

学校读者我要写书评

暂无评论

Optimal preemptive semi-online scheduling on two uniform processors

引用

INFORMATION PROCESSING LETTERS 2004年第5期92卷 219-223页

作者： Du, DL Univ New Brunswick Fac Adm Fredericton NB E3B 5V4 Canada

We investigate a preemptive semi-online scheduling problem. Jobs with sizes within a certain range [1, r] (r greater than or equal to 1) arrive one by one to be scheduled on two uniform parallel processors with speed 1 and s greater than or equal to 1, respectively. The objective is to minimize makespan. We characterize the optimal competitive ratio as a function of both s and r by devising a deterministic on-line scheduling algorithm along with a matching lower bound, which also holds for randomized algorithms. (C) 2004 Elsevier B.V. All rights reserved.

关键词： on-line algorithms uniform processor scheduling preemption

来源：评论

学校读者我要写书评

暂无评论

Scheduling search procedures

引用

JOURNAL OF SCHEDULING 2004年第5期7卷 349-364页

作者： Damaschke, P Chalmers Univ Technol Sch Engn & Comp Sci S-41296 Gothenburg Sweden

We analyze preemptive on-line scheduling against randomized adversaries, with the goal to finish an unknown distinguished target job. Our motivation comes froth clinical gene search projects, but the subject leads to general theoretical questions of independent interest, including some natural but unusual probabilistic models. We study problem versions with known and unknown processing tithes of jobs and target probabilities, and models where the on-line player gets some randomized extra information about the target. For some versions we get optimal competitive ratios, expressed in terms of given parameters of instances.

关键词： on-line algorithms randomized adversary searching Bayesian models

来源：评论

学校读者我要写书评

暂无评论

Allocating servers in infostations for bounded simultaneous requests

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2004年第10期64卷 1113-1126页

作者： Bertossi, AA Pinotti, MC Rizzi, R Gupta, P Univ Perugia Dept Comp Sci & Math I-06123 Perugia Italy Univ Bologna Dept Comp Sci I-40127 Bologna Italy Univ Trent Dept Comp Sci & Telecommun I-38050 Trento Italy Indian Inst Technol Dept Comp Sci & Engn Kanpur 208016 Uttar Pradesh India

The server allocation with bounded simultaneous requests problem arises in isolated infostations, where mobile users going through the coverage area require immediate high-bit rate communications such as web surfing, file transferring, voice messaging, email and fax. Given a set of service requests, each characterized by a temporal interval and a category, an integer k, and an integer h(c) for each category c, the problem consists in assigning a server to each request in such a way that at most k mutually simultaneous requests are assigned to the same server at the same time, out of which at most h(c) are of category c, and the minimum number of servers is used. Since this problem is computationally intractable, a 2-approximation on-line algorithm is exhibited which asymptotically gives a (2 - h/k)- approximation, where h = min{h(c)}. Generalizations of the problem are considered, where each request r is also characterized by a bandwidth rate W, and the sum of the bandwidth rates of the simultaneous requests assigned to the same server at the same time is bounded, and where each request is characterized also by a gender bandwidth. Such generalizations contain bin-packing, multiprocessor task scheduling, and interval graph coloring as special cases, and they admit on-line algorithms providing constant approximations. (C) 2004 Elsevier Inc. All rights reserved.

关键词： infostations server allocation bin-packing greedy algorithms approximation algorithms on-line algorithms interval coloring

来源：评论

学校读者我要写书评

暂无评论

SPT is optimally competitive for uniprocessor flow

引用

INFORMATION PROCESSING LETTERS 2004年第5期90卷 233-238页

作者： Bunde, DP Univ Illinois Dept Comp Sci Urbana IL 61801 USA

We show that the Shortest Processing Time (SPT) algorithm is (Delta + 1)/2-competitive for nonpreemptive uniprocessor total flow time with release dates, where Delta is the ratio between the longest and shortest job lengths. This is best possible for a deterministic algorithm and improves on the (Delta + 1)-competitive ratio shown by Epstein and van Stee using different methods. (C) 2004 Elsevier B.V. All rights reserved.

关键词： algorithms on-line algorithms scheduling

来源：评论

学校读者我要写书评

暂无评论

New lower and upper bounds for the competitive ratio of transmission protocols

引用

INFORMATION PROCESSING LETTERS 2004年第6期89卷 297-301页

作者： Liskiewicz, M Manthey, B Med Univ Lubeck Inst Theoret Informat D-23560 Lubeck Germany

Transmission protocols like TCP are usually divided into a time scheduling and a data selection policy. We consider on-line algorithms of data selection policies for any time scheduling policy and any routing behavior in a network. For the model introduced by Adler et al. [Proc. 5th Israel Symp. on Theory of Computing Systems, 1997, pp. 64-72], we improve both the lower and the upper bound on the competitive ratio making them asymptotically tight. Furthermore, we present a lower bound that depends on the size of the buffers that are available both to the sender and to the receiver. We obtain a constant lower bound for the competitive ratio for constant buffer size. (C) 2003 Elsevier B.V. All rights reserved.

关键词： on-line algorithms interconnection networks transmission protocols

来源：评论

学校读者我要写书评

暂无评论

Grid scheduling by on-line rectangle packing

引用

NETWORKS 2004年第2期44卷 106-119页

作者： Caramia, M Giordani, S Iovanella, A CNR ISt Applicaz Calcolo M Picone I-00161 Rome Italy Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod I-00133 Rome Italy

The Grid computing paradigm is originated from a new computing infrastructure for scientific research and cooperation, and is becoming an established technology for large-scale resource sharing and distributed integration. Two main problems arise: how to efficiently allocate resources to tasks and, after this, how to schedule them. In this article we propose to solve the scheduling phase by means of rectangle packing algorithms. In particular, two on-line rectangle packing algorithms are proposed with the objective of maximizing the system efficiency. A wide computational analysis is provided. The performances of the proposed algorithms are first compared with those of known algorithms on benchmark instances for rectangle packing, and then are evaluated on different Grid scheduling scenarios associated with different processing and dataset environments. (C) 2004 Wiley Periodicals, Inc.

关键词： rectangle packing grid scheduling on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling broadcasts with deadlines

引用

THEORETICAL COMPUTER SCIENCE 2004年第3期325卷 479-488页

作者： Kim, JH Chwa, KY Pusan Natl Foreign Studies Dept Comp Engn Pusan 608738 South Korea Korea Adv Inst Sci & Technol Dept Elect Engn Comp Sci Taejon 305701 South Korea

We investigate the problem of scheduling broadcasts in data delivering systems via broadcast, where a number of requests from several clients can be simultaneously satisfied by one broadcast of a server. Most of prior work has focused on minimizing the total flow time of requests. It assumes that once a request arrives, it will be held until satisfied. In this paper, we are concerned with the situation that clients may leave the system if their requests are still unsatisfied after waiting for some time, that is, each request has a deadline. The problem of maximizing the throughput, for example, the total number of satisfied requests, is developed, and there are given online algorithms achieving constant competitive ratios. (C) 2004 Elsevier B.V. All rights reserved.

关键词： broadcast scheduling on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Path kernels and multiplicative updates

Path kernels and multiplicative updates

引用

16th Annual Conference on Neural Information Processing Systems (NIPS)

作者： Takimoto, E Warmuth, MK Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan Univ Calif Santa Cruz Dept Comp Sci Santa Cruz CA 95064 USA

Kernels are typically applied to linear algorithms whose weight vector is a linear combination of the feature vectors of the examples. On-line versions of these algorithms are sometimes called "additive updates" because they add a multiple of the last feature vector to the current weight vector. In this paper we have found a way to use special convolution kernels to efficiently implement,'multiplicative" updates. The kernels are defined by a directed graph. Each edge contributes an input. The inputs along a path form a product feature and all such products build the feature vector associated with the inputs. We also have a set of probabilities on the edges so that the outflow from each vertex is one. We then discuss multiplicative updates on these graphs where the prediction is essentially a kernel computation and the update contributes a factor to each edge. After adding the factors to the edges, the total outflow out of each vertex is not one any more. However some clever algorithms re-normalize the weights on the paths so that the total outflow out of each vertex is one again. Finally, we show that if the digraph is built from a regular expressions, then this can be used for speeding up the kernel and re-normalization computations. We reformulate a large number of multiplicative update algorithms using path kernels and characterize the applicability of our method. The examples include efficient algorithms for learning disjunctions and a recent algorithm that predicts as well as the best pruning of a series parallel digraphs.

关键词： kernels multiplicative updates on-line algorithms series parallel digraphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：