Solving a linear optimization problem on incentive allocation

Re:Solving a linear optimization problem on incentive alloca... by greedyalgo on Wednesday October 23, 2019 @01:13PM (#21336687)

Since their budget is much larger than each individual incentive, isn't the greedy solution within epsilon of the optimal assignment? I.e. sort by v/c descending and take while sum(c) < B.

[ Parent | on HN ]

Re:Solving a linear optimization problem on incentive alloca... by bo1024 on Wednesday October 23, 2019 @04:55PM (#21338903)

I thought you were right but actually no, you'd need more assumptions. Consider this example:

Type A: coupon a1 has cost 1, value 2. coupon a2 has cost 2, value 3.99.

Type B: coupon b1 has cost 1, value 1.

We have 100 people of Type A and 100 people of Type B. The total budget is 200.

The optimal solution is to pick all Type A people, coupon a2, for a value of 399.

Greedy picks all Type A people, coupon a1, and then all Type B people, coupon b1, for a value of 300.

[ Parent | on HN ]

Re:Solving a linear optimization problem on incentive alloca... by jvanderbot on Wednesday October 23, 2019 @01:35PM (#21336894)

Given there are no overlapping subproblems, I think greedy is optimal[1]. The point was to show primal I(L)P with dual decomposition.

1. You're right, a counter example for greedy (with 2 appox) looks something like: c1=.5+eps, v1=1, c2=.5, v2=.5+eps, B=2.

[ Parent | on HN ]