Exact algorithms and APX-hardness results for geometric packing and covering problems (Q390102): Difference between revisions

@@ Property / Mathematics Subject Classification ID @@
+C45
@@ Property / Mathematics Subject Classification ID: 52C45 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C39
@@ Property / Mathematics Subject Classification ID: 90C39 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6249137
@@ Property / zbMATH DE Number: 6249137 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+geometric set cover
@@ Property / zbMATH Keywords: geometric set cover / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+geometric packing
@@ Property / zbMATH Keywords: geometric packing / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+geometric hitting set
@@ Property / zbMATH Keywords: geometric hitting set / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+APX-hardness
@@ Property / zbMATH Keywords: APX-hardness / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+dynamic programming
@@ Property / zbMATH Keywords: dynamic programming / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.comgeo.2012.04.001
+Normal rank
@@ Property / OpenAlex ID @@
+W2124937241
@@ Property / OpenAlex ID: W2124937241 / rank @@
+Normal rank
@@ Property / cites work @@
+Lenses in arrangements of pseudo-circles and their applications
+Normal rank
@@ Property / cites work @@
+Some APX-completeness results for cubic graphs
@@ Property / cites work: Some APX-completeness results for cubic graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
+Normal rank
@@ Property / cites work @@
+Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
+Normal rank
@@ Property / cites work @@
+Q5452284
@@ Property / cites work: Q5452284 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexities of efficient solutions of rectilinear polygon cover problems
+Normal rank
@@ Property / cites work @@
+Almost optimal set covers in finite VC-dimension
@@ Property / cites work: Almost optimal set covers in finite VC-dimension / rank @@
+Normal rank
@@ Property / cites work @@
+On Column-Restricted and Priority Covering Integer Programs
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for maximum independent set of pseudo-disks
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for geometric set cover
+Normal rank
@@ Property / cites work @@
+Q5573028
@@ Property / cites work: Q5573028 / rank @@
+Normal rank
@@ Property / cites work @@
+PTAS for Weighted Set Cover on Unit Squares
@@ Property / cites work: PTAS for Weighted Set Cover on Unit Squares / rank @@
+Normal rank
@@ Property / cites work @@
+Hitting sets when the VC-dimension is small
@@ Property / cites work: Hitting sets when the VC-dimension is small / rank @@
+Normal rank
@@ Property / cites work @@
+WEIGHTED GEOMETRIC SET COVER PROBLEMS REVISITED
@@ Property / cites work: WEIGHTED GEOMETRIC SET COVER PROBLEMS REVISITED / rank @@
+Normal rank
@@ Property / cites work @@
+Fast approximation algorithms for a nonconvex covering problem
+Normal rank
@@ Property / cites work @@
+Improved results on geometric hitting set problems
+Normal rank
@@ Property / cites work @@
+Tight lower bounds for the size of epsilon-nets
@@ Property / cites work: Tight lower bounds for the size of epsilon-nets / rank @@
+Normal rank
@@ Property / cites work @@
+Optimization, approximation, and complexity classes
+Normal rank
@@ Property / cites work @@
+Weighted geometric set cover via quasi-uniform sampling
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:390102