Approximation algorithms for maximum independent set of pseudo-disks

DOI10.1145/1542362.1542420zbMATH Open1388.68285arXiv1103.1431OpenAlexW2148431844MaRDI QIDQ5370733FDOQ5370733

Authors: Timothy M. Chan, Sariel Har-Peled 

Publication date: 20 October 2017

Published in: Proceedings of the twenty-fifth annual symposium on Computational geometry (Search for Journal in Brave)

Abstract: We present approximation algorithms for maximum independent set of pseudo-disks in the plane, both in the weighted and unweighted cases. For the unweighted case, we prove that a local search algorithm yields a PTAS. For the weighted case, we suggest a novel rounding scheme based on an LP relaxation of the problem, which leads to a constant-factor approximation. Most previous algorithms for maximum independent set (in geometric settings) relied on packing arguments that are not applicable in this case. As such, the analysis of both algorithms requires some new combinatorial ideas, which we believe to be of independent interest.

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

Recommendations

• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation algorithms for maximum independent set of a unit disk graph
• Faster approximation for maximum independent set on unit disk graph
• Efficient independent set approximation in unit disk graphs
• Publication:4504025
• Improved algorithm for maximum independent set on unit disk graph
• A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
• scientific article; zbMATH DE number 3881891
• Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
• Exact algorithms for maximum independent set

zbMATH Keywords

local searchapproximation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cited In (22)

• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• On pseudo-disk hypergraphs
• Balanced independent and dominating sets on colored interval graphs
• Minimum vertex cover in rectangle graphs
• Geometric Packing under Nonuniform Constraints
• Improved results on geometric hitting set problems
• Independent set in \(k\)-claw-free graphs: conditional \(\chi \)-boundedness and the power of LP/SDP relaxations
• Title not available (Why is that?)
• Robust online algorithms for dynamic choosing problems
• Maximum area independent sets in disk intersection graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• Approximation algorithms for maximum independent set of a unit disk graph
• PTAS for minimum \(k\)-path vertex cover in ball graph
• Near-linear algorithms for geometric hitting sets and set covers
• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
• Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
• Local search is a PTAS for feedback vertex set in minor-free graphs
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
• Coloring and maximum independent set of rectangles
• Limits of local search: quality and efficiency

This page was built for publication: Approximation algorithms for maximum independent set of pseudo-disks

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