<p>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). </p>

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

<p>Maximizing the number of different bins is equivalent to maximizing the rank of a partition matroid. </p>

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

<p>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. </p>

<p>Is this - or a similar formulation - equivalent to any other known problem? </p>

CC BY-SA 3.0
2015-10-04T01:06:54.077Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-10-04T03:30:16.203Z
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.
eagle34
CC BY-SA 3.0
2015-10-04T03:43:16.603Z
There is a long line of work on maximizing submodular functions subject to cardinality constraints, including non-monotone submodular functions, e.g. http://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.
Sasho Nikolov
CC BY-SA 3.0
2015-10-04T03:45:13.073Z
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?
eagle34
CC BY-SA 3.0
2015-10-04T03:48:33.670Z
It can, but I will let you figure out yourself what this does to the approximation guarantees.
Sasho Nikolov
<ds.algorithms><co.combinatorics><approximation-algorithms><packing><submodularity>
Maximize number of bins and minimize cost of elements chosen from a set
eagle34
# Maximize number of bins and minimize cost of elements chosen from a set

(Asked by: username_0 on 2015-10-03)

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?

**Tags:** ds.algorithms, co.combinatorics, approximation-algorithms, packing, submodularity
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: There is a long line of work on maximizing submodular functions subject to cardinality constraints, including non-monotone submodular functions, e.g. http://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.  
> **username_0**: 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?  
> **username_1**: It can, but I will let you figure out yourself what this does to the approximation guarantees.  

---

## 0 answers

