8
$\begingroup$

How does in the (famous Zilberstein) PR(uning) algorithm below the LP-dominate function get started: the first time it's called, D=∅ and the linear program deteriorates (i.e. no constraint equations)?

procedure POINTWISE-DOMINATE(w, U)
...
3. return false
procedure LP-DOMINATE(w, U)
4. solve the following linear program variables: d, b(s) ∀s ∈ S
      maximize d
      subject to the constraints
        b · (w − u) ≥ d, ∀u ∈ U
        sum(b) = 1
5. if d ≥ 0 then return b
6. else return nil
procedure BEST(b, U )
...
12. return w
procedure PR(W)
13. D ← ∅
14. while W = ∅
15.   w ← any element in W
16.   if POINTWISE-DOMINATE(w, D) = true
17.      W ← W − {w}
18.   else
19.      b ← LP-DOMINATE(w, D)
20.      if b = nil then
21.         W ← W − {w}
22.      else
23.         w ← BEST(b, W)
24.         D ← D ∪ {w}
25.         W ← W − {w}
26. return D
$\endgroup$
1
  • $\begingroup$ check a book about algorithms heuristics using python. good luck! $\endgroup$ – Youness Abdus Salam Apr 13 '18 at 23:56
1
$\begingroup$

I think I found the solution. When in PR(W), D=∅, the weight is:

b[i] = 0 for { i | w[i]<max(w) },

and

b[i] = 1.0/max(w) for { i | w[i]==max(w) }.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.