I'm trying to solve a set cover problem.

To put it shortly, my problem is about covering a $N \times M$ grid, by using various rectangles which have associated cost depending on their shape and position. A bit like Tetris, but not quite the same (since I have different costs depending on shape and position).

A common approach seems to be using lagrangian relaxation and subgradients to get lower/upper bounds, then do branch and bound. Though I am not sure if it is the most modern approach, I would like to learn about classical results on those subjects from a theoretical standpoint. If you know more efficient techniques, I'll also be interested.

What books or resources would you recommend ? So far I found Korte's Combinatorial Optimization, but I don't know if it is the most indicated book for those subjects. Thanks,


Your Answer

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

Browse other questions tagged or ask your own question.