Approximate Integer Solution Counts over Linear Arithmetic Constraints

• URL: http://arxiv.org/abs/2312.08776v1
• Date: Thu, 14 Dec 2023 09:53:54 GMT
• Title: Approximate Integer Solution Counts over Linear Arithmetic Constraints
• Authors: Cunjing Ge
• Abstract summary: We propose a new framework to approximate the lattice counts inside a polytope with a new random-walk sampling method. Our algorithm could solve polytopes with dozens of dimensions, which significantly outperforms state-of-the-art counters.
• Score: 2.28438857884398
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Counting integer solutions of linear constraints has found interesting applications in various fields. It is equivalent to the problem of counting lattice points inside a polytope. However, state-of-the-art algorithms for this problem become too slow for even a modest number of variables. In this paper, we propose a new framework to approximate the lattice counts inside a polytope with a new random-walk sampling method. The counts computed by our approach has been proved approximately bounded by a $(\epsilon, \delta)$-bound. Experiments on extensive benchmarks show that our algorithm could solve polytopes with dozens of dimensions, which significantly outperforms state-of-the-art counters.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Mathematical Programming Algorithms for Convex Hull Approximation with a Hyperplane Budget [0.0]
  We search for a convex polyhedron with at most K faces, containing all the positive points and no negative point. The problem is known in the literature for pure convex polyhedral approximation. Our interest stems from its possible applications in constraint learning.
  arXiv  Detail & Related papers  (2024-07-24T15:08:52Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB) Existing methods in the R-CPE-MAB can be seen as a special case of the so-called transductive linear bandits. We propose an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity matches the lower bound.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• Accelerated Nonnegative Tensor Completion via Integer Programming [7.3149416054553065]
  We present an approach to nonnegative tensor completion based on integer programming. We explore several variants that can maintain the same theoretical guarantees as the algorithm, but offer potentially faster computation.
  arXiv  Detail & Related papers  (2022-11-28T21:00:25Z)
• Nonnegative Tensor Completion via Integer Optimization [5.932152752097064]
  We prove that our algorithm converges in a linear (in numerical tolerance) number of oracle steps, while achieving the information-theoretic rate. Because the norm is defined using a 0-1 polytope, this means we can use integer linear programming to solve linear separation problems over the polytope.
  arXiv  Detail & Related papers  (2021-11-08T15:43:19Z)
• Efficient Large Scale Inlier Voting for Geometric Vision Problems [3.1231364554255636]
  Outlier rejection and equivalently inlier set optimization is a key ingredient in numerous applications in computer vision. We present an efficient and general algorithm for outlier rejection based on "intersecting" $k$-dimensional surfaces in $Rd$. We demonstrate the versatility of the approach on several camera posing problems with a high number of matches at low inlier ratio.
  arXiv  Detail & Related papers  (2021-07-25T14:13:07Z)
• Mean Field Approximation for solving QUBO problems [0.0]
  We show that the statistical physics approach and the quantum mechanical approach in the mean field annealing give the same result. Our methods consist of a set of simple gradient-based minimizations with continuous variables, thus easy to simulate.
  arXiv  Detail & Related papers  (2021-06-06T20:35:28Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.