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

On-line scheduling to minimize average completion time revisited

OPERATIONS RESEARCH LETTERS 2004年第5期32卷 485-490页

作者： Megow, N Schulz, AS Tech Univ Berlin Inst Math D-10623 Berlin Germany MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA

We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms. (C) 2003 Elsevier B.V. All rights reserved.

关键词： scheduling on-line algorithm approximation algorithm competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Randomized on-line scheduling on three processors

引用

OPERATIONS RESEARCH LETTERS 2004年第2期32卷 152-158页

作者： Tichy, T AS CR Inst Math CZ-11567 Prague 1 Czech Republic

We consider a randomized on-line scheduling problem where each job has to be scheduled on any of m identical processors. The objective is to minimize the expected makespan. We show that the competitive ratio of any randomized algorithm for 27 m = 3 processors must be strictly greater than 27/19. (C) 2003 Elsevier B.V. All rights reserved.

关键词： scheduling makespan competitive analysis on-line algorithm lower bound

来源：评论

学校读者我要写书评

暂无评论

Topic tracking language model for speech recognition

引用

COMPUTER SPEECH AND LANGUAGE 2011年第2期25卷 440-461页

作者： Watanabe, Shinji Iwata, Tomoharu Hori, Takaaki Sako, Atsushi Ariki, Yasuo NTT Corp NTT Commun Sci Labs Seika Kyoto 6190237 Japan Kobe Univ Grad Sch Engn Nada Ku Kobe Hyogo 6578501 Japan

In a real environment, acoustic and language features often vary depending on the speakers, speaking styles and topic changes. To accommodate these changes, speech recognition approaches that include the incremental tracking of changing environments have attracted attention. This paper proposes a topic tracking language model that can adaptively track changes in topics based on current text information and previously estimated topic models in an on-line manner. The proposed model is applied to language model adaptation in speech recognition. We use the MIT OpenCourseWare corpus and Corpus of Spontaneous Japanese in speech recognition experiments, and show the effectiveness of the proposed method. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Language model Latent topic model Topic tracking on-line algorithm Speech recognition

来源：评论

学校读者我要写书评

暂无评论

Jitter regulation in an Internet router with delay constraint

引用

JOURNAL OF SCHEDULING 2001年第6期4卷 355-377页

作者： Koga, H Fujitsu Labs Ltd Network Processor Lab Nakahara Ku Kawasaki Kanagawa 2118588 Japan Univ Tokyo Dept Informat Sci Tokyo 113 Japan

To playback multimedia data smoothly via the world-wide Internet, jitter, the variability of delay of individual packets, must be kept low. We examine on-line algorithms in a router to regulate jitter for a given multimedia stream by holding packets in an internal buffer. The previous work solved the problem with focusing only on the buffer size, allowing a packet to stay in the router infinitely long unless the internal buffer is full. This assumption is unrealistic for many real-time applications. Our main contribution is to introduce a new constraint that a packet can stay in the router at most for a constant time which we name the permitted delay time in order to provide the stream communication with real-time property, besides the conventional constraint about the buffer size. We present a nearly optimal on-line algorithm in terms of competitiveness for this new version of the problem. Our analysis yields the result that the competitiveness of on-line algorithms depends on the permitted delay time rather than the buffer size. We also make clear quantitatively how much jitter is removed by our on-line algorithm. Copyright (C) 2001 John Wiley & Sons, Ltd.

关键词： internet jitter control QoS network on-line algorithm competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Online bin packing of fragile objects with application in cellular networks

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2007年第4期14卷 427-435页

作者： Chan, Wun-Tat Chin, Francis Y. -L. Ye, Deshi Zhang, Guochuan Zhang, Yong Zhejiang Univ Coll Comp Sci Hangzhou 310027 Peoples R China Kings Coll London Dept Comp Sci London WC2R 2LS England Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China

We study a specific bin packing problem which arises from the channel assignment problems in cellular networks. In cellular communications, frequency channels are some limited resource which may need to share by various users. However, in order to avoid signal interference among users, a user needs to specify to share the channel with at most how many other users, depending on the user's application. Under this setting, the problem of minimizing the total channels used to support all users can be modeled as a specific bin packing problem as follows: Given a set of items, each with two attributes, weight and fragility. We need to pack the items into bins such that, for each bin, the sum of weight in the bin must be at most the smallest fragility of all the items packed into the bin. The goal is to minimize the total number of bins (i.e., the channels in the cellular network) used. We consider the on-line version of this problem, where items arrive one by one. The next item arrives only after the current item has been packed, and the decision cannot be changed. We show that the asymptotic competitive ratio is at least 2. We also consider the case where the ratio of maximum fragility and minimum fragility is bounded by a constant. In this case, we present a class of online algorithms with asymptotic competitive ratio at most of 1/4+3r/2, for any r > 1.

关键词： bin packing channel assignment on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

The power of α-points in preemptive single machine scheduling

引用

JOURNAL OF SCHEDULING 2002年第2期5卷 121-133页

作者： Schulz, AS Skutella, M Tech Univ Berlin Fachbereich Math D-10623 Berlin Germany MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA

We consider the NP-hard preemptive single-machine scheduling problem to minimize the total weighted completion time subject to release dates. A natural extension of Smith's ratio rule is to preempt the currently active job whenever a new job arrives that has higher ratio of weight to processing time. We prove that the competitive ratio of this simple on-line algorithm is precisely 2. We also show that list scheduling in order of random alpha-points drawn from the same schedule results in an on-line algorithm with competitive ratio (4)/(3). Since its analysis relies on a well-known integer programming relaxation of the scheduling problem, the relaxation has performance guarantee A as well. On the other hand, we show that it is at best an (8)/(7)-relaxation. Copyright (C) 2002 John Wiley Sons, Ltd.

关键词： scheduling theory approximation algorithm on-line algorithm randomized algorithm LP relaxation combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Dynamic TCP acknowledgment with sliding window

引用

THEORETICAL COMPUTER SCIENCE 2009年第8-10期410卷 914-925页

作者： Koga, Hisashi Univ Electrocommun Grad Sch Informat Syst Tokyo 1828585 Japan

The dynamic TCP acknowledgement problem which focuses the acknowledgment mechanism in TCP protocol has been intensively studied in the area of competitive analysis. However, its framework does not consider the sliding window in the TCP protocol that restricts the maximum number of packets that the sender can inject into the network without an acknowledgement. This paper proposes a new problem in which the sliding window is realistically integrated. We study how the ability of on-line algorithms changes, depending on whether the receiver is taught the window size. The greater part of this paper assumes that the window size is a constant integer W. We first show that, if W is given, the optimal on-line algorithm for the previous framework can be extended to our new framework and achieves the optimal competitive ratio of 2. Next we prove that, if W is not given, the lower bound of the competitive ratio for an algorithm class which contains the optimal algorithm for the previous framework depends on the peak packet rate T from the sender and W, and is not better than (T/W+left perpendicularT/Wright perpendicular-1 competitive. Then, we prove that there exists an on-line algorithm that is (inverted right perpendicularT/Winverted left perpendicular + 2)-competitive, when W is unknown. An optimal off-line algorithm is also presented in this paper. Significantly, our problem models the situation in which an on-line algorithm involuntarily transforms the input and processes the modified input without noticing the transformation. (C) 2008 Elsevier B.V. All rights reserved.

关键词： TCP acknowledgement on-line algorithm Competitive analysis Sliding window

来源：评论

学校读者我要写书评

暂无评论

On-line scheduling of two-machine open shops where jobs arrive over time

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 1998年第4期1卷 355-365页

作者： Chen, B Vestjens, APA Woeginger, GJ Univ Warwick Warwick Business Sch Coventry CV4 7AL W Midlands England Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands Graz Univ Technol Inst Math A-8010 Graz Austria

We investigate the problem of on-line scheduling two-machine open shops with the objective of minimizing the makespan. Jobs arrive independently over time, and the existence of a job is not known until its arrival. In the clairvoyant on-line model, the processing requirement of every job becomes fully known at the arrival of the job, while in the non-clairvoyant on-line model, this processing requirement is not known until the job is processed and completed. In both models, scheduling of a job is irrevocable. We study the two-machine open shop problem for both models in the preemptive and in the non-preemptive version. For each of the four variants, we provide an algorithm that is best possible with respect to the worst-case performance. In the clairvoyant on-line model, the best worst-case performance ratios are 5/4 (preemptive) and 3/2 (non-preemptive), and in the non-clairvoyant on-line model, they are 3/2 (preemptive and non-preemptive).

关键词： scheduling open shop makespan on-line algorithm heuristic algorithm worst-case performance ratio worst-case guarantee

来源：评论

学校读者我要写书评

暂无评论

The distributed wireless gathering problem

引用

THEORETICAL COMPUTER SCIENCE 2011年第8-10期412卷 633-641页

作者： Bonifaci, Vincenzo Korteweg, Peter Marchetti-Spaccamela, Alberto Stougie, Leen Max Planck Inst Informat Saarbrucken Germany Eindhoven Univ Technol NL-5600 MB Eindhoven Netherlands Univ Roma La Sapienza Rome Italy Vrije Univ Amsterdam Amsterdam Netherlands CWI NL-1009 AB Amsterdam Netherlands

We address the problem of data gathering in a wireless network using multi-hop communication;our main goal is the analysis of simple algorithms suitable for implementation in realistic scenarios. We study the performance of distributed algorithms, which do not use any form of local coordination, and we focus on the objective of minimizing average flow times of data packets. We prove a lower bound of Omega(n) on the expected competitive ratio of any acknowledgment-based distributed algorithm minimizing the maximum flow time, where n is the number of nodes of the network. Next, we consider a distributed algorithm which sends packets over shortest paths, and we use resource augmentation to analyze its performance when the objective is to minimize the average flow time. If interferences are modeled as in Bar-Yehuda et al. [R. Bar-Yehuda, O. Goldreich, A. Itai, On the time complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization. Journal of Computer and Systems Sciences 45 (1) (1992) 104-126] we prove that the algorithm is (1 + epsilon)-competitive, when the algorithm sends packets a factor O(log(delta/epsilon) log Delta) faster than the optimal off-line solution;here delta is the radius of the network and Delta, the maximum degree. We finally extend this result to a more complex interference model. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Wireless networks Data gathering Approximation algorithm Distributed algorithm on-line algorithm Resource augmentation

来源：评论

学校读者我要写书评

暂无评论

On-line blind equalization via on-line blind separation

引用

SIGNAL PROCESSING 1998年第3期68卷 271-281页

作者： Yang, HH Oregon Grad Inst Dept Comp Sci & Engn Portland OR 97291 USA

A blind equalization method based on the theory of independent component analysis is presented. The blind equalization of an unknown FIR channel with possibly non-minimum phase is formulated as a blind separation problem. The inputs to the equalizer are formed by stacking the fractional samples of the channel outputs. New on-line blind equalization algorithms are developed from on-line blind separation algorithms, thus they inherit the equivariant property from the equivariant blind separation algorithms. Due to this property, the performance of the new algorithms is independent of the channel parameters. Therefore, they are useful for equalizing some ill-conditioned channels. It is shown by simulations that the proposed algorithm works well when the input sequence has some degree of correlation. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： blind equalization blind separation on-line algorithm fractional sample equivariant property condition number

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：