Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms
DOI10.1016/J.TCS.2024.114402OpenAlexW4391113039WikidataQ129595195 ScholiaQ129595195MaRDI QIDQ6201335FDOQ6201335
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
computational complexityapproximation algorithmsparameterized complexitykernelizationset cover conjectureconstrained geometric hitting set
Cites Work
- A threshold of ln n for approximating set cover
- Fundamentals of parameterized complexity
- Title not available (Why is that?)
- Almost optimal set covers in finite VC-dimension
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
- On problems as hard as CNF-SAT
- The complexity of satisfiability problems
- Parameterized algorithms
- Structure preserving reductions among convex optimization problems
- Kernelization lower bounds through colors and IDs
- Combinatorial optimization. Networks and matroids
- Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes
- Optimal packing and covering in the plane are NP-complete
- Improved approximation algorithms for geometric set cover
- A modified greedy heuristic for the set covering problem with improved worst case bound
- Graph problems with obligations
- Constrained hitting set problem with intervals
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)
