0
$\begingroup$

I am considering the following problem: there is a set of elements $S$ where each element is assigned to a bin $B$. The bins are disjoint and their union is $S$. There is also a cost function assigning each element $e \in S$ a cost $c$. The problem is to maximize the number of different bins and minimize the total cost of the elements, subject to a cardinality constraint $K$. (I'm interested in both cases: either at most or exactly $K$ elements).

So the objective function would be: $f(S) = \lambda\sum_{i=1}^N \mathbb{1}_{|B_{i} \cap S| > 0} - \sum_{e \in S} c(e)$, where $N$ is the number of bins and $\lambda$ is a tradeoff parameter.

Maximizing the number of different bins is equivalent to maximizing the rank of a partition matroid.

In addition to partition matroid rank, I'm also interested in other types of coverage-like submodular functions.

This can also be seen as maximizing the difference between a sub modular function and a modular cost function; it is non monotone sub modular.

Is this - or a similar formulation - equivalent to any other known problem?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ The question is not completely defined. In general you can't both maximize the number of bins and minimize the cost at the same time. You could either combine the objectives somehow or turn one into a constraint. Also, do you need exactly or at most K elements? Finally: a linear combination of a submodular and a modular function is a submodular function. $\endgroup$
    – Sasho Nikolov
    Commented Oct 4, 2015 at 1:06
  • $\begingroup$ Ok, combined the objectives. And I'm interested in both cases - exactly K elements, or at most K. Yes, it is sub modular, but not monotone, so I'm not sure that the greedy algorithm is optimal. $\endgroup$
    – eagle34
    Commented Oct 4, 2015 at 3:30
  • $\begingroup$ There is a long line of work on maximizing submodular functions subject to cardinality constraints, including non-monotone submodular functions, e.g. theory.epfl.ch/moranfe/Publications/SODA2014.pdf. But I am not sure your function is non-negative, and if it's not, this may be a problem for approximation. $\endgroup$
    – Sasho Nikolov
    Commented Oct 4, 2015 at 3:43
  • $\begingroup$ Thanks! Yes, but if there is a known minimum value of the function (this is the case for my problem), can't it be shifted to a nonnegative function? $\endgroup$
    – eagle34
    Commented Oct 4, 2015 at 3:45
  • $\begingroup$ It can, but I will let you figure out yourself what this does to the approximation guarantees. $\endgroup$
    – Sasho Nikolov
    Commented Oct 4, 2015 at 3:48

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.