在线算法导论：投资问题与动态输入挑战

需积分: 9 47 浏览量更新于2024-08-02 收藏 417KB PDF 举报

"这是一份关于在线算法的课程讲义，由Michel X Goemans主讲。内容涵盖了在线算法的基础知识，适合讨论班参考。在线算法是算法领域的一个重要分支，自20世纪70年代起在诸如 bin packing 的问题中已有应用，并在Sleator和Tarjan的经典论文发表后成为热门研究领域。这些算法主要处理那些输入数据无法预先全部知晓，而是在执行过程中逐步呈现的问题。" 在线算法是一种处理动态输入数据的算法设计方法，与离线算法不同，后者通常假设所有输入数据在算法开始运行前已完全给出。在线算法必须在每个决策点即时作出决定，而不能等待更多信息出现。这种特性使得在线算法在现实世界中的许多问题中非常适用，如投资问题、网络路由、资源分配等。例如，在投资问题中，投资者希望最大化其投资收益，但投资机会可能随时间变化，无法提前预知。在线算法可以帮助投资者在接收到新的投资机会时做出最佳选择，而无需知道未来的全部情况。类似地，在网络路由中，数据包的产生和传输路径可能随时变化，要求路由器能够实时调整策略。在线算法的性能通常通过比较它们与最优离线算法（知道所有未来信息的算法）的性能来评估。一个关键指标是竞争比，即在线算法的最坏情况性能与最优离线算法的性能之比。如果一个在线算法的竞争比是常数，那么它被认为是具有良好的近似性能。此外，设计在线算法的一个挑战是如何在信息有限的情况下平衡效率和性能。例如，可以采用贪心策略、预测未来输入或使用随机化方法来改善算法的表现。Sleator和Tarjan的开创性工作可能涉及了自调整数据结构，这些结构能够在数据变化时动态优化其性能，这对于理解和改进在线算法至关重要。在线算法在处理不确定性和时间敏感性的任务中扮演着重要角色。它们的研究不仅涉及理论上的挑战，也对实际应用有着深远影响，包括操作系统调度、云计算资源管理、广告投放等多个领域。深入理解在线算法的概念和技术，有助于我们设计出更适应现实世界复杂性的高效解决方案。



The rst phase b egins on the rst page fault.



The

+ 1-st phase starts on the request following the last request of phase



If phase

starts on



then it ends on



;

where



::: 

but



::: 

;

Thus, in a phase, exactly

distinct pages are requested.

Notice that the initial p ortion before the rst phase costs nothing. Hence the cost



is the sum of the costs of

on all phases of



Before wegoany further let us understand the dynamics of a phase by the following

remarks. Let us denote by

the set of pages that were in memory just before phase

begins.

Remark 1

: Once a page has been accessed in a phase it is marked and hence

will remain in memory till the end of the phase. Thus wemaypay a price of 1 for a

page

only if this is is the rst time

is accessed during this phase and if

is not in

memory.

Remark 2

:We claim that at the end (or the beginning) of every phase the

pages in fast memory are all marked and correspond to the

distinct pages requested

during that phase. This can easily be shown by induction. At the b eginning of the

rst phase all pages in fast memory are marked (since no page fault has yet occurred).

By induction, one can thus assume that the rst request in a phase will cause a page

fault (this is true for phase 1 and, for later phases, this follows by induction from the

claim applied to the previous phase). Then, during the phase, the

distinct pages

requested will be marked and will remain in fast memory until the end of the phase,

proving the inductive statement.

Remark 3

:Obviously, the denition of a phase does not depend on the coin-

tosses of

but only on the input sequence. In other words, the same input sequence

will always b e divided in exactly the same wayinto phases regardless of the coin-tosses

. The coin-tosses only aect the dynamics of

's b ehavior within a phase. Also

(see remark 2),

does not dep end on the coin-tosses {

is simply the

distinct

requested pages in phase

;

By these remarks we can fo cus on the

distinct pages accessed in phase

 for

eachsuch page, we only concentrate on the rst time this page is accessed since only

such rst-time requests can cost us anything. We divide such rst time requests into

two categories.



Clean Requests

: These are requests to pages that did not b elong to

.We

haveto pay a price of 1 for eachsuch request regardless of the coin-tosses.



Stale Requests

: These are requests to pages that b elonged to set

at the

beginning of the phase. Unfortunately,such a page mayha

ve been ejected to

make ro om for a clean page. If it is still around, wepay 0 or else wepay1.

Thus our rst ma jor task is to nd the expected cost of a stale request.

Online-9

Since a phase consists of requests to exactly

distinct pages, if there are

clean

requests then there must be

;

stale requests.

6.1 The exp ected cost of a stale request within a phase

Consider a typical stale request



to page

within phase

. Assume there have been

stale requests and

clean requests so far in the phase. We wish to nd the expected

cost of this request in terms of

and

.To do so, we need the probability that page

is still in memory after

stale and

clean requests. Notice that since this is the

rst time we are accessing

is unmarked.

Now what do weknow? Weknow that the pages requested bythe

stale requests

are in

,by denition of a stale request. Furthermore, since requested pages are

marked, the stale pages will not be removed until the end of the phase, therefore they

are in fast memory at time

;

1. This means that b oth fast memory at time

;

and

contain all of these

stale pages. Therefore, the

clean requests now occupy

uniformly distributed slots from the remaining

;

slots. Nowwe can easily compute

the exp ected cost of a stale request. It is the probability that the requested page is

one of the

pages which is no longer in fast memory due to the clean requests. There

are

;

candidates for these pages. Hence:

Exp

(



)] =

;

6.2 Bounding the total cost of

on a phase

We summarize the last section as follows:

Lemma 6

The expectedcost of the

-st stale request in a phase is equal to

;

where

is the number of preceding clean requests in this phase.

Suppose weknow that there are

clean requests within phase

. Recall that

dened purely in terms of the input sequence (see Remark 3) and does not depend

on the coin-tosses.

Then there must b e

;

stale requests within this phase. Clearly the number of

clean requests preceding any stale request is no more than

. Using this and the last

lemma and summing over all

;

stale requests the expected cost of all the stale

requests on the phase is no more than

where

;

:::

;

(

;

Also the cost of all all clean requests is exactly

since each clean request costs 1.

Hence the total exp ected cost of

on phase

is no more than

.Now

(1 +

:::

)



In summary:

Online-10

剩余51页未读，继续阅读

liu_kqhb

粉丝: 0
资源: 2

在线算法导论：投资问题与动态输入挑战

Online-Clustering-Algorithms-and-Reinforcement-Le_algorithms_onl

Machine-Learning-Algorithms-for-Predators-Detection-in-Online-Chat-Conversations-Paper:一份ML论文旨在分析不同领域的社会问题并找到社会公益，SVM，MLP，CNN，GAN的最佳解决方案

Handbook of Research on Soft Computing and Nature-Inspired Algorithms

Competitive Online Algorithms

data-structures-algorithms-go

The Design of Competitive Online Algorithms via a Primal-Dual Approach.pdf

Comprehensive comparison of online ADP algorithms for continuous-time optimal control

OJ-Data-Structures-and-Algorithms:上海交通大学

936-A Review on Multi-Label Learning Algorithms.pdf

LSD-A-Fast-Line-Segment-Detector.rar_单片机开发_MultiPlatform_

最新资源