Negative prizes

[alexlenail]

Hi @ludwigschmidt,

As we've previously discussed, for many of our applications, we can get better results if we allow negative node prizes. Would you take a look at how difficult it would be to add this functionality?

[ludwigschmidt]

As I mentioned, there are two aspects to this:

• Implement something principled with provable guarantees.
• Implement something that works well for our applications.

Ideally we can get both, but the latter is more important for now.

Can you tell me how your algorithm handles negative-prize nodes? If I remember correctly, you mentioned that the manuscript you wrote with Murodzhon might not be clear about this. Thanks!

[alexlenail]

Hey @ludwigschmidt,

I agree we should aim to do both but focus on the latter.

• I'm not sure what the old lab algorithm does. That's the one we've used the most in the lab. (I think this is the cite)
• Murodzhon's algorithm propagates negative prize information onto the edges somehow, then we solve MST. That algorithm solves MST instead of PCSF, essentially, which is "good enough" most of the time with our graphs, prizes, and costs.
• I think the objective function is the same with negative prizes as without. Let me know how you're thinking about this and what help I can provide.

[alexlenail]

@ludwigschmidt let us know!