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.