Hardness of approximation for non-overlapping local alignments.

DOI10.1016/S0166-218X(03)00344-5zbMath1100.68039MaRDI QIDQ1427808

Hiroyuki Nagashima, Koichi Yamazaki

Publication date: 14 March 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Approximation algorithmsRectanglesLocal alignmentsMAX \(k\)SAT-\(B\)Maximum weighted independent set problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Inapproximability of maximal strip recovery

Cites Work

• Optimal packing and covering in the plane are NP-complete
• Optimization, approximation, and complexity classes
• Label placement by maximum independent set in rectangles
• On Local Search for Weighted k-Set Packing
• When the cartesian product of directed cycles is Hamiltonian
• Algorithms on Strings, Trees and Sequences
• Non-approximability results for optimization problems on bounded degree instances
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Hardness of approximation for non-overlapping local alignments.