A tight analysis of geometric local search
type: Item
instance of: scholarly article
title: A tight analysis of geometric local search
zbMATH Open document ID: 1497.68572
author: Bruno Jartoux
author: Nabil H. Mustafa
published in: Discrete \& Computational Geometry
publication date: 2022-03-21T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 7493727
zbMATH Keywords: local search
zbMATH Keywords: expansion
zbMATH Keywords: matchings
zbMATH Keywords: Hall's marriage theorem
MaRDI profile type: Publication
full work available at URL: s00454-021-00343-y
OpenAlex ID: W4206135143
cites work: Independent set of intersection graphs of convex objects in 2D
cites work: A Separator Theorem for Nonplanar Graphs
cites work: Q5111691
cites work: Local Search Heuristics for k-Median and Facility Location Problems
cites work: Approximation Schemes for Covering and Packing
cites work: Limits of local search: quality and efficiency
cites work: Simple PTAS's for families of graphs excluding a minor
cites work: On the efficiency of polynomial time approximation schemes
cites work: Exact algorithms and APX-hardness results for geometric packing and covering problems
cites work: Approximation algorithms for maximum independent set of pseudo-disks
cites work: Unit disk graphs
cites work: Q4219187
cites work: Geometric packing under non-uniform constraints
cites work: An Approximation Scheme for Terrain Guarding
cites work: Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
cites work: Packing and Covering with Non-Piercing Regions
cites work: Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
cites work: Fast approximation algorithms for a nonconvex covering problem
cites work: Q5767542
cites work: An inequality related to the isoperimetric inequality
cites work: Algorithms – ESA 2005
cites work: Parameterized Complexity of Independence and Domination on Geometric Graphs
cites work: Separators for sphere-packings and nearest neighbor graphs
cites work: Improved results on geometric hitting set problems
cites work: Sparsity. Graphs, structures, and algorithms
cites work: Planar Support for Non-piercing Regions and Applications
DOI: 10.1007/S00454-021-00343-Y
description: scientific article; zbMATH DE number 7493727