In submodular multiway partition (Sub-MP), the input is a non-negative submodular function \(f:2^V\rightarrow \mathbb {R}_{\ge 0}\) given by an evaluation oracle along with k terminals \(t_1, t_2, \ldots , t_k\in V\) . The goal is to find a partition \(V_1, V_2, \ldots , V_k\) of V with \(t_i\in V_i\) for every \(i\in [k]\) in order to minimize \(\sum _{i=1}^k f(V_i)\) . In this work, we focus on Sub-MP when the input function is monotone (termed Mono-Sub-MP). Mono-Sub-MP formulates partitioning problems over several interesting structures—e.g., matrices, matroids, graphs, and hypergraphs. Mono-Sub-MP is NP-hard since the graph multiway cut problem can be cast as a special case. We investigate the approximability of Mono-Sub-MP: we show that it admits a 4/3-approximation and does not admit a \((10/9-\epsilon )\) -approximation for every constant \(\epsilon >0\) . Next, we study a special case of Mono-Sub-MP where the monotone submodular function of interest is the coverage function of an input graph, termed Graph-Cov-MP. Graph-Cov-MP is equivalent to the classic multiway cut problem for the purposes of exact optimization. We show that Graph-Cov-MP admits a 1.125-approximation and does not admit a \((1.00074-\epsilon )\) -approximation for every constant \(\epsilon >0\) assuming the Unique Games Conjecture. These results separate Graph-Cov-MP from graph multiway cut in terms of approximability.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Monotone Submodular Multiway Partition

  • Richard Bi,
  • Karthekeyan Chandrasekaran,
  • Soham Joshi

摘要

In submodular multiway partition (Sub-MP), the input is a non-negative submodular function \(f:2^V\rightarrow \mathbb {R}_{\ge 0}\) given by an evaluation oracle along with k terminals \(t_1, t_2, \ldots , t_k\in V\) . The goal is to find a partition \(V_1, V_2, \ldots , V_k\) of V with \(t_i\in V_i\) for every \(i\in [k]\) in order to minimize \(\sum _{i=1}^k f(V_i)\) . In this work, we focus on Sub-MP when the input function is monotone (termed Mono-Sub-MP). Mono-Sub-MP formulates partitioning problems over several interesting structures—e.g., matrices, matroids, graphs, and hypergraphs. Mono-Sub-MP is NP-hard since the graph multiway cut problem can be cast as a special case. We investigate the approximability of Mono-Sub-MP: we show that it admits a 4/3-approximation and does not admit a \((10/9-\epsilon )\) -approximation for every constant \(\epsilon >0\) . Next, we study a special case of Mono-Sub-MP where the monotone submodular function of interest is the coverage function of an input graph, termed Graph-Cov-MP. Graph-Cov-MP is equivalent to the classic multiway cut problem for the purposes of exact optimization. We show that Graph-Cov-MP admits a 1.125-approximation and does not admit a \((1.00074-\epsilon )\) -approximation for every constant \(\epsilon >0\) assuming the Unique Games Conjecture. These results separate Graph-Cov-MP from graph multiway cut in terms of approximability.