Polynomial-time approximation schemes for packing and piercing fat objects
From MaRDI portal
Publication:4808318
DOI10.1016/S0196-6774(02)00294-8zbMath1030.68093OpenAlexW2031149390WikidataQ56335603 ScholiaQ56335603MaRDI QIDQ4808318
Publication date: 27 May 2003
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0196-6774(02)00294-8
setComputational geometryDynamic programmingApproximation algorithmsHitting setMaximum independentQuadtreesSeparator theorems
Related Items (57)
Generalized disk graphs ⋮ Approximation algorithms on consistent dynamic map labeling ⋮ A randomized algorithm for online unit clustering ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Geometric representation of graphs in low dimension using axis parallel boxes ⋮ An improved approximation algorithm for the discrete Fréchet distance ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs ⋮ APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS ⋮ Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve ⋮ ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INSTERSECTING A STRAIGHT LINE ⋮ Efficient independent set approximation in unit disk graphs ⋮ Closest pair and the post office problem for stochastic points ⋮ Temporal interval cliques and independent sets ⋮ Geometric Packing under Nonuniform Constraints ⋮ PACKING A TRUCK — NOW WITH A TWIST! ⋮ A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space ⋮ Clique-based separators for geometric intersection graphs ⋮ Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane ⋮ Unnamed Item ⋮ Consistent dynamic map labeling with fairness and importance ⋮ On Covering Problems of Rado ⋮ Near-linear approximation algorithms for geometric hitting sets ⋮ Piercing translates and homothets of a convex body ⋮ Secure connected domination and secure total domination in unit disk graphs and rectangle graphs ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ Shifting strategy for geometric graphs without geometry ⋮ Approximation algorithms for intersection graphs ⋮ Computationally-feasible truthful auctions for convex bundles ⋮ Approximation algorithms for maximum independent set of a unit disk graph ⋮ MAXIMUM AREA INDEPENDENT SETS IN DISK INTERSECTION GRAPHS ⋮ Matching colored points with rectangles ⋮ Packing and covering with non-piercing regions ⋮ Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. ⋮ Anchored rectangle and square packings ⋮ Polynomial-time approximation schemes for piercing and covering with applications in wireless networks ⋮ On covering problems of Rado ⋮ Independent set of intersection graphs of convex objects in 2D ⋮ Minimum vertex cover in rectangle graphs ⋮ Approximating minimum independent dominating sets in wireless networks ⋮ Piercing all translates of a set of axis-parallel rectangles ⋮ Range assignment of base-stations maximizing coverage area without interference ⋮ Improved Algorithm for Maximum Independent Set on Unit Disk Graph ⋮ Domination in Geometric Intersection Graphs ⋮ Unnamed Item ⋮ Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks ⋮ Unnamed Item ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ Coloring and Maximum Independent Set of Rectangles ⋮ A note on maximum independent sets in rectangle intersection graphs ⋮ Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking ⋮ The reach of axis-aligned squares in the plane ⋮ On Partial Covering For Geometric Set Systems ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ Geometric red-blue set cover for unit squares and related problems ⋮ Unnamed Item ⋮ Piercing all translates of a set of axis-parallel rectangles
This page was built for publication: Polynomial-time approximation schemes for packing and piercing fat objects
