期刊文献+
共找到7篇文章
< 1 >
每页显示 20 50 100
The LP-rounding plus greed approach for partial optimization revisited
1
作者 Peng ZHANG 《Frontiers of Computer Science》 SCIE EI CSCD 2022年第1期67-75,共9页
There are many optimization problems having the following common property:Given a total task consisting of many subtasks,the problem asks to find a solution to complete only part of these subtasks.Examples include the... There are many optimization problems having the following common property:Given a total task consisting of many subtasks,the problem asks to find a solution to complete only part of these subtasks.Examples include the k-Forest problem and the k-Multicut problem,etc.These problems are called partial optimization problems,which are often NP-hard.In this paper,we systematically study the LP-rounding plus greed approach,a method to design approximation algorithms for partial optimization problems.The approach is simple,powerful and versatile.We show how to use this approach to design approximation algorithms for the k-Forest problem,the k-Multicut problem,the k-Generalized connectivity problem,etc. 展开更多
关键词 k-Forest k-Multicut partial optimization lp-rounding Greedy algorithm Approximation algorithm
原文传递
树上限制性k-node multi-multiway cut问题的近似算法
2
作者 杨惠娟 《洛阳理工学院学报(自然科学版)》 2020年第3期89-93,共5页
k-node multi-multiway cut问题作为multicut问题和multiway cut问题的推广问题是NP难的。首先,将k-严格顶点覆盖归约到此问题说明该问题与k-严格顶点覆盖具有同样的近似值。其次,运用贪婪策略设计了近似值为k的算法。最后,运用线性规划... k-node multi-multiway cut问题作为multicut问题和multiway cut问题的推广问题是NP难的。首先,将k-严格顶点覆盖归约到此问题说明该问题与k-严格顶点覆盖具有同样的近似值。其次,运用贪婪策略设计了近似值为k的算法。最后,运用线性规划的LP-rounding技术改进算法得到近似值为min{2(q-k+1),k}的多项式时间算法。 展开更多
关键词 k-node multi-multiway cut问题 近似算法 lp-rounding技术
下载PDF
一般图上的限制性k node multi-multiway cut问题的启发式算法
3
作者 杨惠娟 胡晓飞 段江梅 《贵阳学院学报(自然科学版)》 2019年第4期12-15,32,共5页
限制性k node multi-multiway cut问题作为multiway cut问题的自然推广是NP难的。论文研究了一般图上的限制k node multi-multiway cut问题,首先用LP-relaxation和LP-rounding技术确定至少断开的k个终端集合,其次用改进的域增长技术将... 限制性k node multi-multiway cut问题作为multiway cut问题的自然推广是NP难的。论文研究了一般图上的限制k node multi-multiway cut问题,首先用LP-relaxation和LP-rounding技术确定至少断开的k个终端集合,其次用改进的域增长技术将求得的分数解调整为整数解从而设计了该问题的一个启发式算法。 展开更多
关键词 k node multi-multiway cut问题 启发式算法 lp-rounding技术 LP-relaxation技术
下载PDF
Robust Correlation Clustering Problem with Locally Bounded Disagreements
4
作者 Sai Ji Min Li +1 位作者 Mei Liang Zhenning Zhang 《Tsinghua Science and Technology》 SCIE EI CAS CSCD 2024年第1期66-75,共10页
Min-max disagreements are an important generalization of the correlation clustering problem(CorCP).It can be defined as follows.Given a marked complete graph G=(V,E),each edge in the graph is marked by a positive labe... Min-max disagreements are an important generalization of the correlation clustering problem(CorCP).It can be defined as follows.Given a marked complete graph G=(V,E),each edge in the graph is marked by a positive label"+"or a negative label"_"based on the similarity of the connected vertices.The goal is to find a clustering C of vertices V,so as to minimize the number of disagreements at the vertex with the most disagreements.Here,the disagreements are the positive cut edges and the negative non-cut edges produced by clustering C.This paper considers two robust min-max disagreements:min-max disagreements with outliers and min-max disagreements with penalties.Given parameter δ∈(0,1/14),we first provide a threshold-based iterative clustering algorithm based on LP-rounding technique,which is a(1/δ,7/(1-14δ))-bi-criteria approximation algorithm for both the min-max disagreements with outliers and the min-max disagreements with outliers on one-sided complete bipartite graphs.Next,we verify that the above algorithm can achieve an approximation ratio of 21 for min-max disagreements with penalties when we set parameter δ=1/21. 展开更多
关键词 min-max disagreements OUTLIERS PENALTIES approximation algorithm lp-rounding
原文传递
环上的最大流通量问题 被引量:1
5
作者 陈智斌 李建平 《云南大学学报(自然科学版)》 CAS CSCD 2004年第4期288-291,共4页
研究一个新颖的最大流通量问题,集中考察在SONET环上的情形,即令R为SONET上的一个环,其顶点集{0,1,2,…,n-1},每条边ei=(i,i+1)和边上的整数容量限制di及m个所要求通过的点对{si,ti}(1≤i≤m且si≠ti).要求一个方案,选择所要求的m个点... 研究一个新颖的最大流通量问题,集中考察在SONET环上的情形,即令R为SONET上的一个环,其顶点集{0,1,2,…,n-1},每条边ei=(i,i+1)和边上的整数容量限制di及m个所要求通过的点对{si,ti}(1≤i≤m且si≠ti).要求一个方案,选择所要求的m个点对中的某些点对(也许是所有的),此时每个点对就由一条道路相连,在通过环上每条边的总条数不超过其边整数容量限制的条件下,最大化所用到的道路条数.通过引入单方向概念并应用LP-rounding技巧,证明了环上的单方向最大流通量问题属于P类,即可有多项式时间算法求解,并因此获得了环上最大流通量问题的一个2-近似多项式算法. 展开更多
关键词 最大流通量 lp-rounding技巧 近似算法 NP-困难
原文传递
An improved per-scenario bound for the two-stage stochastic facility location problem
6
作者 WU Chen Chen DU Dong Lei XU Da Chuan 《Science China Mathematics》 SCIE CSCD 2015年第1期213-220,共8页
We study the two-stage stochastic facility location problem(2-SFLP)by proposing an LP(location problem)-rounding approximation algorithm with 2.3613 per-scenario bound for this problem,improving the previously best pe... We study the two-stage stochastic facility location problem(2-SFLP)by proposing an LP(location problem)-rounding approximation algorithm with 2.3613 per-scenario bound for this problem,improving the previously best per-scenario bound of 2.4957. 展开更多
关键词 facility location problem approximation algorithm lp-rounding algorithm
原文传递
An Approximation Algorithm for the Risk-Adjusted Two-Stage Stochastic Facility Location Problem with Penalties
7
作者 Jiating Shao Dachuan Xu 《Journal of the Operations Research Society of China》 EI 2013年第3期339-346,共8页
In this paper,we consider the risk-adjusted two-stage stochastic facility location problem with penalties(RSFLPP).Using the monotonicity and positive homogeneity of the risk measure function,we present an LP-roundin... In this paper,we consider the risk-adjusted two-stage stochastic facility location problem with penalties(RSFLPP).Using the monotonicity and positive homogeneity of the risk measure function,we present an LP-rounding-based 6-approximation algorithm. 展开更多
关键词 Facility location Approximation algorithm lp-rounding Risk-adjusted
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部