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

On the remote server problem or more about TCP acknowledgments

THEORETICAL COMPUTER SCIENCE 2006年第1-3期369卷 285-299页

作者： Epstein, Leah Kesselman, Alex Univ Haifa Dept Math IL-31905 Haifa Israel Max Planck Inst Informat Saarbrucken Germany

`We study an on-line problem that is motivated by service calls management in a remote support center. When a customer calls the remote support center of a software company, a technician opens a service request and assigns it a severity rating. This request is then transferred to the appropriate support engineer (SE) who establishes a connection to the customer's site and uses remote diagnostic capabilities to resolve the problem. We assume that the SE can service at most one customer at time and a request service time is negligible. There is a constant setup cost of creating a new connection to a customer's site and a specific cost per request for delaying its service that depends on the severity of the request. The problem is to decide which customers to serve first so as to minimize the incurred cost. This problem with just two customers is a natural generalization of the TCP acknowledgment problem. For the on-line version of the Remote Server Problem (RSP), we present algorithms for the general case and for a special casef of two customers that achieve competitive ratios of exactly 4 and 3, respectively. We also show that no deterministic on-line algorithm can have competitive ratio better than 3. Then we study generalized versions of our model, these are the case of an asymmetric setup cost function and the case of multiple SEs. For the off-line version of the RSP, we derive an optimal algorithm with a polynomial running time for a constant number of customers. (c) 2006 Elsevier B.V. All rights reserved.

关键词： on-line algorithms TCP acknowledgement

来源：评论

学校读者我要写书评

暂无评论

Competitive analysis for the on-line truck transportation problem

引用

JOURNAL OF GLOBAL OPTIMIZATION 2006年第4期34卷 489-502页

作者： Ma, WM Liu, JNK Chen, GQ You, J Tsinghua Univ Sch Econ & Management Beijing 100084 Peoples R China Hong Kong Polytech Univ Dept Comp Kowloon Hong Kong Peoples R China

In this paper, the on-line k-truck transportation problem (k-OLTTP) whose objects are to be transported between the vertices of a given graph on which there are k mobile trucks to be scheduled is proposed. It is motivated by the research concerning on-line k-truck problem and on-line transportation problem. The goal is to minimize the makespan which is consumed to complete some on-line request sequence. Some preliminary knowledge is introduced and the model of k-OLTTP is established firstly. Two versions of a special case of k-OLTTP, namely 1-OLTTP, have been studied and some results are obtained. For the first version, Open-1-OLTTP, a lower bound of competitive ratio 2 is presented and two optimal on-line algorithms, Reschedule Strategy (RS) and Lay Over Strategy (LOS) respectively, are analyzed. For the second version, Close-1-OLTTP, a lower bound of competitive ratio1/2 + 1/2. root 1 + 4/theta, where theta is the ratio between the time consumed by the loaded truck and the empty truck to travel the same distance, is also developed and on-line algorithms RS and LOS are proved to have competitive ratio 2. Finally, some interesting remarks concerning OLTTP and its future research are discussed.

关键词： competitive analysis k-truck transportation problem on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

On Multi-threaded Metrical Task Systems

引用

JOURNAL OF DISCRETE algorithms 2006年第3期4卷 401-413页

作者： Feuerstein, Esteban Seiden, Steven S. de Loma, Alejandro Strejilevich Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Computac Pabellon ICiudad Univ RA-1428 Buenos Aires DF Argentina Louisiana State Univ Dept Comp Sci Baton Rouge LA 70803 USA

Traditionally, on-line problems have been studied under the assumption that there is a unique sequence of requests that must be served. This approach is common to most general models of online computation, such as Metrical Task Systems. However, there exist on-line problems in which the requests are organized in more than one independent thread. In this more general framework, at every moment the first unserved request of each thread is available. Therefore, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities. In this paper we introduce Multi-threaded Metrical Task Systems, that is, the generalization of Metrical Task Systems to the case in which there are many threads of tasks. We study the problem from a competitive analysis point of view, proving lower and upper bounds on the competitiveness of on-line algorithms. We consider finite and infinite sequences of tasks, as well as deterministic and randomized algorithms. In this work we present the first steps towards a more general framework for on-line problems which is not restricted to a sequential flow of information. (C) 2006 Elsevier B.V. All rights reserved.

关键词： Competitive analysis Multi-tasking systems on-line algorithms Paging

来源：评论

学校读者我要写书评

暂无评论

A tight lower bound for job scheduling with cancellation

引用

INFORMATION PROCESSING LETTERS 2006年第1期97卷 1-3页

作者： Zheng, FF Chin, FYL Fung, SPY Poon, CK Xu, YF Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Xian Jiaotong Univ Sch Management Xian 710049 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

The Job Scheduling with Cancellation problem is a variation of classical scheduling problems in which jobs can be cancelled while waiting for execution. In this paper we prove a tight lower bound of 5 for the competitive ratio of any deterministic online algorithm for this problem, for the case where all jobs have the same processing time. (c) 2005 Elsevier B.V. All rights reserved.

关键词： on-line algorithms scheduling lower bounds

来源：评论

学校读者我要写书评

暂无评论

Optimal on-line flow time with resource augmentation

引用

DISCRETE APPLIED MATHEMATICS 2006年第4期154卷 611-621页

作者： Epstein, L van Stee, R Univ Karlsruhe Fak Informat D-76128 Karlsruhe Germany Univ Haifa Dept Math IL-31905 Haifa Israel

We study the problem of scheduling n jobs that arrive over time. We consider a non-preemptive setting on a single machine. The goal is to minimize the total flow time. We use extra resource competitive analysis: an optimal off-line algorithm which schedules-jobs on a single machine is compared to a more powerful on-line algorithm that has l machines. We design an algorithm of competitive ratio 1 + 2 min(Delta(1/l), n(1/l)), where Delta is the maximum ratio between two job sizes, and provide a lower bound which shows that the algorithm is optimal up to a constant factor for any constant l. The algorithm works for a hard version of the problem where the sizes of the smallest and the largest jobs are not known in advance, only A and n are known. This gives a trade-off between the resource augmentation and the competitive ratio. We also consider scheduling on parallel identical machines. In this case the optimal off-line algorithm has m machines and the on-line algorithm has lm machines. We give a lower bound for this case. Next, we give lower bounds for algorithms using resource augmentation on the speed. Finally, we consider scheduling with hard deadlines, and scheduling so as to minimize the total completion time. (c) 2005 Elsevier B.V. All rights reserved.

关键词： flow time on-line algorithms scheduling resource augmentation

来源：评论

学校读者我要写书评

暂无评论

on-line algorithms for networks of temporal constraints

引用

Journal of Discrete algorithms 2003年第3-4期1卷 303-312页

作者： Iacobini, Fabio Dipartimento di Informatica e Sistemistica Università di Roma La Sapienza 00198 Roma Via Salaria 113 Italy Oracle Italia 00144 Roma Via Bombay 1 Italy

We consider a semi-dynamic setting for the Temporal Constraint Satisfaction Problem (TCSP), where we are requested to maintain the path-consistency of a network under a sequence of insertions of new (further) constraints between pairs of variables. We show how to maintain the path-consistency in O(nR) amortized time on a sequence of θ(n) insertions, where n is the number of vertices of the network and R is its range, defined as the maximum size of the minimum interval containing all the intervals of a single constraint. Furthermore we extend our algorithms to deal with more general temporal networks where variables can be points and/or intervals and constraints can also be defined on pairs of different kinds of variables. For such cases our algorithms maintain their performance. Finally, we adapt our algorithms to also maintain the arc-consistency of such generalized networks in O(R) amortized time for θ(n) insertions. © 2003 Elsevier B.V. All rights reserved.

关键词： Network constraints on-line algorithms Temporal constraints

来源：评论

学校读者我要写书评

暂无评论

Optimal on-line flow time with resource augmentation

Optimal on-line flow time with resource augmentation

引用

Workshop on Efficient algorithms (WEA)

作者： Epstein, L van Stee, R Univ Karlsruhe Fak Informat D-76128 Karlsruhe Germany Univ Haifa Dept Math IL-31905 Haifa Israel

关键词： flow time on-line algorithms scheduling resource augmentation

来源：评论

学校读者我要写书评

暂无评论

On-line scheduling to minimize max flow time:: an optimal preemptive algorithm

引用

OPERATIONS RESEARCH LETTERS 2005年第6期33卷 597-602页

作者： Ambühl, C Mastrolilli, M IDSIA Ist Dalle Molle Intelligenza Artificiale CH-6928 Manno Switzerland

We investigate the maximum flow time minimization problem of on-line scheduling jobs on m identical parallel machines. When preemption is allowed, we derive an optimal algorithm with competitive ratio 2-1/m. When preemption is not allowed and m = 2, we show that the First In First Out heuristic achieves the best possible competitive ratio. (c) 2004 Elsevier B.V. All rights reserved.

关键词： scheduling preemption on-line algorithms max flow time

来源：评论

学校读者我要写书评

暂无评论

Universal algorithms for learning theory part I : piecewise constant functions

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2005年第9期6卷 1297-1321页

作者： Binev, P Cohen, A Dahmen, W DeVore, R Temlyakov, V Univ S Carolina Dept Math Ind Math Inst Columbia SC 29208 USA Univ Paris 06 Lab Jacques Louis Lions F-75013 Paris France Rhein Westfal TH Aachen Inst Geomet & Prakt Math D-52056 Aachen Germany

This paper is concerned with the construction and analysis of a universal estimator for the regression problem in supervised learning. Universal means that the estimator does not depend on any a priori assumptions about the regression function to be estimated. The universal estimator studied in this paper consists of a least-square fitting procedure using piecewise constant functions on a partition which depends adaptively on the data. The partition is generated by a splitting procedure which differs from those used in CART algorithms. It is proven that this estimator performs at the optimal convergence rate for a wide class of priors on the regression function. Namely, as will be made precise in the text, if the regression function is in any one of a certain class of approximation spaces (or smoothness spaces of order not exceeding one - a limitation resulting because the estimator uses piecewise constants) measured relative to the marginal measure, then the estimator converges to the regression function (in the least squares sense) with an optimal rate of convergence in terms of the number of samples. The estimator is also numerically feasible and can be implemented on-line.

关键词： distribution-free learning theory nonparametric regression universal algorithms adaptive approximation on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel scheduling problems in next generation wireless networks

引用

NETWORKS 2005年第1期45卷 9-22页

作者： Becchetti, L Leonardi, S Marchetti-Spaccamela, A Vitaletti, A Diggavi, S Muthukrishnan, S Nandagopal, T Univ Roma La Sapienza Rome Italy Lab Syst Informat & Commun Lausanne Switzerland Rutgers State Univ Piscataway NJ 08855 USA Bell Labs Holmdel NJ 07733 USA

Next-generation 3G/4G wireless data networks allow multiple codes (or channels) to be allocated to a single user, where each code can support multiple data rates. Providing fine-grained QoS to users in such networks poses the two-dimensional challenge of assigning both power (rate) and codes to every user. This gives rise to a new class of parallel scheduling problems. We abstract general downlink scheduling problems suitable for proposed next-generation wireless data systems. Our contribution includes a communication-theoretic model for multirate wireless channels. In addition, while conventional focus has been on throughput maximization, we attempt to optimize the maximum response time of jobs, which is more suitable for streams of user requests. We present provable results on the algorithmic complexity of these scheduling problems. In particular, we are able to provide very simple, on-line algorithms for approximating the optimal maximum response time. We also perform an experimental study with realistic data of channel conditions and user requests that strengthens our theoretical results. (C) 2004 Wiley Periodicals, Inc.

关键词： scheduling on-line algorithms wireless networks convex programming resource augmentation CDMA

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：