Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms

DOI10.1016/j.tcs.2024.114402OpenAlexW4391113039WikidataQ129595195 ScholiaQ129595195MaRDI QIDQ6201335

Diptapriyo Majumdar, Ankush Acharyya, Vahideh Keikha, Supantha Pandit

Publication date: 20 February 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2024.114402

zbMATH Keywords

computational complexityapproximation algorithmsparameterized complexitykernelizationset cover conjectureconstrained geometric hitting set

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Improved approximation algorithms for geometric set cover
• Structure preserving reductions among convex optimization problems
• Optimal packing and covering in the plane are NP-complete
• A modified greedy heuristic for the set covering problem with improved worst case bound
• Almost optimal set covers in finite VC-dimension
• Graph problems with obligations
• Constrained hitting set problem with intervals
• A threshold of ln n for approximating set cover
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Kernelization Lower Bounds Through Colors and IDs
• On Problems as Hard as CNF-SAT
• Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
• The complexity of satisfiability problems
• Parameterized Algorithms