Cover Image

Improved Approximation Algorithms and Hardness Results for Shortest Common Superstring with Reverse Complements

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Yamano, Ryosuke, Shibuya, Tetsuo
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Improved Approximation Ratios for the Shortest Common Superstring Problem with Reverse Complements
by: Yamano, Ryosuke, et al.
Published: (2026)

Quantum Algorithms for the Shortest Common Superstring and Text Assembling Problems
by: Khadiev, Kamil, et al.
Published: (2023)

Greedy Conjecture for the Shortest Common Superstring Problem and its Strengthenings
by: Nikolaev, Maksim
Published: (2024)

An Algorithm for a Variation of the Shortest Common Superstring Problem
by: Gilfanov, Arthur
Published: (2024)

Hardness of Approximation for Shortest Path with Vector Costs
by: Carlson, Charlie, et al.
Published: (2025)

Differentially Private Selection using Smooth Sensitivity
by: Yamamoto, Akito, et al.
Published: (2024)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

Improved 2-Approximate Shortest Paths for close vertex pairs
by: Gupta, Manoj
Published: (2025)

New Algorithms and Hardness Results for Connected Clustering
by: Eube, Jan, et al.
Published: (2025)

Hardness and Approximation Algorithms for Balanced Districting Problems
by: Dharangutte, Prathamesh, et al.
Published: (2025)

Covering Approximate Shortest Paths with DAGs
by: Assadi, Sepehr, et al.
Published: (2025)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
by: Makarychev, Yury, et al.
Published: (2024)

Algorithms and Hardness Results for the $(k,\ell)$-Cover Problem
by: Madani, Amirali, et al.
Published: (2025)

Automating the Search for Small Hard Examples to Approximation Algorithms
by: Sharma, Eklavya
Published: (2025)

On Incremental Approximate Shortest Paths in Directed Graphs
by: Górkiewicz, Adam, et al.
Published: (2025)

Improved Approximation Guarantees and Hardness Results for MNL-Driven Product Ranking
by: Segev, Danny, et al.
Published: (2025)

Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs
by: Hillebrand, Quentin, et al.
Published: (2024)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
by: Das, Rathish, et al.
Published: (2025)

Faster Algorithms for Shortest Unique or Absent Substrings
by: Charalampopoulos, Panagiotis, et al.
Published: (2026)

On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms
by: Albers, Susanne, et al.
Published: (2025)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
by: Dory, Michal, et al.
Published: (2022)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
by: Chitnis, Rajesh, et al.
Published: (2024)

Improved Additive Approximation Algorithms for APSP
by: Jin, Ce, et al.
Published: (2025)

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
by: Chan, Timothy M., et al.
Published: (2025)

Massively Parallel Algorithms for Approximate Shortest Paths
by: Dory, Michal, et al.
Published: (2024)

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2024)

Improved Hardness-of-Approximation for Token Swapping
by: Hiken, Sam, et al.
Published: (2024)

Hardness and Approximation for Coloring Digraphs
by: Chalermsook, Parinya, et al.
Published: (2026)

Improved Approximation Algorithm for Maximum Balanced Biclique
by: Manurangsi, Pasin
Published: (2026)

Improved Approximation Algorithms for Three-Dimensional Knapsack
by: Jansen, Klaus, et al.
Published: (2025)

An Improved Approximation Algorithm for Metric Triangle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
by: Choudhary, Keerti, et al.
Published: (2025)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
by: Yan, Shuyi
Published: (2025)

Hardness and Algorithmic Results for Roman \{3\}-Domination
by: Reddy, Sangam Balchandar
Published: (2025)

Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
by: Armbruster, Alexander, et al.
Published: (2026)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
by: Gadekar, Ameet, et al.
Published: (2025)

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
by: Atalig, Sunny, et al.
Published: (2024)

Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
by: Zhao, Jingyang, et al.
Published: (2022)