4 papers
Geometric Bin Packing Beyond Convexity: Approximation Schemes without Augmentation
Lucas de Oliveira Silva, Elisa Dell'Arriva, Flávio Keidi Miyazawa
We study the geometric bin packing problem for simple polygonal regions, i.e., non-degenerate, connected, rational regions, in the minimum number of unit-square bins, allowing only…
Vertex Cover Problem with Advice
Lucas de Oliveira Silva, Lehilton Lelis Chaves Pedrosa
We study the minimum Vertex Cover problem under two non-adaptive offline advice models, where predictions about a fixed optimum solution are provided once as part of the input. The…
Freeze-Tag is Strongly NP-hard in 2D with Distances
Lucas de Oliveira Silva, Lehilton Lelis Chaves Pedrosa
The Freeze-Tag Problem (FTP) asks for the minimum time needed to activate a swarm of robots, starting from a single active robot. When an active robot reaches a frozen robot, the l…
Freeze-Tag is NP-Hard in 3D with distance
Lucas de Oliveira Silva
Arkin et al. in 2002 introduced a scheduling-like problem called Freeze-Tag Problem (FTP) motivated by robot swarm activation. The input consists of the locations of n mobile punct…