Given a partition $[0,1]$，there are 5000 partition subsets $P_i=[a_{i1},a_{i2}]\in[0,1], 0≤a_{i1}\leq a_{i2} \leq 1, i \in \{1,2,...,5000\}$. I want to analyze these subsets and find 10 subsets to contain sixty or seventy percent of the subsets. These 10 subsets could be disjoint, or even overlapping.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ I'm confused by the question. What do you mean by "a partition [0,1]"? What do you mean by a "partition subset"? $\endgroup$– D.W. ♦Commented May 11, 2020 at 6:31
-
$\begingroup$ "a partition [0,1]" means vector that starts at 0 and whose length is 1. a "partition subset" means vector that starts at "ai1" and whose length is "∣ai2-ai1∣". $\endgroup$– landscapeCommented May 11, 2020 at 11:09
-
$\begingroup$ Now I'm even more confused: you are defining the word "subset" to mean "a kind of vector"? Redefining standard mathematical terms is confusing. And what does it mean for 10 vectors to contain some other vectors? $\endgroup$– D.W. ♦Commented May 11, 2020 at 20:27
-
$\begingroup$ I think the author may mean "interval"="partition" and "subinterval"="partition subset". @landscape, if you don't know exactly what a math term means, please just use some english words. Mathematics terms have precise definitions. $\endgroup$– Zachary VanceCommented Oct 9, 2020 at 11:50
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
First, let me be sure u r aware of SET PACKING & SET PARTITIONING Problems
https://slideplayer.com/slide/4514539/
Then, I think ur problem is much easier avoiding the overlapping & the complete coverage constraints.
Going simple, here r some heuristics (think as u solving for max/optimal accepting 30%-40%"deviation from optimality)
1-Pick the max. length partition, then in the next 9th steps choose bet the global max of remaining partitions & the max of those starting after what u have reached so far.... I think that's O(10*5000) let's call it $ O(k n) $
2-Do something similar to $Bucket$ $Sorting$
Divide the partition to 10 smaller partitions(put an overlapping sub partition in its starting point bucket) , then select the max length one in each bucket. Still the same order complexity $ O(k*n) $
Finally, maybe a little bit complicated, but if u want a Theoretical abstraction of ur problem I've just watched this about the $maximum$ $K$ $coverage$ problem and the $Influence$ $maximization$ problem.
If u looked to the interval [0,1] as say M smaller/unit sub intervals being ur target population, and viewed each sub partition as connected to/infleuncing the sub intervals(units) it covers. Then u want to select $K$ (10 in ur case) subpartitions that gives u maximum coverage/influence
-
$\begingroup$ Thanks a lot for ur answer. My problem has been abstracted as the question, and you get my idea. But I think my problem is complicated as ur finally step "maximum K coverage problem and the Influence maximization problem" $\endgroup$ Commented May 12, 2020 at 1:50
-
$\begingroup$ The given video link explains a greedy heuristic to solve them $\endgroup$– ShArCommented May 12, 2020 at 2:38
$\begingroup$
$\endgroup$
I would recommend you formulate this as an instance of integer linear programming (straightforward) and then let an off-the-shelf ILP solver solve it, and see if that is able to come up with an efficient solution in a reasonable amount of time.
