完全图上无限制性K Node Multicut问题的近似算法

来源 :数学的实践与认识 | 被引量 : 0次 | 上传用户:hogutan
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Node Multicut问题是图论与组合优化的经典问题,无限制性node Multicut问题是它的一类子问题.而无限制性K node multicut问题是无限制性node multicut问题的进一步推广形式.主要研究了完全图上的无限制性k Node Multicut问题.首先将部分点覆盖问题(PVC)多项式时间内归约到此问题证明该问题是NP难的,其次利用完全图独有的性质将该问题转换成特殊的部分击中集合问题(Special Partial Hitting Set Problem)并运用递归的思想和局部比率定理设计了求解该问题的2近似算法.
其他文献
超短线交易指交易频率较高、持仓时间较短的交易行为.在超短线环境下,.财务数据等低频信息难有发挥空间,基本面分析方法失效;股票和股指期货价格变化具有很强的非线性特征,不同的股票及股指期货之间相互交叉影响并构成一个复杂网络,传统的技术分析方法难以适应复杂多变的超短线环境.梳理了基于时间序列模型、随机占优模型、深度学习模型、文本挖掘模型的股票及股指期货超短线预测研究工作,并对已有研究结果进行总结和评述,最后分析了现有研究存在的不足并提出研究展望.
针对已有的基于经典粗糙集理论的组合预测单项模型选择方法存在的问题与不足,引入邻域粗糙集理论加以改进.首先采用kmeans算法对决策表进行适应性改进,使其符合邻域粗糙集的理论框架;然后,根据不同属性集中对应属性值的分布范围对每个属性集分别设置不同的邻域半径,使粒化结果更为科学合理;最后,结合均方根误差构造出新的属性重要度使其包含信息更为全面,有利于提高预测精度.分别采用四种组合预测方法对不经选择的模型集、原方法和改进方法得到的模型集进行组合并对比分析,验证了模型选择的必要性与改进方法的有效性..
研究了电商平台是否向零售商共享优质物流服务的问题.电商平台的优质物流服务能够使零售商产品更具有市场竞争力,但零售商需要支付更高的物流服务费用.运用效用理论和博弈论分析工具,发现当平台物流竞争力不强且渠道差异化程度较高时,电商平台可以从物流服务共享中获益.零售商使用平台自建物流不一定会带来需求和利润的提升.此外,当满足特定条件时,电商平台和零售商可以实现双赢.研究结果能够为电商平台的物流服务共享决策提供一定的理论支持和指导.
研究一类非齐次p-Kirchhoff型椭圆方程组{-M(∫RN|x|-ap|▽u|pdx)div(|x|-ap|▽u|p-2▽u)=α/α+βH(x)|u|α-2u|v|β+λh1(x)|u|q-2u+l1(x),-M(∫RN|x|-ap|▽v|pdx)div(|x|-ap|▽v|p-2▽v)=β/α+βH(x)|v|β-2v|u|α+μh2(x)|v|q-2v+l2(x),u(x)→0,v(x)→0,|x|→∞,x ∈ RN,其中λ,μ>0,1<p<N,1<q<p<p(k+1)<α+β<p*=Np/N-
在逐次Ⅰ型混合截尾样本下,研究具有相关性应力-强度模型的可靠性.假设应力和强度分布为参数不同的指数分布,选用FGM copula作为连接函数构造联合分布,得到参数和可靠度的极大似然估计(MLEs)、贝叶斯估计和对应渐近置信区间、HPD置信区间.通过Monte Carlo模拟方法,获得不同样本量不同截尾方案下估计值的数值模拟结果,通过比较各估计的均方误差和覆盖率来评价估计效果.结果表明估计效果良好.随着样本量的增加,均方误差逐渐减小,置信区间长度缩短.最后选用一组真实数据,模型应用到实际案例中,说明提出模型
在“双循环”新发展格局下,研究了新疆居民消费与经济发展的协调促进关系.以人均地区生产总值作为新疆经济增长指标,农村家庭和城镇家庭平均每人全年消费性支出作为新疆居民消费指标,选用1997-2018年的时间序列数据,基于VAR模型,通过格兰杰因果检验、脉冲响应和方差分解探究新疆城乡居民消费与地区经济增长的长期动态关系.研究显示:新疆居民消费与地区经济增长之间存在一定程度的相互促进作用;地区经济增长对新疆居民消费的促进效果较弱;农村居民消费和城镇居民消费对经济的促进作用,前者大于后者.进一步根据分析结果给出了相
首先采用Riccati方程的解的性质和试探函数法找到了 Riccati方程的八种类型的显式新精确解.其次运用李群分析法获得了 KdV-Burgers-Kuramoto方程的约化方程和群不变解.然后利用Riccati方程的八种类型的显式新精确解和广义Tanh函数法给出了约化方程的多种类型的显式新精确解.最后将Riccati方程的八种类型的显式新精确解与李群分析法和广义Tanh函数法相结合,得到了 KdV-Burgers-Kuramoto方程的多种类型的显式新行波解.这些技巧和方法可以用于求解其它一些非线性偏
为了全面提高复杂装备费用的合理使用度,构建了复杂装备费用测算的灰色自记忆耦合模型,借助自记忆预测技术来提高其预测精度.模型通过有机耦合自记忆原理与传统灰色模型,综合了两者各自的优势.系统的自记忆方程包含多个时次初始场而不仅是单个时次初始场,从而克服了传统灰色预测模型对初值比较敏感的弱点.通过对复杂装备费用测算的两个案例分析,验证了该耦合模型由于充分挖掘了多时点系统历史资料,能够紧密捕获复杂系统的演化路径.三个误差分析指标综合验证了灰色自记忆耦合模型的可靠性和稳健性,以及较其他传统统计方法和灰色预测模型明显
基于对单叶调和函数系数估计的猜想,对定义在单位圆盘上的调和映照类的星象半径进行研究.首先研究系数在满足一定条件下的调和映照类的星象半径,得到其精确的估计,其次研究两类调和函数的卷积的星象半径,所得到的结论也是精确的.
充分利用故障暂态信息可有效提高小电流接地系统故障区段定位的成功率,暂态零序电流在故障点前后差异较大,基于此特点对故障区段定位,零序电流波形在故障点同侧相似,在故障点异侧差异大.计算了故障线路各区段波形相关系数,选择波形相关系数为负值的区段为故障区段.数据模型表明,选线方案在高阻接地时依然具有较高的准确性,与传统选线方法相比,该方法利用了更丰富更全面的电气特征,进一步提高了选线准确率与可靠性.定位方案在不同位置、不同接地电阻、不同故障初相角下的情况均适用.