c*****t
发帖数: 1879 | 1 【 以下文字转载自 Programming 讨论区 】
【 原文由 coconut 所发表 】
Activity selection problem. For those people who don't remember,
it asks one to pick max # of non-overlapping segments. The optimal
strategy is to sort the segments according to where it ends and
pick accordingly. However, this is not what I am asking.
I am asking for a counter example that that Minimum Overlap greedy
(sort segments according to minimum overlap). I knew that it is
not optimal (I did it before), but apparently I forgot the solut | k**y
发帖数: 320 | 2 not quite sure i understand. maybe the following example helps:
{[0,10], [11,20], [10,11]} greedy picks [10,11] but the opt
solution is [0,11]+[11,20].
it is not hard to prove greedy gives > 0.5 approximation.
【在 c*****t 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 【 原文由 coconut 所发表 】
: Activity selection problem. For those people who don't remember,
: it asks one to pick max # of non-overlapping segments. The optimal
: strategy is to sort the segments according to where it ends and
: pick accordingly. However, this is not what I am asking.
: I am asking for a counter example that that Minimum Overlap greedy
: (sort segments according to minimum overlap). I knew that it is
: not optimal (I did it before), but apparently I forgot the solut
| c*****t
发帖数: 1879 | 3 So, to look for a counter example, one needs to find a case where
a first peak does not pick the end (or resulting a pick that that
is compatible with picking the end). Since the optimal strategy
(btw, is also greedy) is
1. sort the segments ending from left to right.
2. pick the one that end the first w/o conflict w/ existing picks.
3. repeat 2.
Obviously, it is very different from minOverlap, yet in many cases
they produce equivalent results.
Unfortunately, it is hard to find a counter exampl
【在 c*****t 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 【 原文由 coconut 所发表 】
: Activity selection problem. For those people who don't remember,
: it asks one to pick max # of non-overlapping segments. The optimal
: strategy is to sort the segments according to where it ends and
: pick accordingly. However, this is not what I am asking.
: I am asking for a counter example that that Minimum Overlap greedy
: (sort segments according to minimum overlap). I knew that it is
: not optimal (I did it before), but apparently I forgot the solut
| k**y
发帖数: 320 | 4 not considering the tie break cases (in which just random pick
one with min overlapping with others), i think this is the best
i can find: your method always give >.75 approximation.
i changed it a little bit so you cannot remove any element
without stadying the whole set.
【在 k**y 的大作中提到】
: not quite sure i understand. maybe the following example helps:
: {[0,10], [11,20], [10,11]} greedy picks [10,11] but the opt
: solution is [0,11]+[11,20].
: it is not hard to prove greedy gives > 0.5 approximation.
| c*****t
发帖数: 1879 | 5 Yes. This is the idea I was looking for. Thank you so much!
------- ------- ------ --------
----------- ----- ------------
----------- ------------
----------- ------------
Damn. How could I forgot the solution. Now, looking back, I should
have realized that the segment that picked by minOverlap would cause
two segments (not one) needed by the optimal method to be removed.
Thank you.
【在 k**y 的大作中提到】
: not considering the tie break cases (in which just random pick
: one with min overlapping with others), i think this is the best
: i can find: your method always give >.75 approximation.
: i changed it a little bit so you cannot remove any element
: without stadying the whole set.
|
|
