4 papers
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 for several -dimensional geometric prob…
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 t…
Maximum Coverage -Antichains and Chains: A Greedy Approach
Manuel Cáceres, Andreas Grigorjew, Wanchote Po Jiamjitrak +1
Given an acyclic digraph and a positive integer , the problem of Maximum Coverage -Antichains (resp. Chains) denoted as MA- (resp. MC-) asks to find set…
Minimum Path Cover: The Power of Parameterization
Manuel Cáceres, Brendan Mumey, Santeri Toivonen +1
Computing a minimum path cover (MPC) of a directed acyclic graph (DAG) is a fundamental problem with a myriad of applications, including reachability. Although it is known how to s…