The LP-rounding plus greed approach for partial optimization revisited

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-node multi-multiway cut问题的近似算法

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问题的启发式算法

限制性k node multi-multiway cut问题作为multiway cut问题的自然推广是NP难的。论文研究了一般图上的限制k node multi-multiway cut问题,首先用LP-relaxation和LP-rounding技术确定至少断开的k个终端集合,其次用改进的域增长技术将求得的分数解调整为整数解从而设计了该问题的一个启发式算法。

Robust Correlation Clustering Problem with Locally Bounded Disagreements

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.

环上的最大流通量问题

研究一个新颖的最大流通量问题,集中考察在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-近似多项式算法.

An Approximation Algorithm for the Risk-Adjusted Two-Stage Stochastic Facility Location Problem with Penalties

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.