Manuel Cáceres

collaborators

3 papers

cs.CG2026

Shifting is Optimal under Gap-ETH: A Lower Bound Framework for Geometric Approximation Schemes

Manuel CÃ¡ceres, SÃ¡ndor Kisfaludi-Bak, Saeed Odak

The shifting technique of Hochbaum and Maass [J.ACM'85] produces PTASes with the fastest known running times $n^{O (1/ ε^{d - 1})}$ for several $d$ -dimensional geometric prob…

cs.DS2026

Maximum Coverage $k$ -Antichains and Chains: A Greedy Approach

Manuel CÃ¡ceres, Andreas Grigorjew, Wanchote Po Jiamjitrak +1

Given an acyclic digraph $G = (V, E)$ and a positive integer $k$ , the problem of Maximum Coverage $k$ -Antichains (resp. Chains) denoted as MA- $k$ (resp. MC- $k$ ) asks to find $k$ set…

cs.DS2025

Practical colinear chaining on sequences revisited

Nicola Rizzo, Manuel CÃ¡ceres, Veli MÃ¤kinen

Colinear chaining is a classical heuristic for sequence alignment and is widely used in modern practical aligners. Jain et al. (J. Comput. Biol. 2022) proposed an $O (n lo g^{3} n)$ t…

Shifting is Optimal under Gap-ETH: A Lower Bound Framework for Geometric Approximation Schemes

Maximum Coverage k-Antichains and Chains: A Greedy Approach

Practical colinear chaining on sequences revisited

Maximum Coverage $k$ -Antichains and Chains: A Greedy Approach