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.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…

cs.DS2025

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…

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

Practical colinear chaining on sequences revisited

Maximum Coverage k-Antichains and Chains: A Greedy Approach

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