scientific article; zbMATH DE number 7053377
From MaRDI portal
Publication:5743501
zbMath1421.68198MaRDI QIDQ5743501
Jochen Könemann, Timothy M. Chan, Malcolm Sharpe, Elyot Grant
Publication date: 10 May 2019
Full work available at URL: https://dl.acm.org/citation.cfm?id=2095241
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
Tighter estimates for \(\epsilon\)-nets for disks ⋮ On pseudo-disk hypergraphs ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces ⋮ Parallel algorithm for minimum partial dominating set in unit disk graph ⋮ Hypergraph representation via axis-aligned point-subspace cover ⋮ Linear Time Approximation Schemes for Geometric Maximum Coverage ⋮ A PTAS for the horizontal rectangle stabbing problem ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ On the geometric set multicover problem ⋮ Minimum power partial multi-cover on a line ⋮ Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ Capacitated covering problems in geometric spaces ⋮ On the geometric priority set cover problem ⋮ Geometric stabbing via threshold rounding and factor revealing LPs ⋮ Constant-Factor Approximation for TSP with Disks ⋮ Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ Unnamed Item ⋮ Constructing planar support for non-piercing regions ⋮ Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time ⋮ Covering segments with unit squares ⋮ Fair Scheduling via Iterative Quasi-Uniform Sampling ⋮ Near-linear time approximation schemes for geometric maximum coverage ⋮ Packing and covering with non-piercing regions ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Computing a tree having a small vertex cover ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation algorithms for the connected sensor cover problem ⋮ On Geometric Set Cover for Orthants ⋮ Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks ⋮ Approximability of covering cells with line segments ⋮ When are epsilon-nets small? ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ A primal-dual algorithm for the minimum power partial cover problem ⋮ On Partial Covering For Geometric Set Systems ⋮ Capacitated Covering Problems in Geometric Spaces ⋮ Twin-width and polynomial kernels ⋮ Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time ⋮ Approximation algorithm for minimum partial multi-cover under a geometric setting
Cites Work
- Improved approximation algorithms for geometric set cover
- Hitting sets when the VC-dimension is small
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- \(\epsilon\)-nets and simplex range queries
- Flows and generalized coloring theorems in graphs
- Voronoi diagrams in higher dimensions under certain polyhedral distance functions
- On a set of almost deterministic k-independent random variables
- New applications of random sampling in computational geometry
- Applications of random sampling in computational geometry. II
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Almost optimal set covers in finite VC-dimension
- Approximation algorithms for covering/packing integer programs
- Weighted geometric set cover via quasi-uniform sampling
- On Capacitated Set Cover Problems
- A threshold of ln n for approximating set cover
- On Column-Restricted and Priority Covering Integer Programs
- Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- Improved Approximation Guarantees for Packing and Covering Integer Programs
- Epsilon nets and union complexity
- Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
- Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
