Abstract / Description of output
We provide a perfect sampling algorithm for the hard-sphere model on subsets of R^d with expected running time linear in the volume under the assumption of strong spatial mixing. A large number of perfect and approximate sampling algorithms have been devised to sample from the hard-sphere model, and our perfect sampling algorithm is efficient for a range of parameters for which only efficient approximate samplers were previously known and is faster than these known approximate approaches. Our methods also extend to the more general setting of Gibbs point processes interacting via finite-range, repulsive potentials.
Original language | English |
---|---|
Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques |
Editors | Nicole Megow, Adam Smith |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Pages | 1-18 |
Number of pages | 18 |
ISBN (Electronic) | 9783959772969 |
DOIs | |
Publication status | Published - 4 Sept 2023 |
Event | 27th International Conference on Randomization and Computation and the 26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems - Georgia Institute of Technology, Atlanta, United States Duration: 11 Sept 2023 → 13 Sept 2023 https://randomconference.com/random-2023-home/ |
Publication series
Name | Leibniz International Proceedings in Informatics |
---|---|
Publisher | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
ISSN (Electronic) | 1868-8969 |
Conference
Conference | 27th International Conference on Randomization and Computation and the 26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems |
---|---|
Abbreviated title | APPROX/RANDOM 2023 |
Country/Territory | United States |
City | Atlanta |
Period | 11/09/23 → 13/09/23 |
Internet address |
Keywords / Materials (for Non-textual outputs)
- perfect sampling
- hard-sphere model
- Gibbs point processes