1 Search Results for "Izsak, Rani"

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.160

Constrained Monotone Function Maximization and the Supermodular Degree

Authors: Moran Feldman and Rani Izsak

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract

The problem of maximizing a constrained monotone set function has many practical applications and generalizes many combinatorial problems such as k-Coverage, Max-SAT, Set Packing, Maximum Independent Set and Welfare Maximization. Unfortunately, it is generally not possible to maximize a monotone set function up to an acceptable approximation ratio, even subject to simple constraints. One highly studied approach to cope with this hardness is to restrict the set function, for example, by requiring it to be submodular. An outstanding disadvantage of imposing such a restriction on the set function is that no result is implied for set functions deviating from the restriction, even slightly. A more flexible approach, studied by Feige and Izsak [ITCS 2013], is to design an approximation algorithm whose approximation ratio depends on the complexity of the instance, as measured by some complexity measure. Specifically, they introduced a complexity measure called supermodular degree, measuring deviation from submodularity, and designed an algorithm for the welfare maximization problem with an approximation ratio that depends on this measure. In this work, we give the first (to the best of our knowledge) algorithm for maximizing an arbitrary monotone set function, subject to a k-extendible system. This class of constraints captures, for example, the intersection of k-matroids (note that a single matroid constraint is sufficient to capture the welfare maximization problem). Our approximation ratio deteriorates gracefully with the complexity of the set function and k. Our work can be seen as generalizing both the classic result of Fisher, Nemhauser and Wolsey [Mathematical Programming Study 1978], for maximizing a submodular set function subject to a k-extendible system, and the result of Feige and Izsak for the welfare maximization problem. Moreover, when our algorithm is applied to each one of these simpler cases, it obtains the same approximation ratio as of the respective original work. That is, the generalization does not incur any penalty. Finally, we also consider the less general problem of maximizing a monotone set function subject to a uniform matroid constraint, and give a somewhat better approximation ratio for it.

Cite as

Moran Feldman and Rani Izsak. Constrained Monotone Function Maximization and the Supermodular Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 160-175, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{feldman_et_al:LIPIcs.APPROX-RANDOM.2014.160,
  author =	{Feldman, Moran and Izsak, Rani},
  title =	{{Constrained Monotone Function Maximization and the Supermodular Degree}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{160--175},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.160},
  URN =		{urn:nbn:de:0030-drops-46950},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.160},
  annote =	{Keywords: supermodular degree, set function, submodular, matroid, extendible system}
}

Refine by Author
1 Feldman, Moran
1 Izsak, Rani

Refine by Classification

Refine by Keyword
1 extendible system
1 matroid
1 set function
1 submodular
1 supermodular degree

Refine by Type
1 document

Refine by Publication Year
1 2014

1 Search Results for "Izsak, Rani"

Constrained Monotone Function Maximization and the Supermodular Degree

Abstract

Cite as

Thanks for your feedback!

Could not send message