Feldman, Moran ;
Izsak, Rani
Constrained Monotone Function Maximization and the Supermodular Degree
Abstract
The problem of maximizing a constrained monotone set function has many practical applications and generalizes many combinatorial problems such as kCoverage, MaxSAT, 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 kextendible system. This class of constraints captures, for example, the intersection of kmatroids (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 kextendible 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.
BibTeX  Entry
@InProceedings{feldman_et_al:LIPIcs:2014:4695,
author = {Moran Feldman and Rani Izsak},
title = {{Constrained Monotone Function Maximization and the Supermodular Degree}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
pages = {160175},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897743},
ISSN = {18688969},
year = {2014},
volume = {28},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4695},
URN = {urn:nbn:de:0030drops46950},
doi = {10.4230/LIPIcs.APPROXRANDOM.2014.160},
annote = {Keywords: supermodular degree, set function, submodular, matroid, extendible system}
}
04.09.2014
Keywords: 

supermodular degree, set function, submodular, matroid, extendible system 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Issue date: 

2014 
Date of publication: 

04.09.2014 