Cover Image

Deterministic Longest Common Subsequence Approximation in Near-Linear Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Boneh, Itai, Golan, Shay, Kraus, Matan
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms F.2.0
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hairpin Completion Distance Lower Bound
by: Boneh, Itai, et al.
Published: (2024)

The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$
by: Boneh, Itai, et al.
Published: (2025)

Hamming Distance Oracle
by: Boneh, Itai, et al.
Published: (2024)

String 2-Covers with No Length Restrictions
by: Boneh, Itai, et al.
Published: (2024)

Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
by: Hušek, Radek, et al.
Published: (2020)

Searching 2D-Strings for Matching Frames
by: Boneh, Itai, et al.
Published: (2023)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
by: Boneh, Itai, et al.
Published: (2025)

Planar Multiway Cut with Terminals on Few Faces
by: Pandey, Sukanya, et al.
Published: (2025)

Clustering Permutations: New Techniques with Streaming Applications
by: Chakraborty, Diptarka, et al.
Published: (2022)

Calculation of the Comparative Efficiency of Algorithms Using a Single Metric
by: Chakraborty, Arya
Published: (2024)

Arcee: An OCM-Solver
by: Boehmer, Kimon, et al.
Published: (2024)

The Pareto Frontier of Randomized Learning-Augmented Online Bidding
by: Degryse, Mathis, et al.
Published: (2026)

On the I/O Complexity of the CYK Algorithm and of a Family of Related DP Algorithms
by: De Stefani, Lorenzo, et al.
Published: (2024)

Deterministically Simulating Barely Random Algorithms in the Random-Order Arrival Model
by: Borodin, Allan, et al.
Published: (2025)

Longest Common Extensions with Wildcards: Trade-off and Applications
by: Bathie, Gabriel, et al.
Published: (2024)

Which $L_p$ norm is the fairest? Approximations for fair facility location across all "$p$"
by: Gupta, Swati, et al.
Published: (2022)

Online Paging with Heterogeneous Cache Slots
by: Chrobak, Marek, et al.
Published: (2022)

Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
by: Boneh, Itai, et al.
Published: (2025)

String Problems in the Congested Clique Model
by: Golan, Shay, et al.
Published: (2025)

Efficient Approximation of Fractional Hypertree Width
by: Korchemna, Viktoriia, et al.
Published: (2024)

Approximation Algorithms for Capacitated Vehicle Routing Problems: A Comprehensive Survey
by: Chen, Yongyu
Published: (2023)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
by: Lokshtanov, Daniel, et al.
Published: (2024)

Provably Small Portfolios for Multiobjective Optimization with Application to Subsidized Facility Location
by: Gupta, Swati, et al.
Published: (2025)

Balancing Notions of Equity: Trade-offs Between Fair Portfolio Sizes and Achievable Guarantees
by: Gupta, Swati, et al.
Published: (2023)

Stochastic Function Certification with Correlations
by: Ghuge, Rohan, et al.
Published: (2026)

An Optimal Randomized Algorithm for Finding the Saddlepoint
by: Dallant, Justin, et al.
Published: (2024)

New Entropy Measures for Tries with Applications to the XBWT
by: Carfagna, Lorenzo, et al.
Published: (2025)

Replicability in High Dimensional Statistics
by: Hopkins, Max, et al.
Published: (2024)

The Degree of Fairness in Efficient House Allocation
by: Hosseini, Hadi, et al.
Published: (2024)

Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
by: Chauhan, Archit, et al.
Published: (2026)

An Algorithm for the Longest Common Subsequence and Substring Problem for Multiple Strings
by: Li, Rao
Published: (2024)

Improved Lower Bounds on the Expected Length of Longest Common Subsequences
by: Heineman, George T., et al.
Published: (2024)

Connected Components in Linear Work and Near-Optimal Time
by: Farhadi, Alireza, et al.
Published: (2023)

Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop
by: Antoniadis, Antonios, et al.
Published: (2020)

Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication
by: Elkin, Michael, et al.
Published: (2024)

A simple polynomial-time approximation algorithm for the total variation distance between two product distributions
by: Feng, Weiming, et al.
Published: (2022)

A Linear-Time 1.5-Approximation for Broadcasting in k-Cycle Graphs
by: Bringolf, Jeffrey, et al.
Published: (2025)

The Longest Common Bitonic Subsequence: A Match-Sensitive Dynamic Programming Approach
by: Rahat, Md. Tanzeem, et al.
Published: (2025)

Range Longest Increasing Subsequence and its Relatives
by: S., Karthik C., et al.
Published: (2024)

Online Bin Packing with Predictions
by: Angelopoulos, Spyros, et al.
Published: (2021)