The dynamic program can be implemented on top of an unbreakable decomposition using algebraic techniques and compute in time a tree decomposition with adhesions of size at most $2k$ whose bags are $(3k,k)$-edge-unbreakable inside their own subtrees.
Aditya Anand, Evangelos Kipouridis, Karol Węgrzycki· 0 citations
For every $0<\varepsilon \le 1$, we give a randomized $(3+\varepsilon)$-approximation to weighted edit distance when the costs form a metric on the alphabet augmented with a gap symbol. For strings of total length $N$, the running time is $\widetilde{O}(N^{8/5}/\varepsilon^{16/5})$, where $\widetilde{O}$ suppresses fac...
D. Das, Evangelos Kipouridis, Tomasz Kociumaka· 0 citations
This work identifies Constrained Correlation Clustering as a variant of Correlation Clustering for which optimal approximations might be within reach, and significantly tighten the gap, by showing that the optimal approximation factor lies in $[2,\frac{16}{7}-\gamma)$ for a small constant $0$.
Sina Azizeddin, Evangelos Kipouridis, Nithin M. Varma· 2 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.