3
$\begingroup$

Given a set of elements $S=\{a_1,a_2,\cdots,a_n\}$, my problem is to find a partition $P$, i.e., partition $S$ into $g$ subsets, the objective is to maximize a utility function $f(P)$, under the constraint that $d(P)\le D$, where $d(P)$ is a given function. Is this problem related to some known combinatorial problem?

A few words regarding $d(P)$: suppose $S$ is partitioned into $g$ subsets $S_1,\cdots,S_g$, $d(P)$ can be expressed as $d(P)=\sum_{i=1}^g z(S_i)$, where $z(S_i)$ is a positive real-valued function that is monotonous in each element in $S_i$. $f(P)$ has similar structure

Improve this question
$\endgroup$
9
  • $\begingroup$ What is $d$ and $f$? Way too vague. $\endgroup$
    – Ethan Splaver
    Commented Apr 1 at 12:46
  • 4
    $\begingroup$ @ichen Still too vague. Also why are you specifying "$d(P)\leq D$" when you haven't defined $d$? Might as well say $d(P)\geq D$ since you could just send $d\to -d$ again meaningless details. You need to be way more specific here. $\endgroup$
    – Ethan Splaver
    Commented Apr 1 at 12:58
  • 1
    $\begingroup$ As you probably know the number of possible partitions of $n$ elements is huge (unless $n$ is tiny). So your options are likely either (1) approximate, e.g. stochastic search, (2) exact algorithms and spending some serious time in computing, or (3) hoping that the $d(P)$ bound restricts the search space quite a lot. Which of these cases is it? Depending on the situation, the additive structure may help a little, or a lot. $\endgroup$
    – Jukka Kohonen
    Commented Apr 4 at 4:18
  • 2
    $\begingroup$ If you are after exact solutions, and want to exploit the additive structure of $f$, there are some algorithms for similar problems based on subset convolution, e.g. Björklund et al 2009: Set partitioning via inclusion-exclusion (§3.4 Finding a heaviest partition). Whether this helps you is difficult to say without further details on your problem size and characteristics. $\endgroup$
    – Jukka Kohonen
    Commented Apr 4 at 4:25
  • 1
    $\begingroup$ It would be useful to hear more about the role of your $d(P)$ bound: how tight is it? Is it so loose that almost all partitions pass it, so you can just search over all partitions and check for the bound afterwards? Or so tight that it is difficult to even find a partition that fits the bound? Or something in between? $\endgroup$
    – Jukka Kohonen
    Commented Apr 4 at 4:33

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .