The LP-rounding plus greed approach for partial optimization revisited  

作　　者：Peng ZHANG 

机构地区：[1]School of Software,Shandong University,Jinan,250101,China

出　　处：《Frontiers of Computer Science》2022年第1期67-75,共9页中国计算机科学前沿（英文版）

基　　金：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.

关 键 词：k-Forest k-Multicut partial optimization LP-rounding Greedy algorithm Approximation algorithm 

分 类 号：O17[理学—数学]