Approximation schemes for covering and packing problems in image processing and VLSI
From MaRDI portal
image processingpackingVLSIshifting strategypolynomial approximation schemesworst case analysis of heuristicscovering points in the Euclidean spacestrongly NP-complete problems
Analysis of algorithms and problem complexity (68Q25) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Combinatorial aspects of packing and covering (05B40) Applications of design theory to circuits and networks (94C30) Lattice packing and covering (number-theoretic aspects) (11H31)
Recommendations
- scientific article; zbMATH DE number 3888915
- Approximation algorithms for NP-complete problems on planar graphs
- Fast approximation algorithms for a nonconvex covering problem
- Complexities of efficient solutions of rectilinear polygon cover problems
- Close approximations of minimum rectangular coverings
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A beam search algorithm for the circular packing problem
- A dynamic adaptive local search algorithm for the circular packing problem
- A literature review on circle and sphere packing problems: models and methodologies
- A short note on a simple search heuristic for the diskspacking problem
- Adaptive beam search lookahead algorithms for the circular packing problem
- An effective hybrid algorithm for the problem of packing circles into a larger containing circle
- An improved algorithm for the packing of unequal circles within a larger containing circle
- Approximation schemes for covering and packing problems in image processing and VLSI
- Basin filling algorithm for the circular packing problem with equilibrium behavioral constraints
- Efficiently packing unequal disks in a circle
- Generating optimal T-shape cutting patterns for circular blanks
- Integrated container loading software for pulp and paper industry
- New heuristics for packing unequal circles into a circular container
- Optimizing the packing of cylinders into a rectangular container: A nonlinear approach
- PERM for solving circle packing problem
- Solving circle packing problems by global optimization: numerical results and industrial applications
- Solving the problem of packing equal and unequal circles in a circular container
- Tabu Search—Part I
- Tabu search -- uncharted domains
- Two personification strategies for solving circles packing problem
Cited in
(only showing first 100 items - show all)- Liar's dominating set problem on unit disk graphs
- Near-linear approximation algorithms for geometric hitting sets
- PERM for solving circle packing problem
- New heuristics for packing unequal circles into a circular container
- The most points connected-covering problem with two disks
- Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
- On covering problems of Rado
- Approximation schemes for covering and packing problems in image processing and VLSI
- Approximation algorithms for the unit disk cover problem in 2D and 3D
- Interval selection in data streams: weighted intervals and the insertion-deletion setting
- Maximum bipartite subgraphs of geometric intersection graphs
- A bicriteria approximation algorithm for the minimum hitting set problem in measurable range spaces
- An impossible combinatorial counting method in distance geometry
- A randomized algorithm for online unit clustering
- Approximation schemes for the generalized extensible bin packing problem
- A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM
- Fast stabbing of boxes in high dimensions
- Minimum vertex cover in rectangle graphs
- Improper colouring of (random) unit disk graphs
- On partial covering for geometric set systems
- A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
- An improved algorithm for online unit clustering
- Algorithms for covering barrier points by mobile sensors with line constraint
- scientific article; zbMATH DE number 7561427 (Why is no real title available?)
- PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs
- Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
- Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
- An improved approximation algorithm for the discrete Fréchet distance
- An improved approximation algorithm for the most points covering problem
- On the number and arrangement of sensors for the multiple covering of bounded plane domains
- Covering Points by Unit Disks of Fixed Location
- Tiling with Squares and Packing Dominos in Polynomial Time
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Covering polygons with rectangles
- Approximation algorithms for the partition set cover problem with penalties
- Covering many or few points with unit disks
- Geometric Knapsack problems
- Rectangle blanket problem: binary integer linear programming formulation and solution algorithms
- A constant approximation for colorful k-center
- Latency Constrained Aggregation in Chain Networks Admits a PTAS
- Approximation algorithms for free-label maximization
- Covering moving points with anchored disks
- An algorithmic framework for solving geometric covering problems -- with applications
- Algorithms for Steiner connected dominating set problem based on learning automata theory
- Approximation algorithm for minimum partial multi-cover under a geometric setting
- Approximation algorithms for maximum weighted target cover problem with distance limitations
- Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs
- Approximating the Spanning k-Tree Forest Problem
- Two generalizations of proper coloring: hardness and approximability
- Clique partitioning with value-monotone submodular cost
- Analysis of a first-fit algorithm for the capacitated unit covering problem
- An efficient heuristic algorithm for two-dimensional rectangular packing problem with central rectangle
- Maximum area independent sets in disk intersection graphs
- On grids in topological graphs
- Approximations for Steiner trees with minimum number of Steiner points
- Approximability and hardness of geometric hitting set with axis-parallel rectangles
- Evaluation of labeling strategies for rotating maps
- Shortest paths in intersection graphs of unit disks
- Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking
- The inverse protein folding problem on 2D and 3D lattices
- Radar placement along banks of river
- The maximum exposure problem
- Label placement by maximum independent set in rectangles
- Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
- A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
- Novel hybrid heuristics for an extension of the dynamic relay deployment problem over disaster areas
- A 4.31-approximation for the geometric unique coverage problem on unit disks
- Online unit clustering and unit covering in higher dimensions
- Near-linear time approximation schemes for geometric maximum coverage
- Optimizing active ranges for consistent dynamic map labeling
- A weakly robust PTAS for minimum clique partition in unit disk graphs
- On the complexity of some geometric problems in unbounded dimension
- Approximation algorithms for aligning points
- On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line
- A note on maximum independent sets in rectangle intersection graphs
- A clustering-based approach to kinetic closest pair
- Clique clustering yields a PTAS for max-coloring interval graphs
- A simpler PTAS for connected k-path vertex cover in homogeneous wireless sensor network
- Discrete unit square cover problem
- Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
- Covering a set of points in multidimensional space
- Weighted geometric set cover with rectangles of bounded integer side lengths
- PTAS for minimum cost multicovering with disks
- Capacitated max-batching with interval graph compatibilities
- Hierarchically specified unit disk graphs
- Minimum-energy broadcast and disk cover in grid wireless networks
- Unit disk cover problem in 2D
- A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang
- Grid scheduling by on-line rectangle packing
- Maximizing the number of obnoxious facilities to locate within a bounded region
- The algorithm and complexity of secure domination in 3-dimensional box graphs
- Hitting geometric objects online via points in \(\mathbb{Z}^d\)
- Sensor cover and double partition
- An improved line-separable algorithm for discrete unit disk cover
- Minimum covering with travel cost
- Shifting strategy for geometric graphs without geometry
- On the discrete unit disk cover problem
- Almost optimal set covers in finite VC-dimension
- Covering a line segment with variable radius discs
- Identifying Fixations in Gaze Data via Inner Density and Optimization
This page was built for publication: Approximation schemes for covering and packing problems in image processing and VLSI
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3771608)
