Network design for information networks

近似算法 计算机科学 斯坦纳树问题 数学优化 设施选址问题 最优化问题 随机优化 集合(抽象数据类型) 网络规划与设计 算法 数学 计算机网络 程序设计语言
作者
Ara Hayrapetyan,Chaitanya Swamy,Éva Tardos
出处
期刊:Symposium on Discrete Algorithms 卷期号:: 933-942 被引量:84
标识
DOI:10.5555/1070432.1070567
摘要

We define a new class of network design problems motivated by designing information networks. In our model, the cost of transporting flow for a set of users (or servicing them by a facility) depends on the amount of information requested by the set of users. We assume that the aggregation cost follows economies of scale, that is, the incremental cost of a new user is less if the set of users already served is larger. Naturally, information requested by some sets of users might aggregate better than that of others, so our cost is now a function of the actual set of users. not just their total demand.We provide constant-factor approximation algorithms to two important problems in this general model. In the Group Facility Location problem, each user needs information about a resource. and the cost is a linear function of the number of resources involved (instead of the number of clients served). The Dependent Maybecast Problem extends the Karger-Minkoff maybecast model to probabilities with limited correlation and also contains the 2-stage stochastic optimization problem as a special case. We also give an O(ln n)-approximation algorithm for the Single Sink Information Network Design problem.We show that the Stochastic Steiner Tree problem can be approximated by dependent maybecast, and using this we obtain an O(1)-approximation algorithm for the k-stage stochastic Steiner tree problem for any fixed k. This is the first approximation algorithm for multi-stage stochastic optimization. Our algorithm allows scenarios to have different inflation factors, and works for any distribution provided that we can sample the distribution.

科研通智能强力驱动
Strongly Powered by AbleSci AI
更新
PDF的下载单位、IP信息已删除 (2025-6-4)

科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
优雅的平安完成签到 ,获得积分10
3秒前
南浔完成签到 ,获得积分10
4秒前
zzx完成签到 ,获得积分10
5秒前
虚心的幻梅完成签到 ,获得积分10
6秒前
欧皇发布了新的文献求助50
6秒前
量子星尘发布了新的文献求助10
9秒前
Jasper应助科研通管家采纳,获得10
9秒前
勤恳的书文完成签到 ,获得积分10
10秒前
无敌大流流完成签到,获得积分10
11秒前
无辜凝天完成签到,获得积分10
14秒前
秋思冬念完成签到 ,获得积分10
16秒前
17秒前
ioio完成签到 ,获得积分10
18秒前
清爽的火车完成签到 ,获得积分10
20秒前
MRQ完成签到 ,获得积分10
23秒前
hyd1640完成签到,获得积分10
24秒前
金枪鱼子完成签到,获得积分10
24秒前
默默完成签到 ,获得积分10
29秒前
聪明勇敢有力气完成签到 ,获得积分10
30秒前
金枪鱼子发布了新的文献求助10
31秒前
buerzi完成签到,获得积分10
32秒前
leo完成签到,获得积分10
33秒前
33秒前
dldldl完成签到,获得积分10
35秒前
爱书儿的小周完成签到,获得积分10
36秒前
Noah完成签到 ,获得积分0
38秒前
小伊001完成签到,获得积分10
40秒前
欧皇完成签到,获得积分20
40秒前
心心完成签到 ,获得积分10
47秒前
量子星尘发布了新的文献求助10
48秒前
娇娇大王完成签到,获得积分10
51秒前
woshiwuziq完成签到 ,获得积分10
51秒前
自然白秋完成签到,获得积分20
52秒前
韦老虎完成签到,获得积分20
54秒前
自然白秋发布了新的文献求助20
56秒前
Krim完成签到 ,获得积分10
59秒前
大个应助金枪鱼子采纳,获得10
1分钟前
喜悦向日葵完成签到 ,获得积分10
1分钟前
淡然的糖豆完成签到 ,获得积分10
1分钟前
E0702完成签到,获得积分10
1分钟前
高分求助中
【提示信息,请勿应助】关于scihub 10000
A new approach to the extrapolation of accelerated life test data 1000
Coking simulation aids on-stream time 450
北师大毕业论文 基于可调谐半导体激光吸收光谱技术泄漏气体检测系统的研究 390
Phylogenetic study of the order Polydesmida (Myriapoda: Diplopoda) 370
Robot-supported joining of reinforcement textiles with one-sided sewing heads 360
Novel Preparation of Chitin Nanocrystals by H2SO4 and H3PO4 Hydrolysis Followed by High-Pressure Water Jet Treatments 300
热门求助领域 (近24小时)
化学 材料科学 医学 生物 工程类 有机化学 生物化学 物理 内科学 纳米技术 计算机科学 化学工程 复合材料 遗传学 基因 物理化学 催化作用 冶金 细胞生物学 免疫学
热门帖子
关注 科研通微信公众号,转发送积分 4015585
求助须知:如何正确求助?哪些是违规求助? 3555572
关于积分的说明 11318138
捐赠科研通 3288762
什么是DOI,文献DOI怎么找? 1812284
邀请新用户注册赠送积分活动 887882
科研通“疑难数据库(出版商)”最低求助积分说明 812015