Certified Algorithms: Worst-Case Analysis and Beyond
In this paper, we introduce the notion of a certified algorithm. Certified algorithms provide worst-case and beyond-worst-case performance guarantees. First, a γ-certified algorithm is also a γ-approximation algorithm - it finds a γ-approximation no matter what the input is. Second, it exactly solves γ-perturbation-resilient instances (γ-perturbation-resilient instances model real-life instances). Additionally, certified algorithms have a number of other desirable properties: they solve both maximization and minimization versions of a problem (e.g. Max Cut and Min Uncut), solve weakly perturbation-resilient instances, and solve optimization problems with hard constraints. In the paper, we define certified algorithms, describe their properties, present a framework for designing certified algorithms, provide examples of certified algorithms for Max Cut/Min Uncut, Minimum Multiway Cut, k-medians and k-means. We also present some negative results.
Authors:
;
Award ID(s):
Publication Date:
NSF-PAR ID:
10185956
Journal Name:
Innovations in Theoretical Computer Science Conference
Sequence mappability is an important task in genome resequencing. In the (km)-mappability problem, for a given sequenceTof lengthn, the goal is to compute a table whoseith entry is the number of indices$$j \ne i$$$j\ne i$such that the length-msubstrings ofTstarting at positionsiandjhave at mostkmismatches. Previous works on this problem focused on heuristics computing a rough approximation of the result or on the case of$$k=1$$$k=1$. We present several efficient algorithms for the general case of the problem. Our main result is an algorithm that, for$$k=O(1)$$$k=O\left(1\right)$, works in$$O(n)$$$O\left(n\right)$space and, with high probability, in$$O(n \cdot \min \{m^k,\log ^k n\})$$$O\left(n·min\left\{{m}^{k},{log}^{k}n\right\}\right)$time. Our algorithm requires a careful adaptation of thek-errata trees of Cole et al. [STOC 2004] to avoid multiple counting of pairs of substrings. Our technique can also be applied to solve the all-pairs Hamming distance problem introduced by Crochemore et al. [WABI 2017]. We further develop$$O(n^2)$$$O\left({n}^{2}\right)$-time algorithms to computeall(km)-mappability tables for a fixedmand all$$k\in \{0,\ldots ,m\}$$$k\in \left\{0,\dots ,m\right\}$or a fixedkand all$$m\in \{k,\ldots ,n\}$$$m\in \left\{k,\dots ,n\right\}$. Finally, we show that, for$$k,m = \Theta (\log n)$$$k,m=\Theta \left(logn\right)$, the (km)-mappability problem cannot be solved in strongly subquadratic time unless the Strong Exponential Time Hypothesis fails. This is an improved and extended version of a paper presented at SPIRE 2018.