这个又是哪位老师？小泽老师？滨崎老师？ - 未名空间MITBBS历史存档

这个又是哪位老师？小泽老师？滨崎老师？# Joke - 肚皮舞运动

M*a2014-01-05 08:01

1 楼

A service system has n DIFFERENT servers; each one provides one unique
service to the clients. Clients submit requests to the service system, each
request may have multiple sub-requests; each sub-request is to a DIFFERENT
server. A request can have at most n sub-requests. Each sub-request takes 1
time unit to finish at any server. The finish time of a request is the
finish time of its LAST finished sub-request. The notation "total request
finish time" is the sum of all requests' finish time.
1. Design an off-line algorithm to reorder the execution order of sub-
requests on the servers, so that "total request finish time" can be
minimized (if multiple solutions exist, only one solution is enough).
Discuss the complexity of the algorithm.
2. Discuss feasible algorithms that can achieve sub-optimal solutions with N
~ 10000.
3. Suppose the sub-requests can be queued at each server, and the servers
are running all the time. Discuss feasible on-line algorithms that can
achieve sub-optimal solutions with N ~ 10000.

l*z2014-01-05 08:01

2 楼

【以下文字转载自 MyActivity 讨论区】
发信人: mitbbs (未名空间), 信区: MyActivity
标题: ★★2010年度评选活动开始了！★★
发信站: BBS 未名空间站 (Tue Dec 21 00:52:24 2010, 美东)
为表彰先进，促进版主之间的学习交流，调动网友积极性，同时向大家展示论坛版
主及网友的风采，回顾一年内热点事件，特举办2010年度买买提年度评选活动！
活动分站务举办和各版承办两部分
一、站务举办
2010年十大优秀版主
2010年十大活跃网友
2010年十大风云事件
活动版面：MyActivity
活动流程：
第一阶段：推荐阶段(即日起至2011-1-10(美东时间))
⑴推荐格式：
优秀版主/活跃网友/风云事件：
理由：
⑵参选条件：
优秀版务参选条件：整理版面及精华；及时mark好帖；积极举办活动；曾被提名为月优
秀版务；2010年内无重大处罚记录
活跃网友参选条件：经常参与讨论；常有文章上首页
风云事件参选条件：本站原创；众多网友参与讨论
第二阶段：投票阶段(2011-1-11至2011-1-21(美东时间))
第三阶段：颁奖阶段(2011-1-22至2011-1-25(美东时间))
十大优秀版务：获奖版务得2000伪币+任意形象秀着装一套
十大活跃网友：获奖网友得1000伪币+年度活跃网友勋章一枚
十大风云事件：所在版面得1000伪币
二、版面承办
2010年买买提十佳厨艺奖
2010年买买提十佳摄影奖
2010年买买提十佳……
活动版面：各版面
活动流程：
即日起，各版务根据版面特点，在版面举办2010年度买买提十佳*奖评比活动，活动结
束后，到WBCenter申请，审批通过(截止2011-1-30(美东时间))后，站务发奖给申请版
面及获奖ID各200伪币，获奖ID另得十佳*奖勋章一枚

M*82014-01-05 08:01

3 楼

r*s2014-01-05 08:01

4 楼

这题有意思，什么叫online,什么叫offline？

each
1

【在 M*******a 的大作中提到】

: A service system has n DIFFERENT servers; each one provides one unique
: service to the clients. Clients submit requests to the service system, each
: request may have multiple sub-requests; each sub-request is to a DIFFERENT
: server. A request can have at most n sub-requests. Each sub-request takes 1
: time unit to finish at any server. The finish time of a request is the
: finish time of its LAST finished sub-request. The notation "total request
: finish time" is the sum of all requests' finish time.
: 1. Design an off-line algorithm to reorder the execution order of sub-
: requests on the servers, so that "total request finish time" can be
: minimized (if multiple solutions exist, only one solution is enough).

l*z2014-01-05 08:01

5 楼

请支持版主泡泡，繁荣时尚，美女们可以多吃包子啦！！

c*y2014-01-05 08:01

6 楼

第一问类似于给定workload然后装箱（n个）问题。这个是不是纯静态优化的问题？应
当有最优解，不过没学过不知道咋做。
第二问是dynamic workload scheduling/balancing，估计最后是想让average
response delay比较短？因为不能预知接下来的input，所以optimal就不大可能。这个
换我那就只能xb说了，等大牛解释。
楼主是面的

each
1

【在 M*******a 的大作中提到】

: A service system has n DIFFERENT servers; each one provides one unique
: service to the clients. Clients submit requests to the service system, each
: request may have multiple sub-requests; each sub-request is to a DIFFERENT
: server. A request can have at most n sub-requests. Each sub-request takes 1
: time unit to finish at any server. The finish time of a request is the
: finish time of its LAST finished sub-request. The notation "total request
: finish time" is the sum of all requests' finish time.
: 1. Design an off-line algorithm to reorder the execution order of sub-
: requests on the servers, so that "total request finish time" can be
: minimized (if multiple solutions exist, only one solution is enough).

p*l2014-01-05 08:01

7 楼

hehe, thank you, mm.
Here is the link:
http://www.mitbbs.com/article_t/MyActivity/12517489.html
2000伪币哦，真要拿到了就都捐出来搞活动，黑黑～

l*62014-01-05 08:01

8 楼

If all subrequests of a request are flat and requests are independent
offline algorithm:
sort requests by number of subrequest than greedy assign subrequests to most
idle server
onlie algorithm:
greedy assign subrequests to most idle server

l*z2014-01-05 08:01

9 楼

嗬嗬，俺早在那上面顶你了！拿奖了你得奔一个，俺还木有看过你的片片呢！！
嗯，还该顶公主作十大网友，她对花生的贡献很大啊！！

【在 p*********l 的大作中提到】

: hehe, thank you, mm.
: Here is the link:
: http://www.mitbbs.com/article_t/MyActivity/12517489.html
: 2000伪币哦，真要拿到了就都捐出来搞活动，黑黑～

r*s2014-01-05 08:01

10 楼

每个server都不一样，没法greedy吧
"each one provides one unique
service to the clients"

b*s2014-01-05 08:01

11 楼

agree! support Gilda!

【在 l*****z 的大作中提到】

: 嗬嗬，俺早在那上面顶你了！拿奖了你得奔一个，俺还木有看过你的片片呢！！
: 嗯，还该顶公主作十大网友，她对花生的贡献很大啊！！

F*m2014-01-05 08:01

12 楼

谢谢分享

l*z2014-01-05 08:01

13 楼

你出面号召下？领导面子大啊！！

【在 b*********s 的大作中提到】

: agree! support Gilda!

f*e2014-01-05 08:01

14 楼

不能证明approximation ratio的都不是好题。

each
1

【在 M*******a 的大作中提到】

: A service system has n DIFFERENT servers; each one provides one unique
: service to the clients. Clients submit requests to the service system, each
: request may have multiple sub-requests; each sub-request is to a DIFFERENT
: server. A request can have at most n sub-requests. Each sub-request takes 1
: time unit to finish at any server. The finish time of a request is the
: finish time of its LAST finished sub-request. The notation "total request
: finish time" is the sum of all requests' finish time.
: 1. Design an off-line algorithm to reorder the execution order of sub-
: requests on the servers, so that "total request finish time" can be
: minimized (if multiple solutions exist, only one solution is enough).

p*l2014-01-05 08:01

15 楼

我已经去投Gilda啦～

【在 l*****z 的大作中提到】

: 你出面号召下？领导面子大啊！！

o*g2014-01-05 08:01

16 楼

sub-request之间的关系是怎样的？是可以同时进行的？还是必须顺序进行？
如果可以同时进行，那就简单了。如果必须顺序做，那就复杂了。

each
1

【在 M*******a 的大作中提到】

: A service system has n DIFFERENT servers; each one provides one unique
: service to the clients. Clients submit requests to the service system, each
: request may have multiple sub-requests; each sub-request is to a DIFFERENT
: server. A request can have at most n sub-requests. Each sub-request takes 1
: time unit to finish at any server. The finish time of a request is the
: finish time of its LAST finished sub-request. The notation "total request
: finish time" is the sum of all requests' finish time.
: 1. Design an off-line algorithm to reorder the execution order of sub-
: requests on the servers, so that "total request finish time" can be
: minimized (if multiple solutions exist, only one solution is enough).

l*z2014-01-05 08:01

17 楼

那俺也去吧！！

【在 p*********l 的大作中提到】

: 我已经去投Gilda啦～

M*a2014-01-05 08:01

18 楼

可以同时进行也可以不同时进行
Depend on the availability of servers

【在 o***g 的大作中提到】

: sub-request之间的关系是怎样的？是可以同时进行的？还是必须顺序进行？
: 如果可以同时进行，那就简单了。如果必须顺序做，那就复杂了。
:
: each
: 1

C*32014-01-05 08:01

19 楼

顶！

o*g2014-01-05 08:01

20 楼

你的意思是所有sub request之间都没有约束关系，那就简单了。并且所有sub request
都是运行1 unit时间。
那就是所有request都变成sub request，然后找哪个server上排了最多sub request，
这个就是最长时间了

【在 M*******a 的大作中提到】

: 可以同时进行也可以不同时进行
: Depend on the availability of servers

M*a2014-01-05 08:01

21 楼

The notation "total request finish time" is the sum of all requests' finish
time.
Not
Earliest time that all request can be finished.

request

【在 o***g 的大作中提到】

: 你的意思是所有sub request之间都没有约束关系，那就简单了。并且所有sub request
: 都是运行1 unit时间。
: 那就是所有request都变成sub request，然后找哪个server上排了最多sub request，
: 这个就是最长时间了