On partial covering for geometric set systems

DOI10.4230/LIPICS.SOCG.2018.47zbMATH Open1489.68359arXiv1711.04882OpenAlexW2962723793MaRDI QIDQ5115815FDOQ5115815

Authors: Tanmay Inamdar, Kasturi Varadarajan 

Publication date: 18 August 2020

Abstract: We study a generalization of the Set Cover problem called the emph{Partial Set Cover} in the context of geometric set systems. The input to this problem is a set system $(X,mathcalS)$, where $X$ is a set of elements and $mathcalS$ is a collection of subsets of $X$, and an integer $kle|X|$. The goal is to cover at least $k$ elements of $X$ by using a minimum-weight collection of sets from $mathcalS$. The main result of this article is an LP rounding scheme which shows that the integrality gap of the Partial Set Cover LP is at most a constant times that of the Set Cover LP for a certain projection of the set system $(X,mathcalS)$. As a corollary of this result, we get improved approximation guarantees for the Partial Set Cover problem for a large class of geometric set systems.

Full work available at URL: https://arxiv.org/abs/1711.04882

Recommendations

• Approximation algorithms for partial covering problems
• scientific article; zbMATH DE number 1754596
• On the set multicover problem in geometric settings
• Approximation algorithm for minimum partial multi-cover under a geometric setting
• On the set multi-cover problem in geometric settings

zbMATH Keywords

geometric set coverpartial set cover

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites Work

• A threshold of ln n for approximating set cover
• Hitting sets when the VC-dimension is small
• \(\epsilon\)-nets and simplex range queries
• New applications of random sampling in computational geometry
• Almost optimal set covers in finite VC-dimension
• Using homogeneous weights for approximating the partial cover problem
• Weighted geometric set cover via quasi-uniform sampling
• Approximation algorithms for partial covering problems
• Applications of approximation algorithms to cooperative games
• Epsilon nets and union complexity
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Improved results on geometric hitting set problems
• The budgeted maximum coverage problem
• Approximation schemes for covering and packing problems in image processing and VLSI
• Improved performance of the greedy algorithm for partial cover
• Analytical approach to parallel repetition
• A unified approach to approximating partial covering problems
• Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes
• Polynomial-time approximation schemes for packing and piercing fat objects
• PTAS for weighted set cover on unit squares
• Improved approximation for guarding simple galleries from the perimeter
• Improved approximation algorithms for geometric set cover
• Title not available (Why is that?)
• Improved bound for the union of fat triangles
• Improved approximations for guarding 1.5-dimensional terrains
• Guarding terrains via local search
• Packing and covering with non-piercing regions
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• Geometric red-blue set cover for unit squares and related problems
• On combinatorial approximation of covering 0-1 integer programs and partial set cover
• Multiobjective Disk Cover Admits a PTAS

Cited In (20)

• Overlarge sets and partial geometries
• A parameterized approximation scheme for generalized partial vertex cover
• Algorithms for covering multiple submodular constraints and applications
• Treewidth, crushing and hyperbolic volume
• Title not available (Why is that?)
• Approximation algorithm for minimum partial multi-cover under a geometric setting
• On colorful vertex and edge cover problems
• A technique for obtaining true approximations for \(k\)-center with covering constraints
• Geometric Set Cover and Hitting Sets for Polytopes in R
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• A unified approach to approximating partial covering problems
• On fair covering and hitting problems
• Minimum power partial multi-cover on a line
• Title not available (Why is that?)
• On approximating partial scenario set cover
• A Unified Approach to Approximating Partial Covering Problems
• On the positive-negative partial set cover problem
• A primal-dual algorithm for the minimum power partial cover problem
• Few cuts meet many point sets
• Parallel approximation for partial set cover

This page was built for publication: On partial covering for geometric set systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115815)