资源描述：
《从算法设计到机制设计_张国川》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、从算法设计到机制设计张国川研究组成员：叶德仕、陈林、程郁琨、余炜、罗文昌中国运筹学会2012学术年会，沈阳，10月20日AlanTuring(1912-1954)•图灵机•可计算性•计算的难解性复杂性分类•Cook(1971):Cook(1971):33--SATSAT是NPNP--完全的•Karp(1972):21个NP-完全问题•．．．P≠NP•计算资源的匮乏•困难问题–多项式时间近似算法–指数时间的精确算法–解的质量与时间成本的平衡多项式时间
2、
3、巨大的间隙巨大的间隙
4、
5、指数时间多项式时间下的计算效能•近
6、似比•近似方案近似方案((PTAS)•EPTAS•完全近似方案完全近似方案((FPTAS)P≠NP下的效能极限•没有FPTAS•没有EPTAS•没有PTAS•近似比的下界CdilitCtitCardinalityConstraints•Wehavemidenticalmachinesandnjbjobs•Machineicanacceppptuptokijobs•GGlfidGoal:findaschdlhedulemeetiihngthecardinalityconstraintssothatthemake
7、spanisminimizedAikAquickremark•Youmayhaveinmindthe33--partitionproblem,fromwhichwemovefurthertok-partition,ffyinallywearriveatk-partitionithatisexactlytheproblemwejjtjustiitddntroducedPreviouslyresults•KK--partitionpartition4/3[Bable,Kellerer,Kotov,1998]7/6
8、fork=3,[fork=3,[BableBable,,KellererKellerer,1999],1999]•K--parpartitioniFPTASforfixedm[Woegggingerer20052005]3[Zhangetal.2009]2[Barna,Aravind2010](moregeneral)3/2[[KellererKellerer,,KotovKotov,2011],2011]OtiOurcontribbtutiionEPTASNonNon--standardILPformula
9、tion+BeststandardILPformulation+Best--Fit+Fit+GreedyRounding精确算法的计算效率•伪多项式时间•指数时间•双指数时间指数运行时间假设(ExponentialTimeHypothesis)•Impagliazzo,Paturi,andZane(2001)存在s>0，使得33--CNFCNF--SASAT没有如下时snO(1)间的精确算法2(n+m)..•Lokshtanov,,,Marx,SaurabhSaurabh(()2011)Lowerbounds
10、basedontheETH建立从33--SASAT的线性规模的归约另一个影响计算效能的因素信息•不完全信息下的算法设计与分析V在线算法V鲁棒优化V随机优化算法博弈论(AGT)•纳什均衡的计算及复杂性•算法机制设计•系统有效性分析“稳定”装箱•Input:asetofitems{a,a,…,a},12neachofsizeatmost1,andaninfinitenumberofidenticalbins•OttOutput:afeasibliblepackingithwithammmmminimumnumbe
11、roffbinsused换个角度•Thereisonedecisionmakerwhodoesnottkttakecarefthoftheowniitnteresttfofeachitem•Whathappenedifeveryitemishandledbyanagent?•Whatafeasiblepackinglookslikeinthhiscase?分摊机制•Howtodesignasharingpolicysothtthatanystblstablepackingisnotfarawayypfroma
12、socialoptimum?•PPptProportiinlonalshshiarinn(g(Bilo2006)•Identicalsharing(Hanetal.2012)“厌恶型”选址博弈问题描述•AAidAresidentilttialareaasanetwork•Thelocalgovernmentplanstobuildagarbagedumpinthisareagarbagedumpin
