Limits of local search: quality and efficiency
DOI10.1007/S00454-016-9819-XzbMATH Open1369.68339OpenAlexW2535021959MaRDI QIDQ527441FDOQ527441
Authors: 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
Recommendations
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cites Work
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Hitting sets when the VC-dimension is small
- Almost optimal set covers in finite VC-dimension
- Tighter estimates for \(\epsilon\)-nets for disks
- Geometric hitting sets for disks: theory and practice
- An improved line-separable algorithm for discrete unit disk cover
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- Fast approximation algorithms for a nonconvex covering problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
- On the discrete unit disk cover problem
- Covering Points by Unit Disks of Fixed Location
- Improved results on geometric hitting set problems
- A sublinear-time randomized approximation algorithm for matrix games
- Graph-theoretical conditions for inscribability and Delaunay realizability
- Unit disk cover problem in 2D
- Independent set of intersection graphs of convex objects in 2D
- Optimal halfspace range reporting in three dimensions
- Combinatorial geometry and its algorithmic applications. The Alcalá lectures
- Approximation algorithms for maximum independent set of pseudo-disks
- On Approximating the Depth and Related Problems
- State of the union (of geometric objects)
- Near-linear approximation algorithms for geometric hitting sets
- Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
- Speeding up the incremental construction of the union of geometric objects in practice.
- Simple PTAS's for families of graphs excluding a minor
- Guarding terrains via local search
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- A fast algorithm for the Boolean masking problem
- Packing and covering with non-piercing regions
- Approximation Schemes for Covering and Packing
Cited In (10)
- Effectiveness of local search for geometric optimization
- Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
- A tight analysis of geometric local search
- Bounds-Consistent Local Search
- Efficiency of Local Search
- PTAS for geometric hitting set problems via local search
- Improved local search for geometric hitting set
- Optimality of geometric local search
- Local search is a PTAS for feedback vertex set in minor-free graphs
- Commonalities in local search
This page was built for publication: Limits of local search: quality and efficiency
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q527441)
