Reconfiguration Problems on Submodular Functions
share
Reconfiguration problems require finding a step-by-step transformation between a pair of feasible solutions for a particular problem. The primary concern in Theoretical Computer Science has been revealing their computational complexity for classical problems. This paper presents an initial study on reconfiguration problems derived from a submodular function, which has more of a flavor of Data Mining. Our submodular reconfiguration problems request to find a solution sequence connecting two input solutions such that each solution has an objective value above a threshold in a submodular function f: 2^[n]→ℝ_+ and is obtained from the previous one by applying a simple transformation rule. We formulate three reconfiguration problems: Monotone Submodular Reconfiguration (MSReco), which applies to influence maximization, and two versions of Unconstrained Submodular Reconfiguration (USReco), which apply to determinantal point processes. Our contributions are summarized as follows: 1. We prove that MSReco and USReco are both 𝖯𝖲𝖯𝖠𝖢𝖤-complete. 2. We design a 1/2-approximation algorithm for MSReco and a 1/n-approximation algorithm for (one version of) USReco. 3. We devise inapproximability results that approximating the optimum value of MSReco within a (1-1+ϵ/n^2)-factor is 𝖯𝖲𝖯𝖠𝖢𝖤-hard, and we cannot find a (5/6+ϵ)-approximation for USReco. 4. We conduct numerical study on the reconfiguration version of influence maximization and determinantal point processes using real-world social network and movie rating data.
READ FULL TEXT