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