In this work we are interested in study packing problems, especially those considered NP-hard. If we consider that P != NP, we know that there are no efficient algorithms to solve such problems. Several techniques have been developed to deal with NP-Hard problems e.g., integer programming, constraint programming, approximation algorithms, probabilistic algorithms and heuristics. In this project we are interested in studying and developing algorithms for packing problems with unloading constraints. We are particularly interested in formal techniques and approximation algorithms. Our goal is to study the main techniques used in the literature and assess the practical feasibility of the studied algorithms. It is also our goal to develop new approximation algorithms lower bounds for the studied problem using conventional techniques or new techniques such as Algorithmic Game Theory.
News published in Agência FAPESP Newsletter about the scholarship: