Approximation schemes for covering and packing problems in image processing and VLSI

From MaRDI portal

Publication:3771608

Jump to:navigation, search

DOI10.1145/2455.214106zbMath0633.68027OpenAlexW2100961486MaRDI QIDQ3771608

Dorit S. Hochbaum, Wolfgang Maass

Publication date: 1985

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2455.214106

zbMATH Keywords

image processing packing VLSI shifting strategy polynomial approximation schemes worst case analysis of heuristics covering points in the Euclidean space strongly NP-complete problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of design theory to circuits and networks (94C30) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Lattice packing and covering (number-theoretic aspects) (11H31) Combinatorial aspects of packing and covering (05B40)

Related Items

Grid scheduling by on-line rectangle packing, On Locality-Sensitive Orderings and Their Applications, A PTAS for the Weighted Unit Disk Cover Problem, Approximation algorithms on consistent dynamic map labeling, Linear-Time Approximation Algorithms for Unit Disk Graphs, Algorithms for Steiner Connected Dominating Set Problem Based on Learning Automata Theory, On approximating MIS over B1-VPG graphs*, ON THE DISCRETE UNIT DISK COVER PROBLEM, Minimum Dominating Set Problem for Unit Disks Revisited, A Scheme for Computing Minimum Covers within Simple Regions, On the complexity of some geometric problems in unbounded dimension, Maximum lifetime connected coverage with two active-phase sensors, Linear Time Approximation Schemes for Geometric Maximum Coverage, Faster approximation for maximum independent set on unit disk graph, AN ALGORITHMIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS — WITH APPLICATIONS, Approximating the Spanning k-Tree Forest Problem, A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM, APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS, ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INSTERSECTING A STRAIGHT LINE, The homogeneous broadcast problem in narrow and wide strips. I: Algorithms, 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, PACKING A TRUCK — NOW WITH A TWIST!, Covering a set of points with a minimum number of equal disks via simulated annealing, Dispersing facilities on planar segment and circle amidst repulsion, Approximation schemes for covering and packing problems in image processing and VLSI, Approximation algorithms for the generalized incremental knapsack problem, Unnamed Item, Spectrum Bidding in Wireless Networks and Related, Two generalizations of proper coloring: hardness and approximability, Hitting geometric objects online via points in \(\mathbb{Z}^d\), A scheme for computing minimum covers within simple regions, A weakly robust PTAS for minimum clique partition in unit disk graphs, On Covering Problems of Rado, Near-linear approximation algorithms for geometric hitting sets, Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\), Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting), Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs, A PTAS for the cardinality constrained covering with unit balls, Secure connected domination and secure total domination in unit disk graphs and rectangle graphs, Many disjoint edges in topological graphs, Covering Polygons with Rectangles, Stabbing Convex Polygons with a Segment or a Polygon, Covering Points by Unit Disks of Fixed Location, Identifying Fixations in Gaze Data via Inner Density and Optimization, Covering segments with unit squares, Efficient Approximations for the Online Dispersion Problem, PERM for solving circle packing problem, The Maximum Exposure Problem., On Locality-Sensitive Orderings and Their Applications, AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER, Discrete unit square cover problem, Clique Clustering Yields a PTAS for max-Coloring Interval Graphs, MAXIMUM AREA INDEPENDENT SETS IN DISK INTERSECTION GRAPHS, Many disjoint edges in topological graphs, Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams., Hierarchically specified unit disk graphs, Improper colouring of (random) unit disk graphs, Polynomial-time approximation schemes for piercing and covering with applications in wireless networks, Optimizing active ranges for consistent dynamic map labeling, APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM, Hitting and Piercing Rectangles Induced by a Point Set, Unnamed Item, Unnamed Item, New heuristics for packing unequal circles into a circular container, A new heuristic recursive algorithm for the strip rectangular packing problem, Approximation algorithms for maximum two-dimensional pattern matching, On point covers of \(c-\)oriented polygons, On optimal placement of relay nodes for reliable connectivity in wireless sensor networks, Unnamed Item, Approximations for Steiner trees with minimum number of Steiner points, Improved Algorithm for Maximum Independent Set on Unit Disk Graph, Deadline TSP, Disjoint edges in complete topological graphs, Domination in Geometric Intersection Graphs, Maximum independent and disjoint coverage, On the Discrete Unit Disk Cover Problem, Covering and packing of rectilinear subdivision, Online unit covering in Euclidean space, Covering uncertain points in a tree, ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS, On the Number and Arrangement of Sensors for the Multiple Covering of Bounded Plane Domains, Sensor Cover and Double Partition, Analysis of a first-fit algorithm for the capacitated unit covering problem, Latency Constrained Aggregation in Chain Networks Admits a PTAS, A PTAS FOR MINIMUM d-HOP UNDERWATER SINK PLACEMENT PROBLEM IN 2-D UNDERWATER SENSOR NETWORKS, On Partial Covering For Geometric Set Systems, Capacitated Covering Problems in Geometric Spaces, Unnamed Item, On capacitated covering with unit balls, Evaluation of Labeling Strategies for Rotating Maps, A Probability Collectives Approach for Multi-Agent Distributed and Cooperative Optimization with Tolerance for Agent Failure, The maximum exposure problem, Approximation algorithms for aligning points, Approximability and hardness of geometric hitting set with axis-parallel rectangles, Novel hybrid heuristics for an extension of the dynamic relay deployment problem over disaster areas, Approximation schemes for the generalized extensible bin packing problem, 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, Covering many or few points with unit disks, On the complexity of some basic problems in computational convexity. I. Containment problems, A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang, Solving a \(k\)-node minimum label spanning arborescence problem to compress fingerprint templates, Parallel algorithm for minimum partial dominating set in unit disk graph, An effective hybrid algorithm for the problem of packing circles into a larger containing circle, An improved approximation algorithm for the discrete Fréchet distance, Almost optimal set covers in finite VC-dimension, An AFPTAS for variable sized bin packing with general activation costs, A PTAS for the horizontal rectangle stabbing problem, Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve, The inverse protein folding problem on 2D and 3D lattices, Interval selection in the streaming model, Relay node placement in two-tiered wireless sensor networks with base stations, Efficient independent set approximation in unit disk graphs, Polynomial time approximation schemes for minimum disk cover problems, Capacitated covering problems in geometric spaces, New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs, 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, Capacitated max-batching with interval graph compatibilities, Approximation algorithms for free-label maximization, Covering moving points with anchored disks, A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares, Winner determination in geometrical combinatorial auctions, Radar placement along banks of river, Theory and application of width bounded geometric separators, Liar's dominating set problem on unit disk graphs, Trimming of graphs, with application to point labeling, Minimum covering with travel cost, Shifting strategy for geometric graphs without geometry, An efficient polynomial time approximation scheme for load balancing on uniformly related machines, Approximation algorithms for hitting objects with straight lines, Minimum-energy broadcast and disk cover in grid wireless networks, Computationally-feasible truthful auctions for convex bundles, Approximation algorithms for maximum independent set of a unit disk graph, Two personification strategies for solving circles packing problem, Coloring intersection graphs of \(x\)-monotone curves in the plane, Rectangle blanket problem: binary integer linear programming formulation and solution algorithms, Covering a set of points in multidimensional space, Unit disk cover problem in 2D, A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem, Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking, Geometric hitting set for segments of few orientations, A basic algorithm for computer-aided design of material arrangement, Approximation algorithms for the unit disk cover problem in 2D and 3D, On the complexity of bandwidth allocation in radio networks, Near-linear time approximation schemes for geometric maximum coverage, On grids in topological graphs, Minimum vertex cover in ball graphs through local search, A 4.31-approximation for the geometric unique coverage problem on unit disks, Geometric Knapsack problems, Covering a line segment with variable radius discs, The within-strip discrete unit disk cover problem, An improved approximation algorithm for the most points covering problem, Exact and approximation algorithms for geometric and capacitated set cover problems, Local approximability of max-min and min-max linear programs, On covering problems of Rado, Minimum vertex cover in rectangle graphs, Optimization for first order Delaunay triangulations, The complexity of base station positioning in cellular networks, Smooth kinetic maintenance of clusters, Hyperbolic set covering problems with competing ground-set elements, 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, An exact algorithm for a class of geometric set-cover problems, Range assignment of base-stations maximizing coverage area without interference, Maximizing the number of obnoxious facilities to locate within a bounded region, Hitting sets online and unique-MAX coloring, Hierarchically specified unit disk graphs, Label placement by maximum independent set in rectangles, A note on maximum independent sets in rectangle intersection graphs, Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs, A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks, A better constant-factor approximation for weighted dominating set in unit disk graph, The most points connected-covering problem with two disks, An improved algorithm for online unit clustering, Fast stabbing of boxes in high dimensions, Finding, hitting and packing cycles in subexponential time on unit disk graphs, An improved algorithm for the packing of unequal circles within a larger containing circle, An effective quasi-human based heuristic for solving the rectangle packing problem, An efficient heuristic algorithm for two-dimensional rectangular packing problem with central rectangle, Experiments with unit disk cover algorithms for covering massive pointsets, Clique partitioning with value-monotone submodular cost, Approximating uniform triangular meshes in polygons., Geometric red-blue set cover for unit squares and related problems, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems., Shortest paths in intersection graphs of unit disks, An optimal algorithm for solving collision distance between convex polygons in plane, Approximation algorithm for minimum partial multi-cover under a geometric setting, Robustness of regional matching scheme over global matching scheme

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:3771608&oldid=17315866"