ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INSTERSECTING A STRAIGHT LINE

DOI10.15826/umj.2016.2.010zbMath1396.68127OpenAlexW2560035725MaRDI QIDQ4581438

Daniel M. Khachai, Mikhail Yu. Khachay

Publication date: 17 August 2018

Published in: Ural mathematical journal (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/umj25

zbMATH Keywords

dynamic programmingcomputational geometryparameterized complexityhitting set problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Uses Software

• AdaBoost.MH

Cites Work

• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• Committee polyhedral separability: complexity and polynomial approximation
• \(\epsilon\)-nets and simplex range queries
• Optimal packing and covering in the plane are NP-complete
• Almost optimal set covers in finite VC-dimension
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line
• Approximation schemes for covering and packing problems in image processing and VLSI
• Polynomial-time approximation schemes for packing and piercing fat objects
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INSTERSECTING A STRAIGHT LINE