Barna Saha

Available identifiers

List of research outcomes

Publication	Date of Publication	Type
Faster approximate all pairs shortest paths	2024-11-28	Paper
An algorithmic bridge between Hamming and Levenshtein distances	2024-09-25	Paper
Approximating LCS and alignment distance over multiple sequences	2024-08-22	Paper
An upper bound and linear-space queries on the LZ-End parsing	2024-07-19	Paper
The complexity of average-case dynamic subgraph counting	2024-07-19	Paper
How compression and approximation affect efficiency in string distance measures	2024-07-19	Paper
Improved approximation algorithms for Dyck edit distance and RNA folding	2024-06-24	Paper
Weighted edit distance computation: strings, trees, and Dyck	2024-05-08	Paper
https://portal.mardi4nfdi.de/entity/Q6168412	2023-08-08	Paper
https://portal.mardi4nfdi.de/entity/Q5875512	2023-02-03	Paper
https://portal.mardi4nfdi.de/entity/Q5075830	2022-05-11	Paper
Does preprocessing help in fast sequence comparisons?	2021-01-19	Paper
Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!	2020-05-27	Paper
Min-max correlation clustering via multicut	2020-02-06	Paper
Dynamic set cover: improved algorithms and lower bounds	2020-01-30	Paper
A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median	2019-06-20	Paper
Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product	2019-05-07	Paper
A Constant Factor Approximation Algorithm for Fault-Tolerant k -Median	2018-11-05	Paper
A new approximation technique for resource‐allocation problems	2018-09-05	Paper
https://portal.mardi4nfdi.de/entity/Q5365103	2017-09-29	Paper
https://portal.mardi4nfdi.de/entity/Q2963933	2017-02-21	Paper
New approximation results for resource replication problems	2016-04-06	Paper
Facility Location with Matroid or Knapsack Constraints	2015-05-29	Paper
https://portal.mardi4nfdi.de/entity/Q5417714	2014-05-22	Paper
New Constructive Aspects of the Lovász Local Lemma	2014-02-17	Paper
Set Cover Revisited: Hypergraph Cover with Hard Capacities	2013-08-12	Paper
New Approximation Results for Resource Replication Problems	2012-11-02	Paper
AdCell: ad allocation in cellular networks	2011-09-16	Paper
On capacitated set cover problems	2011-08-17	Paper
On Finding Dense Subgraphs	2009-07-14	Paper
On Estimating Path Aggregates over Streaming Graphs	2008-04-24	Paper

Research outcomes over time

This page was built for person: Barna Saha