8 papers · 1 filter
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…
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…
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…