期刊文献+
共找到4篇文章
< 1 >
每页显示 20 50 100
Multicut L-Shaped Algorithm for Stochastic Convex Programming with Fuzzy Probability Distribution
1
作者 Miaomiao Han Xinshun MA 《Open Journal of Applied Sciences》 2012年第4期219-222,共4页
Two-stage problem of stochastic convex programming with fuzzy probability distribution is studied in this paper. Multicut L-shaped algorithm is proposed to solve the problem based on the fuzzy cutting and the minimax ... Two-stage problem of stochastic convex programming with fuzzy probability distribution is studied in this paper. Multicut L-shaped algorithm is proposed to solve the problem based on the fuzzy cutting and the minimax rule. Theorem of the convergence for the algorithm is proved. Finally, a numerical example about two-stage convex recourse problem shows the essential character and the efficiency. 展开更多
关键词 STOCHASTIC CONVEX PROGRAMMING fuzzy probability DISTRIBUTION TWO-STAGE problem multicut l-shaped algorithm
在线阅读 下载PDF
树上推广的Multicut问题的近似算法 被引量:3
2
作者 张鹏 《计算机研究与发展》 EI CSCD 北大核心 2008年第7期1195-1202,共8页
给定边上有费用的树T,终端集合族X={S1,S2,…,Sl},推广的Multicut问题询问费用最小的边集,使得在树上删除边集中的边能够断开每一个终端集.推广的Multicut问题有其独立的研究意义,因为该问题分别是经典的Multicut问题和Multiway Cut问... 给定边上有费用的树T,终端集合族X={S1,S2,…,Sl},推广的Multicut问题询问费用最小的边集,使得在树上删除边集中的边能够断开每一个终端集.推广的Multicut问题有其独立的研究意义,因为该问题分别是经典的Multicut问题和Multiway Cut问题的自然推广,同时也是推广的Steiner Forest问题的对偶问题.树上推广的Multicut问题的完全版本可以归约到树上经典的Multicut问题近似求解.对于该问题的Prize-collecting版本,给出了原始-对偶的3倍近似算法.对于该问题的k版本,通过非一致的途径给出了近似比为min{2(l-k+1),k}的近似算法.以及找到了该问题的k版本与k-稠密子图问题之间的一个有趣的联系,从而证明了将k版本的树上推广的Multicut问题近似到O(n1/6-ε)以内是困难的(对某个小的常数ε>0). 展开更多
关键词 multicut 线性规划 近似算法 组合优化
在线阅读 下载PDF
树上的限制性node multicut问题 被引量:2
3
作者 杨惠娟 《大理学院学报(综合版)》 CAS 2014年第12期21-25,共5页
割集问题在图论和组合优化中占有重要地位,限制性node multicut问题是割集问题的一类比较重要的推广问题。树上的限制性node multicut问题是值得研究的一个问题。首先说明此问题是NP难的,其次用线性规划理论中的互补松弛条件设计了一个... 割集问题在图论和组合优化中占有重要地位,限制性node multicut问题是割集问题的一类比较重要的推广问题。树上的限制性node multicut问题是值得研究的一个问题。首先说明此问题是NP难的,其次用线性规划理论中的互补松弛条件设计了一个近似值2且时间复杂度为O(max{kn,n log n})的算法。并进一步说明了通过算法得到的解具有半整数的性质。 展开更多
关键词 限制性node multicut 近似算法 互补松弛条件
在线阅读 下载PDF
一般图上的限制性k-node multicut问题 被引量:1
4
作者 杨惠娟 董延寿 严佩升 《宜宾学院学报》 2018年第6期53-56,共4页
对图论和组合优化经典multicut和multiwaycut问题中的一般图上的限制性k-node multicut问题进行讨论,该问题作为multicut问题的推广问题,它是NP难的,运用线性规划理论的知识设计了一个近似值为O((qlogq)(1/2))多项式时间算法.
关键词 限制性k-nodemulticut 近似算法 线性规划
在线阅读 下载PDF
上一页 1 下一页 到第
使用帮助 返回顶部