Near-linear algorithms for geometric hitting sets and set covers
PK Agarwal, J Pan - Proceedings of the thirtieth annual symposium on …, 2014 - dl.acm.org
Given a finite range space Σ=(X, R), with N=| X|+| R|, we present two simple algorithms,
based on the multiplicative-weight method, for computing a small-size hitting set or set cover …
based on the multiplicative-weight method, for computing a small-size hitting set or set cover …
Construction of energy functions for lattice heteropolymer models: Efficient encodings for constraint satisfaction programming and quantum annealing
R Babbush, A Perdomo‐Ortiz… - … in Chemical Physics …, 2014 - Wiley Online Library
This chapter presents a general construction of the free energy function for the two‐
dimensional lattice heteropolymer model widely used to study the dynamics of proteins. It …
dimensional lattice heteropolymer model widely used to study the dynamics of proteins. It …
New existence proofs ε-nets
E Pyrga, S Ray - Proceedings of the twenty-fourth annual symposium on …, 2008 - dl.acm.org
We describe a new technique for proving the existence of small μ-nets for hypergraphs
satisfying certain simple conditions. The technique is particularly useful for proving o (1/μ log …
satisfying certain simple conditions. The technique is particularly useful for proving o (1/μ log …
Near-linear algorithms for geometric hitting sets and set covers
PK Agarwal, J Pan - Discrete & Computational Geometry, 2020 - Springer
Given a finite range space Σ=(X, R) Σ=(X, R), with N=| X|+| R| N=| X|+| R|, we present two
simple algorithms, based on the multiplicative-weight method, for computing a small-size …
simple algorithms, based on the multiplicative-weight method, for computing a small-size …
PTAS for weighted set cover on unit squares
T Erlebach, EJ Van Leeuwen - International Workshop on Randomization …, 2010 - Springer
We study the planar version of Minimum-Weight Set Cover, where one has to cover a given
set of points with a minimum-weight subset of a given set of planar objects. For the unit …
set of points with a minimum-weight subset of a given set of planar objects. For the unit …
[图书][B] Optimization and approximation on systems of geometric objects
EJ van Leeuwen - 2009 - pure.uva.nl
Can a combinatorial optimization problem be approximated better if it is determined by a
system of geometric objects? Many combinatorial optimization problems are NP-hard to …
system of geometric objects? Many combinatorial optimization problems are NP-hard to …
Near-linear approximation algorithms for geometric hitting sets
Given a set system (X, R), the hitting set problem is to find a smallest-cardinality subset H⊆
X, with the property that each range R∈ R has a non-empty intersection with H. We present …
X, with the property that each range R∈ R has a non-empty intersection with H. We present …
A bicriteria approximation algorithm for the minimum hitting set problem in measurable range spaces
K Elbassioni - Operations Research Letters, 2023 - Elsevier
We consider the problem of finding a minimum-size hitting set in a range space F=(Q, R)
defined by a measure on a family of subsets of an infinite set R. We observe that, under …
defined by a measure on a family of subsets of an infinite set R. We observe that, under …
Algorithms for the construction of an optimal cover for sets in three-dimensional Euclidean space
VN Ushakov, PD Lebedev - Proceedings of the Steklov Institute of …, 2016 - Springer
The problem of an optimal cover of sets in three-dimensional Euclidian space by the union
of a fixed number of equal balls, where the optimality criterion is the radius of the balls, is …
of a fixed number of equal balls, where the optimality criterion is the radius of the balls, is …