Constrained monotone function maximization and the supermodular degree
From MaRDI portal
Abstract: The problem of maximizing a constrained monotone set function has many practical applications and generalizes many combinatorial problems. 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. 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, 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, 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.
Recommendations
- Maximizing nonmonotone submodular functions under matroid or knapsack constraints
- Maximizing a monotone submodular function subject to a matroid constraint
- Welfare maximization and the supermodular degree
- Non-monotone submodular maximization under matroid and knapsack constraints
- Approximation for maximizing monotone non-decreasing set functions with a greedy method
Cited in
(14)- Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
- Parametric monotone function maximization with matroid constraints
- Multi-attribute based influence maximization in social networks: algorithms and analysis
- Generalized self-profit maximization in attribute networks
- Set function optimization
- Welfare maximization and the supermodular degree
- A simple and approximately optimal mechanism for a buyer with complements
- Capturing complementarity in set functions by going beyond submodularity/subadditivity
- Fast algorithms for maximizing monotone nonsubmodular functions
- Fast algorithms for maximizing monotone nonsubmodular functions
- Competition-based generalized self-profit maximization in dual-attribute network
- Competition-based generalized self-profit maximization in dual-attribute networks
- q-partitioning valuations: exploring the space between subadditive and fractionally subadditive valuations
- Influence maximization problem: properties and algorithms
This page was built for publication: Constrained monotone function maximization and the supermodular degree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2969616)
