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

DOI10.1016/J.TCS.2024.114402MaRDI QIDQ6201335zbMATH OpenOpenAlexWikidataFDO

Authors Ankush Acharyya, Vahideh Keikha, Diptapriyo Majumdar, 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

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A modified greedy heuristic for the set covering problem with improved worst case bound
• A threshold of ln n for approximating set cover
• Almost optimal set covers in finite VC-dimension
• Combinatorial optimization. Networks and matroids
• Constrained hitting set problem with intervals
• Fundamentals of parameterized complexity
• Graph problems with obligations
• Improved approximation algorithms for geometric set cover
• Kernelization lower bounds through colors and IDs
• On problems as hard as CNF-SAT
• Optimal packing and covering in the plane are NP-complete
• Parameterized algorithms
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes
• Structure preserving reductions among convex optimization problems
• The complexity of satisfiability problems

This page was built for publication: Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms

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