User nick russler - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T08:17:35Z http://mathoverflow.net/feeds/user/24150 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/98651/how-to-get-the-largest-subset-of-a-set-of-sets-of-intervals-with-no-overlapping-i/98863#98863 Answer by Nick Russler for How to get the largest subset of a set of sets of intervals with no overlapping intervals Nick Russler 2012-06-05T11:44:38Z 2012-06-05T11:44:38Z <p>Vel Nias gave almost the right answer in:</p> <p><a href="http://mathoverflow.net/questions/98651/how-to-get-the-largest-subset-of-a-set-of-sets-of-intervals-with-no-overlapping-i/98663#98663" rel="nofollow">http://mathoverflow.net/questions/98651/how-to-get-the-largest-subset-of-a-set-of-sets-of-intervals-with-no-overlapping-i/98663#98663</a></p> <p>but instead of the connected components we are looking for the maximum independent set in this graph.</p> http://mathoverflow.net/questions/98651/how-to-get-the-largest-subset-of-a-set-of-sets-of-intervals-with-no-overlapping-i How to get the largest subset of a set of sets of intervals with no overlapping intervals Nick Russler 2012-06-02T12:31:13Z 2012-06-05T11:44:38Z <p>Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}}</p> <p>Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise.</p> <p>Example:</p> <pre> Input {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}} A possible Solution would be: {{(1,2), (3,4)}, {(13,14)}} Another could be {{(1, 3)}, {(13,14)}}, it's not important that the solution above has more 'subelements', its only important that 2 = |{{(1,2), (3,4)}, {(13,14)}}| = |{{(1, 3)}, {(13,14)}}| </pre> <p>Now i am looking for a good/efficient Algorithm to solve that problem.</p> http://mathoverflow.net/questions/98570/maximum-subset-of-set-of-integers-with-minimum-distance Maximum subset of set of Integers with minimum distance Nick Russler 2012-06-01T13:13:47Z 2012-06-01T13:36:56Z <p>Hi, i have a set of integers for example: {0,1,3,100,102} and i am looking for a maximum subset in which all elements have a minimum distance to all elements (or the "next" doesnt matter i guess) for my example ({0,1,3,100,102}) and the distance 3 the result could be: {0,3,100} for distance 2 it could be: {0,3,100,102}</p> <p>Is there an "good" algorithm to do that ?</p> <p>(This is my first post, sry when i chose the wrong tag)</p> http://mathoverflow.net/questions/98651/how-to-get-the-largest-subset-of-a-set-of-sets-of-intervals-with-no-overlapping-i/98686#98686 Comment by Nick Russler Nick Russler 2012-06-05T10:22:58Z 2012-06-05T10:22:58Z Maybe i dont understand the paper right, but as far as i can tell this paper only deals with a Set of Intervall's not a Set of Set's of Intervalls. http://mathoverflow.net/questions/98651/how-to-get-the-largest-subset-of-a-set-of-sets-of-intervals-with-no-overlapping-i/98663#98663 Comment by Nick Russler Nick Russler 2012-06-05T00:32:50Z 2012-06-05T00:32:50Z Yeah, now i think hes right... We are looking for the maximum independent set... and that takes too much time. http://mathoverflow.net/questions/98570/maximum-subset-of-set-of-integers-with-minimum-distance Comment by Nick Russler Nick Russler 2012-06-01T15:28:00Z 2012-06-01T15:28:00Z here i got my answer: <a href="http://stackoverflow.com/questions/10852535/get-largest-subset-of-integers-with-certain-minimum-distance-difference" rel="nofollow" title="get largest subset of integers with certain minimum distance difference">stackoverflow.com/questions/10852535/&hellip;</a> http://mathoverflow.net/questions/98570/maximum-subset-of-set-of-integers-with-minimum-distance Comment by Nick Russler Nick Russler 2012-06-01T13:36:12Z 2012-06-01T13:36:12Z isn't this also a mathematical problem ? Something like the Knapsack problem ?