Copertina

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Mao, Xiao, Rubinstein, Aviad
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
di: Cheng, Siu-Wing, et al.
Pubblicazione: (2025)

Approximating Maximum Matching Requires Almost Quadratic Time
di: Behnezhad, Soheil, et al.
Pubblicazione: (2024)

Weakly Approximating Knapsack in Subquadratic Time
di: Chen, Lin, et al.
Pubblicazione: (2025)

Approximate Distance Sensitivity Oracles in Subquadratic Space
di: Bilò, Davide, et al.
Pubblicazione: (2023)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
di: Azarmehr, Amir, et al.
Pubblicazione: (2025)

Approximately Counting Knapsack Solutions in Subquadratic Time
di: Feng, Weiming, et al.
Pubblicazione: (2024)

Fréchet Distance in Subquadratic Time
di: Cheng, Siu-Wing, et al.
Pubblicazione: (2024)

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
di: Bathie, Gabriel, et al.
Pubblicazione: (2025)

On the Complexity of Finding Approximate LCS of Multiple Strings
di: Hasibi, Hamed, et al.
Pubblicazione: (2025)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
di: Bilò, Davide, et al.
Pubblicazione: (2024)

Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
di: Rubinstein, Aviad
Pubblicazione: (2016)

Approximate Circular Pattern Matching under Edit Distance
di: Charalampopoulos, Panagiotis, et al.
Pubblicazione: (2024)

Sublinear Algorithms for TSP via Path Covers
di: Behnezhad, Soheil, et al.
Pubblicazione: (2023)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
di: Ebbens, Matthijs, et al.
Pubblicazione: (2024)

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
di: Mao, Xiao
Pubblicazione: (2023)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
di: Das, Debarati, et al.
Pubblicazione: (2025)

Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
di: Rubinstein, Aviad, et al.
Pubblicazione: (2026)

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
di: Bille, Philip, et al.
Pubblicazione: (2022)

Computing Flows in Subquadratic Space
di: Brand, Jan van den, et al.
Pubblicazione: (2026)

Many Flavors of Edit Distance
di: Bhattacharya, Sudatta, et al.
Pubblicazione: (2024)

Subsequence Matching and LCS with Segment Number Constraints
di: Yonemoto, Yuki, et al.
Pubblicazione: (2024)

A Subquadratic Bound for Online Bisection
di: Bienkowski, Marcin, et al.
Pubblicazione: (2023)

Subsequence Matching and LCS under Cartesian-Tree Equivalence
di: Tsujimoto, Taketo, et al.
Pubblicazione: (2024)

Faster Space-Efficient STR-IC-LCS Computation
di: Yonemoto, Yuki, et al.
Pubblicazione: (2022)

Streaming Edge Coloring with Subquadratic Palette Size
di: Chechik, Shiri, et al.
Pubblicazione: (2023)

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
di: Kociumaka, Tomasz, et al.
Pubblicazione: (2025)

Pattern Matching under Weighted Edit Distance
di: Charalampopoulos, Panagiotis, et al.
Pubblicazione: (2025)

Hardness of Dynamic Tree Edit Distance and Friends
di: Hu, Bingbing, et al.
Pubblicazione: (2025)

Almost Linear Size Edit Distance Sketch
di: Koucký, Michal, et al.
Pubblicazione: (2024)

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
di: Haeupler, Bernhard, et al.
Pubblicazione: (2026)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
di: Bentert, Matthias, et al.
Pubblicazione: (2025)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
di: Kirkpatrick, Yael, et al.
Pubblicazione: (2026)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
di: Georgiadis, Loukas, et al.
Pubblicazione: (2026)

Subquadratic Submodular Maximization with a General Matroid Constraint
di: Kobayashi, Yusuke, et al.
Pubblicazione: (2024)

Strategizing against No-Regret Learners in First-Price Auctions
di: Rubinstein, Aviad, et al.
Pubblicazione: (2024)

String Sanitization Under Edit Distance: Improved and Generalized
di: Mieno, Takuya, et al.
Pubblicazione: (2020)

Linear-space LCS enumeration with quadratic-time delay for two strings
di: Sakai, Yoshifumi
Pubblicazione: (2025)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
di: Paul-Pena, Daniel, et al.
Pubblicazione: (2024)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
di: Nogler, Jakob, et al.
Pubblicazione: (2024)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
di: Driemel, Anne, et al.
Pubblicazione: (2026)