Limits of local search: quality and efficiency

DOI10.1007/s00454-016-9819-xzbMath1369.68339OpenAlexW2535021959MaRDI QIDQ527441

Norbert Bus, Shashwat Garg, Nabil H. Mustafa, Saurabh Ray

Publication date: 11 May 2017

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-016-9819-x

zbMATH Keywords

local searchgeometric algorithmsDelaunay triangulationdiskshitting sets

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Related Items (5)

Local search is a PTAS for feedback vertex set in minor-free graphs ⋮ Covering segments with unit squares ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A tight analysis of geometric local search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tighter estimates for \(\epsilon\)-nets for disks
• Unit disk cover problem in 2D
• Improved results on geometric hitting set problems
• Hitting sets when the VC-dimension is small
• Graph-theoretical conditions for inscribability and Delaunay realizability
• Speeding up the incremental construction of the union of geometric objects in practice.
• Almost optimal set covers in finite VC-dimension
• A sublinear-time randomized approximation algorithm for matrix games
• Simple PTAS's for families of graphs excluding a minor
• Near-linear approximation algorithms for geometric hitting sets
• Independent set of intersection graphs of convex objects in 2D
• Guarding terrains via local search
• Geometric Hitting Sets for Disks: Theory and Practice
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER
• Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• On Approximating the Depth and Related Problems
• A fast algorithm for the Boolean masking problem
• Fast approximation algorithms for a nonconvex covering problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Packing and Covering with Non-Piercing Regions
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Approximation Schemes for Covering and Packing
• ON THE DISCRETE UNIT DISK COVER PROBLEM
• Approximation algorithms for maximum independent set of pseudo-disks
• Covering Points by Unit Disks of Fixed Location

This page was built for publication: Limits of local search: quality and efficiency