License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.144
URN: urn:nbn:de:0030-drops-46943
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4694/
Go to the corresponding LIPIcs Volume Portal

Ene, Alina ; Vondrák, Jan

Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture

pdf-format:
11.pdf (0.5 MB)

Abstract

We consider the Minimum Submodular Cost Allocation (MSCA) problem.
In this problem, we are given k submodular cost functions f_1, ... ,
f_k: 2^V -> R_+ and the goal is to partition V into k sets A_1, ...,
A_k so as to minimize the total cost sum_{i = 1}^k f_i(A_i). We show
that MSCA is inapproximable within any multiplicative factor even in
very restricted settings; prior to our work, only Set Cover hardness
was known. In light of this negative result, we turn our attention
to special cases of the problem. We consider the setting in which
each function f_i satisfies f_i = g_i + h, where each g_i is monotone
submodular and h is (possibly non-monotone) submodular. We give an
O(k log |V|) approximation for this problem. We provide some evidence
that a factor of k may be necessary, even in the special case of
HyperLabel. In particular, we formulate a simplex-coloring
conjecture that implies a Unique-Games-hardness of (k - 1 - epsilon)
for k-uniform HyperLabel and label set [k]. We provide a proof of the
simplex-coloring conjecture for k=3.

BibTeX - Entry

@InProceedings{ene_et_al:LIPIcs:2014:4694,
  author =	{Alina Ene and Jan Vondr{\'a}k},
  title =	{{Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{144--159},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4694},
  URN =		{urn:nbn:de:0030-drops-46943},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.144},
  annote =	{Keywords: Minimum Cost Submodular Allocation, Submodular Optimization, Hypergraph Labeling}
}

Keywords: Minimum Cost Submodular Allocation, Submodular Optimization, Hypergraph Labeling
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI