Optimal packing and covering in the plane are NP-complete
From MaRDI portal
Publication:1157170
DOI10.1016/0020-0190(81)90111-3zbMath0469.68053OpenAlexW2013451793WikidataQ57568241 ScholiaQ57568241MaRDI QIDQ1157170
Robert J. Fowler, Steven L. Tanimoto, Michael S. Paterson
Publication date: 1981
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(81)90111-3
Analysis of algorithms and problem complexity (68Q25) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Discrete mathematics in relation to computer science (68R99)
Related Items (only showing first 100 items - show all)
Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons ⋮ ON THE DISCRETE UNIT DISK COVER PROBLEM ⋮ Unnamed Item ⋮ On the complexity of some geometric problems in unbounded dimension ⋮ Boxicity and treewidth ⋮ A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM ⋮ Co-Clustering Under the Maximum Norm ⋮ ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INSTERSECTING A STRAIGHT LINE ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ Tiling with Squares and Packing Dominos in Polynomial Time ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ PACKING A TRUCK — NOW WITH A TWIST! ⋮ Mixed-Integer programming models for irregular strip packing based on vertical slices and feasibility cuts ⋮ Improving emergency services efficiency during Islamic pilgrimage through optimal allocation of facilities ⋮ Covering a set of points with a minimum number of equal disks via simulated annealing ⋮ On the geometric priority set cover problem ⋮ Exact algorithms and hardness results for geometric red-blue hitting set problem ⋮ Approximating the discrete center line segment in linear time ⋮ Unnamed Item ⋮ Hitting geometric objects online via points in \(\mathbb{Z}^d\) ⋮ On Covering Problems of Rado ⋮ Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\) ⋮ Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms ⋮ Constrained hitting set problem with intervals ⋮ Many disjoint edges in topological graphs ⋮ Covering Polygons with Rectangles ⋮ THE ALIGNED K-CENTER PROBLEM ⋮ Efficient Approximations for the Online Dispersion Problem ⋮ The Maximum Exposure Problem. ⋮ Jump Number of Two-Directional Orthogonal Ray Graphs ⋮ AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER ⋮ Discrete unit square cover problem ⋮ Many disjoint edges in topological graphs ⋮ Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. ⋮ AN APPROXIMATION ALGORITHM FOR LOCATING MAXIMAL DISKS WITHIN CONVEX POLYGONS ⋮ Hierarchically specified unit disk graphs ⋮ Hitting and Piercing Rectangles Induced by a Point Set ⋮ Approximation algorithms for maximum two-dimensional pattern matching ⋮ On point covers of \(c-\)oriented polygons ⋮ Piercing all translates of a set of axis-parallel rectangles ⋮ TERRAIN DECOMPOSITION AND LAYERED MANUFACTURING ⋮ Cubicity of interval graphs and the claw number ⋮ Convex Cardinal Shape Composition ⋮ Computing coverage kernels under restricted settings ⋮ Disjoint edges in complete topological graphs ⋮ The pallet loading problem: a review of solution methods and computational experiments ⋮ Minimum membership covering and hitting ⋮ Combining Traditional Map Labeling with Boundary Labeling ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack ⋮ Unnamed Item ⋮ On Geometric Set Cover for Orthants ⋮ On the Discrete Unit Disk Cover Problem ⋮ Covering and packing of rectilinear subdivision ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ Online unit covering in Euclidean space ⋮ Local search strikes again: PTAS for variants of geometric covering and packing ⋮ Coloring and Maximum Independent Set of Rectangles ⋮ Covering a set of line segments with a few squares ⋮ Covering a set of line segments with a few squares ⋮ ON PLANAR MEDIANOID COMPETITIVE LOCATION PROBLEMS WITH MANHATTAN DISTANCE ⋮ Dynamic data structures for fat objects and their applications ⋮ Locating two obnoxious facilities using the weighted maximin criterion ⋮ On capacitated covering with unit balls ⋮ Decision Trees for Geometric Models ⋮ Diameter partitioning ⋮ The maximum exposure problem ⋮ A mixed integer formulation for maximal covering by inclined parallelograms ⋮ Improved algorithms for resource allocation under varying capacity ⋮ \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point ⋮ Approximability and hardness of geometric hitting set with axis-parallel rectangles ⋮ Weighted geometric set cover with rectangles of bounded integer side lengths ⋮ Online unit clustering and unit covering in higher dimensions ⋮ A randomized algorithm for online unit clustering ⋮ On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ Optimal packing of similar triangles ⋮ A mixed breadth-depth first strategy for the branch and bound tree of Euclidean \(k\)-center problems ⋮ A heuristic for the p-center problem in graphs ⋮ A simulated annealing approach to the nesting problem in the textile manufacturing industry ⋮ The nesting problem in the leather manufacturing industry ⋮ Target coverage with minimum number of camera sensors ⋮ Geometric optimization and the polynomial hierarchy ⋮ Parallel algorithm for minimum partial dominating set in unit disk graph ⋮ Packing 16, 17 or 18 circles in an equilateral triangle ⋮ Geometric optimization and \(D^ P\)-completeness ⋮ A new approach to cooperative competition in facility location problems: mathematical formulations and an approximation algorithm ⋮ A clique covering MIP model for the irregular strip packing problem ⋮ Max point-tolerance graphs ⋮ Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve ⋮ Complexity of tiling a polygon with trominoes or bars ⋮ Covering points by disjoint boxes with outliers ⋮ Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane ⋮ Optimal packings of 2,3, and 4 equal balls into a cubical flat 3-torus ⋮ Convexity in partial cubes: the hull number ⋮ Approximation algorithms for free-label maximization ⋮ Covering moving points with anchored disks ⋮ Near-linear approximation algorithms for geometric hitting sets ⋮ Theory and application of width bounded geometric separators ⋮ Piercing translates and homothets of a convex body ⋮ Lexicographic local search and the \(p\)-center problem.
Cites Work
This page was built for publication: Optimal packing and covering in the plane are NP-complete
