12 papers
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…
Algorithms for the Bin Packing Problem with Scenarios
Yulle G. F. Borges, Vinícius L. de Lima, Flávio K. Miyazawa +3
This paper presents theoretical and practical results for the bin packing problem with scenarios, a generalization of the classical bin packing problem which considers the presence…
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…
A parameterized approximation algorithm for the Multiple Allocation -Hub Center
Marcelo P. L. Benedito, Lucas P. Melo, Lehilton L. C. Pedrosa
In the Multiple Allocation -Hub Center (MAHC), we are given a connected edge-weighted graph , sets of clients and hub locations , where ${V(G) =…
Computing the Largest Bond and the Maximum Connected Cut of a Graph
Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka +6
The cut-set of a graph is the set of edges that have one endpoint in and the other endpoint in , and whenever is connected…
Approximation algorithms for the MAXSPACE advertisement problem
Mauro R. C. da Silva, Lehilton L. C. Pedrosa, Rafael C. S. Schouery
In MAXSPACE, given a set of ads $\cala$, one wants to schedule a subset ${\cala'\subseteq\cala}$ into slots of size . E…
A 2-approximation for the -prize-collecting Steiner tree problem
Lehilton Lelis Chaves Pedrosa, Hugo Kooki Kasuya Rosado
We consider the -prize-collecting Steiner tree problem. An instance is composed of an integer and a graph with costs on edges and penalties on vertices. The objective is…
Computing the largest bond of a graph
Gabriel L. Duarte, Daniel Lokshtanov, Lehilton L. C. Pedrosa +2
A bond of a graph is an inclusion-wise minimal disconnecting set of , i.e., bonds are cut-sets that determine cuts of such that and $G[V\setmin…
Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center
Cristina G. Fernandes, Samuel P. de Paula, Lehilton L. C. Pedrosa
In the k-center problem, given a metric space V and a positive integer k, one wants to select k elements (centers) of V and an assignment from V to centers, minimizing the maximum…
Polynomial-Time Approximation Schemes for Circle and Other Packing Problems
Flávio K. Miyazawa, Lehilton L. C. Pedrosa, Rafael C. S. Schouery +2
We give an asymptotic approximation scheme (APTAS) for the problem of packing a set of circles into a minimum number of unit square bins. To obtain rational solutions, we use augme…
A Systematic Approach to Bound Factor-Revealing LPs and its Application to the Metric and Squared Metric Facility Location Problems
Cristina G. Fernandes, Luís A. A. Meira, Flávio K. Miyazawa +1
A systematic technique to bound factor-revealing linear programs is presented. We show how to derive a family of upper bound factor-revealing programs (UPFRP), and show that each s…