Fugu-MT 論文翻訳(概要): Approximate Integer Solution Counts over Linear Arithmetic Constraints

論文の概要: Approximate Integer Solution Counts over Linear Arithmetic Constraints

arxiv url: http://arxiv.org/abs/2312.08776v1
Date: Thu, 14 Dec 2023 09:53:54 GMT
ステータス: 処理完了
システム内更新日: 2023-12-15 22:57:57.656751
Title: Approximate Integer Solution Counts over Linear Arithmetic Constraints
Title（参考訳）: 線形算術的制約による近似整数解数
Authors: Cunjing Ge
Abstract要約: 本稿では,ポリトープ内の格子数に近似する新しいフレームワークを提案する。我々のアルゴリズムは、数十次元のポリトープを解くことができ、最先端のカウンタを著しく上回る。
参考スコア（独自算出の注目度）: 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.
Abstract（参考訳）: 線形制約の整数解を数えることは、様々な分野の興味深い応用を見出した。これは、ポリトープ内の格子点を数える問題と同値である。しかし、この問題に対する最先端のアルゴリズムは、控えめな数の変数でも遅すぎる。本稿では,新しいランダムウォークサンプリング法を用いて,ポリトープ内の格子数を近似する新しい枠組みを提案する。このアプローチによって計算されたカウントは、およそ$(\epsilon, \delta)$-boundによって制限されている。広範なベンチマーク実験により,本アルゴリズムは数十次元のポリトープを解き,最先端のカウンタを大きく上回ることを示した。

関連論文リスト

Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
Mathematical Programming Algorithms for Convex Hull Approximation with a Hyperplane Budget [0.0]
我々は、すべての正の点と負の点を含む、ほとんどのK面を持つ凸多面体を探索する。この問題は純粋凸多面体近似の文献で知られている。私たちの関心は、制約学習の応用の可能性に起因しています。
論文参考訳（メタデータ） (2024-07-24T15:08:52Z)
An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文参考訳（メタデータ） (2023-06-15T15:37:31Z)
Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-31T19:14:30Z)
Accelerated Nonnegative Tensor Completion via Integer Programming [7.3149416054553065]
整数計画法に基づく非負のテンソル完備化へのアプローチを提案する。我々はアルゴリズムと同じ理論的な保証を維持できるいくつかの変種を探索するが、潜在的に高速な計算を提供する。
論文参考訳（メタデータ） (2022-11-28T21:00:25Z)
Nonnegative Tensor Completion via Integer Optimization [5.932152752097064]
我々は,本アルゴリズムが情報理論速度を達成しつつ,線形(数値耐性)なオラクルステップ数に収束することを証明した。ノルムは0-1ポリトープで定義されるので、これは整数線形計画法を用いてポリトープ上の線形分離問題を解くことができることを意味する。
論文参考訳（メタデータ） (2021-11-08T15:43:19Z)
Efficient Large Scale Inlier Voting for Geometric Vision Problems [3.1231364554255636]
コンピュータビジョンにおける多くの応用において、アウター・リジェクション(英語版)と等価に不整集合最適化(英語版)が重要な要素である。我々は、$Rd$の「交差」$k$次元曲面に基づいて、外周拒絶に対する効率的で一般的なアルゴリズムを提案する。本手法は, 複数枚のカメラにおいて, 多数の一致が低い不整合比で発生する問題に対するアプローチの汎用性を示す。
論文参考訳（メタデータ） (2021-07-25T14:13:07Z)
Mean Field Approximation for solving QUBO problems [0.0]
平均場焼鈍における統計物理学的アプローチと量子力学的アプローチが同じ結果をもたらすことを示す。提案手法は連続変数を持つ単純な勾配に基づく最小化からなるため,シミュレーションが容易である。
論文参考訳（メタデータ） (2021-06-06T20:35:28Z)
Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文参考訳（メタデータ） (2020-12-09T20:19:32Z)
Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文参考訳（メタデータ） (2020-07-07T21:26:35Z)
Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文参考訳（メタデータ） (2020-02-21T17:45:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。