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.展开更多
In the k-product uncapacitated facility location problem with penalties,we are given a set of demand points where clients are located and a set of potential sites where facilities with unlimited capacities can be open...In the k-product uncapacitated facility location problem with penalties,we are given a set of demand points where clients are located and a set of potential sites where facilities with unlimited capacities can be opened.There are k different kinds of products to be supplied by a set of open facilities.Each open facility can supply only a distinct product with a non-negative fixed cost determined by the product it wants to supply.Each client is either supplied with k kinds of products by a set of k different open facilities or completely rejected.There is a non-negative service cost between each pair of locations and also a penalty cost for each client if its service is rejected.These service costs are assumed to be symmetric and satisfy the triangle inequality.The goal is to select a set of clients to reject their service and then choose a set of facilities to be opened to service the remaining clients so that the total cost of opening facilities,servicing the clients,and the penalty is minimized.We address two different integer programs to describe the problem.Based on the linear programming rounding technique,we propose a(2k+1)-approximation algorithm for this problem.展开更多
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.展开更多
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.展开更多
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.展开更多
基金The work was supported by the National Natural Science Foundation of China(Grant Nos.61972228,61672323,61672328)the Natural Science Foundation of Shandong Province(ZR2016AM28,ZR2019MF072).
文摘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.
基金supported by the National Natural Science Foundation of China(No.11971252)。
文摘In the k-product uncapacitated facility location problem with penalties,we are given a set of demand points where clients are located and a set of potential sites where facilities with unlimited capacities can be opened.There are k different kinds of products to be supplied by a set of open facilities.Each open facility can supply only a distinct product with a non-negative fixed cost determined by the product it wants to supply.Each client is either supplied with k kinds of products by a set of k different open facilities or completely rejected.There is a non-negative service cost between each pair of locations and also a penalty cost for each client if its service is rejected.These service costs are assumed to be symmetric and satisfy the triangle inequality.The goal is to select a set of clients to reject their service and then choose a set of facilities to be opened to service the remaining clients so that the total cost of opening facilities,servicing the clients,and the penalty is minimized.We address two different integer programs to describe the problem.Based on the linear programming rounding technique,we propose a(2k+1)-approximation algorithm for this problem.
基金This work was supported by the Science and Technology Project of Hebei Education Department(No.BJK2023076)the National Natural Science Foundation of China(Nos.12101594,12001025,and 12131003)the Natural Science Foundation of Shandong Province of China(No.ZR2020MA029).
文摘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.
基金supported by National Natural Science Foundation of China (Grant No. 11371001)the Natural Sciences and Engineering Research Council of Canada (Grant No. 283106)China Scholarship Council
文摘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.
基金This work was supported by Scientific Research Common Program of Beijing Municipal Commission of Education(No.KM201210005033)and China Scholarship CouncilThe authors would like to thank the two anonymous referees for many helpful suggestions.
文摘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.
