Approximability of longest run subsequence and complementary minimization problems

DOI10.4230/LIPICS.WABI.2025.3MaRDI QIDQ7302678zbMATH OpenFDO

Authors Yuichi Asahiro, Mingyang Gong, Jesper Jansson, Guohui Lin, Sichen Lu, Eiji Miyano, Hirotaka Ono, Toshiki Saitoh, S. Tanaka

Publication date 22 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.WABI.2025.3

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20)

Cites work

• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Approximation algorithms for the longest run subsequence problem
• Automata, Languages and Programming
• scientific article; zbMATH DE number 2086914 (Why is no real title available?)
• scientific article; zbMATH DE number 7696000 (Why is no real title available?)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Some optimal inapproximability results
• The importance of being biased
• The longest run subsequence problem

This page was built for publication: Approximability of longest run subsequence and complementary minimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7302678)