search

sharmaeklavya2 / packing-game

2D geometric bin-packing game in the browser
https://sharmaeklavya2.github.io/packing-game/
8 stars 4 forks source link

Better lower bounds #18

Open sharmaeklavya2 opened 3 years ago

sharmaeklavya2 commented 3 years ago

Currently, we use ceil(area) as a lower bound on the minimum number of bins. It's easy to come up with inputs where ceil(area) is far from optimal (but I don't know how true this is for 'interesting' inputs). We need something better.

These lower-bounds should either be very efficiently computable, or we should have a mechanism where a user can choose to compute them on-demand-only.

sharmaeklavya2 commented 3 years ago

I have added more lower-bounds. They transform the width and height of items by applying dual-feasible-functions and then ceil(area) of this transformed instance gives us lower-bounds.